满二叉树 完全二叉树 ■如果一橾二叉树的任何结点,或者是制叶 最多只有最下面的两层结点度数可以小于2 或者恰有两裸空子树,则此二叉树称作 最下一层的结点都集中最左边 叉树 F G 宜大_息啦张写 扩充二叉树 扩充二叉树 ■所有空子树,都增加空树叶 ■扩充二叉树是满二叉树 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点个数加1 路径长度 zom 外部路径长度E从扩充的二叉树的根到每个外部 结点的路径长度之和 内部路径长度I扩充的二叉树里从根到每个内部 结点的路径长度之和 四·E和两个量之间的关系为E=I+2n 42二叉树的主要性质 42二叉树的性质 满二叉树定理;非空满二叉树树叶数等于其分支结 2满二叉树定理推论:一个非空二叉树的空子树(指针) 点数加1 数目等于其结点数加1。 证明:设结点总数为n,叶结点数m,分支结点数b 有n(总结点数=m(叶)+b(分支)(公式4.1) 证明:设二叉树T,将其所有空子树换为树叶,记新的 每个分支,恰有两个子结点(满),故有2+b条边 〓叉树,除根结点外,每个结点都恰有一条边联摸父结 扩充满二叉树为T。所有原来T的结点现在是T的分支结 故共有n1条 点。根据满二叉树定理,新添加的树叶数目等于T结点 由(公式41),(公式42)得n1=m+b-1=2b,得出 个数加1。而每个新添加的树叶对应T的一个空子树。 Hb(分支)+1 区因此T中空子树数目等于T中结点数加1。 真大_血单2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 满二叉树 „ 如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作 满二叉树 A B C D E F G H I 树叶 两棵非空子树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 完全二叉树 A B G C A B C F G D E I J L D E F H K „ 最多只有最下面的两层结点度数可以小于2 „ 最下一层的结点都集中最左边 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 扩充二叉树 „ 所有空子树，都增加空树叶 wen wim xul yum wul xal wan zol wil yo zom xem yon zi 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 扩充二叉树 „ 扩充二叉树是满二叉树 „ 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点)个数加1 „ 路径长度 „ 外部路径长度E 从扩充的二叉树的根到每个外部 结点的路径长度之和 „ 内部路径长度I 扩充的二叉树里从根到每个内部 结点的路径长度之和 „ E和I两个量之间的关系为 E=I+2n 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 4.2 二叉树的主要性质 „ 1. 满二叉树定理：非空满二叉树树叶数等于其分支结 点数加1 „ 证明：设结点总数为n，叶结点数m，分支结点数b。 有n（总结点数= m（叶)+b（分支） (公式4.1) „ 每个分支，恰有两个子结点（满），故有2*b条边； „ 一颗二叉树，除根结点外，每个结点都恰有一条边联接父结 点，故共有n-1条边, 即n - 1 = 2b (公式4.2) „ 由(公式4.1)，(公式4.2)得 n-1=m+b-1 = 2b，得出 m(叶) = b（分支）+ 1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 4.2 二叉树的性质 2.满二叉树定理推论：一个非空二叉树的空子树(指针) 数目等于其结点数加1。 证明：设二叉树T，将其所有空子树换为树叶，记新的 扩充满二叉树为T’。所有原来T的结点现在是T’的分支结 点。根据满二叉树定理，新添加的树叶数目等于T结点 个数加1。而每个新添加的树叶对应T的一个空子树。 因此T中空子树数目等于T中结点数加1