1、第六章 树和二叉树树的概念和基本术语二叉树 二叉树遍历二叉树的计数树与森林霍夫曼树 树的概念和基本术语树的定义 树是由 n (n 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根 (Root)的结点，它只有直接后继，但没有直接前驱； 当 n 1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 , T m，其中每个集合本身又是一棵树，并且称为根的子树 (SubTree)。ACGB DE FK LHMI J例如A只有根结点的树有 13个结点的树其中： A是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2
2、=C,G； T3=D,H,I,J,M,T1,T2,T3都是根 A的子树，且本身也是一棵树树的基本术语 1层2层4层3层height= 4ACGB DE FK LHMI J结点结点结点的度结点的度叶结点叶结点分支结点分支结点子女子女双亲双亲兄弟兄弟祖先祖先子孙子孙结点层次结点层次树的深树的深 度度树的度树的度有序树有序树无序树无序树森林森林结点：一个数据元素及指向其子树的分支。结点的度：结点拥有的子树个数。叶结点：度为零的结点。子女：结点子树的根。兄弟：同一结点子女。祖先：根到该结点路径上的所有结点。子孙：某结点为根的子树上的任意结点。结点层次：从根开始，根为第一层，根的子女为第二层，以此类推。
3、树的深度（高度）：树中结点的最大层次数。有序树：树中结点的子树由左向右有序。森林： m(m 0)棵互不相交的树。二叉树 (Binary Tree)定义五种形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。L LR R特点 每个结点至多只有两棵子树（二叉树中不存在度大于 2的结点）性质 1 在二叉树的第 i 层上至多有 2i 1个结点。 (i 1) 证明用归纳法 证明：当 i=1时，只有根结点， 2 i-1=2 0=1。假设对所有 j， ij1，命题成立，即第 j层上至多有 2 j-1 个结点。由归纳假设第 i-1 层上
4、至多有 2i 2个结点。由于二叉树的每个结点的度至多为 2，故在第 i层上的最大结点数为第 i-1层上的最大结点数的 2倍，即 2* 2i 2= 2 i-1。性质性质 2 深度为 k 的二叉树至多有 2k -1个结点 (k 1)。证明：由性质 1可见，深度为 k的二叉树的最大结点数为 20 + 21 + + 2 k-1 = 2k -1性质 3 对任何一棵二叉树 T, 如果其叶结点数为 n0, 度为 2的结点数为 n2,则 n0 n2 1.证明：若度为 1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义，n = n0 + n1 + n2 e = 2n2 + n1 = n - 1因此，有 2n2 + n1 = n0 + n1 + n2 - 1n2 = n0 - 1 n0 = n2 + 1 定义 1 满二叉树 (Full Binary Tree) 一棵深度为 k且有 2k -1个结点的二叉树称为满二叉树。两种特殊形态的二叉树62175438 9 10 11 13 14 1512满二叉树
