Java数据结构之树与二叉树.ppt

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。,满二叉树与完全二叉树 性质

3、4 如果一棵完全二叉树有n个结点，则其深度。 性质5 若将一棵具有n个结点的完全二叉树按顺序表示，对于编号为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,

4、right; / 指向左、右孩子结点的链 public TreeNode() this(?); public 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() retur

5、n left; ,二叉树类节点,public TreeNode setRight(TreeNode right) return this.right = right; public TreeNode getRight() return right; / 测试一个节点是否是叶子节点 public boolean isLeaf() return left = 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; ,练习,提供复制一棵二叉树的方