Java数据结构-树与二叉树

1、学习目标树二叉树的定义及性质二叉树的遍历树与二叉树的转换树树的定义树的术语树的定义树（tree）是由n（n0）个结点组成的有限集合。n=0的树称为空树；对n0的树T，有：有一个特殊的结点称为根结点（root），它只有直接后继结点，没有直接前驱结点。当n1时，除根结点之外的其他结点分为m（m0）个互不相交的集合T1, T2, , Tm，其中每个集合Tm（1im）本身又是一棵结构与树类同的子树（subtree）。每棵子树的根结点有且仅有一个直接前驱结点，但可以有零或多个直接后继结点。树的术语结点孩子结点与双亲结点兄弟结点祖先结点与后代结点结点的度叶子结点与分支结点树的度二叉树的定义及性质二叉树的定

2、义二叉树的性质二叉树的存储结构声明二叉树类二叉树的定义二叉树的递归定义二叉树（binary tree）是n（n0）个结点组成的有限集合。n=0时称为空二叉树；n0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树的基本形态3个结点树与二叉树的基本形态二叉树的性质性质1若根结点的层次为1，则二叉树第i层的结点数目最多为2i-1（i1）。性质2在深度为k的二叉树中，至多有2k-1个结点（k0）。性质3二叉树中，若叶子结点数为n0，2度结点数为n2，则有n0=n2+1。满二叉树与完全二叉树性质4如果一棵完全二叉树有n个结点，则其深度。性质5若将一棵具有n个结点的完全二

3、叉树按顺序表示，对于编号为i（1in）的结点，有如下特点：若i=1，则i为根结点，无双亲；若i1，则i的双亲是编号为i /2的结点。若2in，则i的左孩子是编号为2i的结点；若2in，则i无左孩子。若2i+1n，则i的右孩子是编号为2i+1的结点；若2i+1n，则i无右孩子。二叉树的存储结构二叉树的顺序存储结构二叉树的链式存储结构声明二叉树类二叉树的结点类public class TreeNode public Object data; / 数据元素public TreeNode left, right; / 指向左、右孩子结点的链public TreeNode() this(?);publi

4、c TreeNode(Object o) / 构造有值结点data = o;left = null;right = null;二叉树类节点public void setData(Object data) this.data = data;public Object getData() return data;public void setLeft(TreeNode left) this.left = left;public TreeNode getLeft() return left;二叉树类节点public TreeNode setRight(TreeNode right) return t

5、his.right = right;public TreeNode getRight() return right;/ 测试一个节点是否是叶子节点public boolean isLeaf() return left = null & right = null;/如何从最左节点或最右节点获取数据？二叉树类节点/从最左节点或最右节点获取数据public Object getLeftmostData()if (left=null) return data; else return left.getLeftmostData();/如何删除最左节点或最右节点？提示：二叉树类节点/删除最左或最右节点public TreeNode removeLeftmost()if(left=null)/最左节点是根节点，因为它没有左孩子return right;else/一个递归调用删除左子树的最左节点left = left.removeLeftmost();return this;练习提供复制一棵二叉树的