性质3： 对任何一棵二叉树，若它含有no个叶子结 点、n2个度为2的结点，则必存在关系式： no=n2+1。 证明： 设二叉树上结点总数n=n,+n1+n2 又二叉树上分支总数b=n+2n2 而b=n-l=no+n1+n2-I 由此，o=n2+1
§ 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结 点、n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1
★几种特殊形式的二叉树 满二叉树 ●定义：一棵深度为k且有2-1个结点的二叉树称为~ ●特点：每一层上的结点数都是最大结点数 $完全二叉树 ●定义：深度为k,有个结点的二又树当且仅当 其每一个结点都与深度为k的满二叉树中编号 从1至n的结点一一对应时，称为~ ●特点 ◆叶子结点只可能在层次最大的两层上出现 ◆对任一结点，若其右分支下子孙的最大层 次为L，则其左分支下子孙的最大层次必为 L或L+1
几种特殊形式的二叉树 ❖满二叉树 ⚫定义： 一棵深度为 且有2 −1个结点的二叉树称为~ k k ⚫特点：每一层上的结点数都是最大结点数 ❖完全二叉树 ⚫定义：深度为k，有n个结点的二叉树当且仅当 其每一个结点都与深度为k的满二叉树中编号 从1至n的结点一一对应时，称为~ ⚫特点 ◆叶子结点只可能在层次最大的两层上出现 ◆对任一结点，若其右分支下子孙的最大层 次为L，则其左分支下子孙的最大层次必为 L 或L+1
2 3 6 2 3 4 6 8 完全二叉树？
1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 7 1 2 3 4 5 6 完全二叉树？
性质4： 具有n个结点的完全二叉树的深度为 Llog2nJ+1。 证明： 设完全二叉树的深度为k 则根据第二条性质得2kl≤n<2k 即k-l≤log2n<k 因为k只能是整数，因此，k=llog2n/+1
§ 性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。 证明： 设完全二叉树的深度为k 则根据第二条性质得 2 k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1
◆性质5：如果对一棵有个结点的完全二叉树的 结点按层序编号，则对任一结点i(1≤i≤)，有： (1)如果i=1,则结点i是二叉树的根，无双亲；如 果i>1,则其双亲是i/2 (2)如果2i>n,则结点i无左孩子；如果2i≤n,则 其左孩子是2引 (3)如果2i+1>n,则结点i无右孩子；如果2i+1≤n, 则其右孩子是2i+1
◆性质5：如果对一棵有n个结点的完全二叉树的 结点按层序编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如 果i>1，则其双亲是i/2 (2) 如果2i>n，则结点i无左孩子；如果2in，则 其左孩子是2i (3) 如果2i+1>n，则结点i无右孩子；如果2i+1n， 则其右孩子是2i+1