42二叉树的主要性质 满二叉树定理:非空满二叉树树叶数等于其分支结 点数加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 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
42二叉树的性质 2.满二叉树定理推论:一个非空二叉树的空子树(指针) 数目等于其结点数加1 证明:设二叉树T,将其所有空子树换为树叶,记新的 扩充满二叉树为T。所有原来T的结点现在是T的分支结 点。根据满二叉树定理,新添加的树叶数目等于T结点 个数加1。而每个新添加的树叶对应T的一个空子树。 因此T中空子树数目等于T中结点数加1 北京大学信息学院张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 4.2 二叉树的性质 2.满二叉树定理推论：一个非空二叉树的空子树(指针) 数目等于其结点数加1。 证明：设二叉树T，将其所有空子树换为树叶，记新的 扩充满二叉树为T’。所有原来T的结点现在是T’的分支结 点。根据满二叉树定理，新添加的树叶数目等于T结点 个数加1。而每个新添加的树叶对应T的一个空子树。 因此T中空子树数目等于T中结点数加1
42二叉树的性质 3任何一颗二叉树,度为0的结点比度为2的结点多一个 证明:设有n个结点的二叉树的度为0、1、2的结点数 分别为=no,n1,n2,则 n t n,t n 2 (公式4.3) 设边数为e因为除根以外,每个结点都有一条边进入,故 n=e+1。由于这些边是有度为1和2的的结点射出的, 因此e=n1+2·n2,于是 n=e+1 +2·n2+1 (公式4.4) 因此由公式(1)(2)得 0+n1+n2=n1+2·n2+1 即 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 4.2 二叉树的性质 3.任何一颗二叉树，度为0的结点比度为2的结点多一个 证明：设有n个结点的二叉树的度为0、1、2的结点数 分别为=n0，n1，n2，则 n = n0 + n1 + n2 (公式4.3) 设边数为e。因为除根以外，每个结点都有一条边进入，故 n = e + 1。由于这些边是有度为1和2的的结点射出的， 因此e = n1+ 2·n2，于是 n = e + 1= n1 + 2·n2 + 1 （公式4.4） 因此由公式（1）（2）得 n0 + n1 + n2 = n1 + 2·n2 + 1 即 n0 = n2 + 1
42二叉树的性质 4.二叉树的第i层(根为第0层,i≥1)最多有21 个结点 5.高度为k(深度为k-1。只有一个根结点的二叉 树的高度为1,深度为0)的二叉树至多有2k-1个 结点 6.有n个结点(n>0)的完全二叉树的高度为 「og2(n+1)(深度为og2(n+1)1-1) 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 14
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 4.2 二叉树的性质 4. 二叉树的第i层（根为第0层，i≥1）最多有2i 个结点 5. 高度为k(深度为k-1。只有一个根结点的二叉 树的高度为1，深度为0)的二叉树至多有2k-1个 结点 6. 有n个结点（n>0）的完全二叉树的高度为 ⎡log2 (n+1)⎤ (深度为⎡log2 (n+1)⎤ - 1)
43二叉树的抽象数据类型 逻辑结构十运算: 针对整棵树 初始化二叉树 n合并两棵二叉树 围绕结点 访问某个结点的左子结点、右子结点、父结点 访问结点存储的数据 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 15
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 4.3 二叉树的抽象数据类型 逻辑结构 + 运算： 针对整棵树 初始化二叉树 合并两棵二叉树 围绕结点 访问某个结点的左子结点、右子结点、父结点 访问结点存储的数据