完全二叉树 满二叉树: 完全二叉树: 1、满二叉树 每层结点 2、从满二叉树 数最多 最底层从右向左 依次去掉若干结 点形成的 P)(a)(R)(s)(u)(v)(w 性质4:具有n个结点的完全二叉树高度为ogn」+1 证:根据性质2和完全二叉树的定义:设其高度为k 2k-1-1<n<=2k-1 k-1<n+1<=2k 2k1<=n<2 故:k-1<=log2n<k;原命题得证
完全二叉树 B C E F D L A P Q R S U B C E F D L A P Q R S U V W X •满二叉树: 每层结点 数最多 •完全二叉树: 1、满二叉树 2、从满二叉树 最底层从右向左 依次去掉若干结 点形成的 性质4：具有 n 个结点的完全二叉树高度为 log2n + 1 证：根据性质 2 和完全二叉树的定义：设其高度为 k 2 k-1 -1< n <= 2k -1 2 k-1 < n + 1 <= 2k 2 k-1 <= n < 2k 故：k-1 <= log2n < k ; 原命题得证
完全二叉树 性质5:对一棵有n个结点的完全二叉树按照从第一层(根所在的层次〕到最后一层,并且 每一层都按照从左到右的次序进行编号。根结点的编号为1,最后一个结点的编号 为n。 1:对任何一个编号为i的结点而言,它的左儿子的编号为2(若2i<=n),而右儿子的 编号为2H1(若2i+1<=n)。 2:对任何一个编号为的结点而言,它的父亲结点的的编号为j2}根结点无父结 证:对编号归纳 3 7 89101112
完全二叉树 B C E F D L A P Q R S U 性质5：对一棵有 n 个结点的完全二叉树按照从第一层（根所在的层次〕到最后一层，并且 每一层都按照从左到右的次序进行编号。根结点的编号为 1，最后一个结点的编号 为 n。 1：对任何一个编号为 i 的结点而言，它的左儿子的编号为 2i( 若 2i <= n) ,而右儿子的 编号为 2i+1(若 2i +1 <= n)。 2：对任何一个编号为 j 的结点而言，它的父亲结点的的编号为 j/2 。根结点无父结 点。 证：对编号归纳 8 9 10 11 12 4 5 6 7 3 2 1
二叉树的顺序存储 一般情况: data left right 01234567 195 G|87 14 应用范围:适用于二叉树上的结点个数已知,或不支持动态存储分配的高级语言
二叉树的顺序存储 一般情况： A B C D E F G I H L A 1 -1 B 9 2 C 5 3 D 6 -1 E -1 -1 F -1 -1 G 8 7 H -1 -1 I -1 -1 L -1 4 0 1 2 3 4 5 6 7 8 9 data left right 应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言
二叉树的顺序存储 特殊情况:完全二叉树 data left right 234567 2468 357900 3456 000000 0000 10 应用范围:适用于完全二叉树,且结点个数已知
二叉树的顺序存储 特殊情况：完全二叉树 A 2 3 B 4 5 C 6 7 D 8 9 E 10 0 F 0 0 G 0 0 H 0 0 I 0 0 L 0 0 0 1 2 3 4 5 6 7 8 9 10 data left right 应用范围：适用于完全二叉树，且结点个数已知。 D C E F G B A H I L A B C D E F G H I 0 1 2 3 4 5 6 7 8 9 L
二叉树的顺序存储 特殊情况:若不是完全二叉树,许多数据场为空,不合算。如下例所示: 考虑浪费空间最多的情况,是一种什么情况?浪费2^k-1-k个单元 3456
二叉树的顺序存储 特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示： 考虑浪费空间最多的情况，是一种什么情况？ 浪费 2^k - 1 – k 个单元 A B ∧ D ∧ ∧ ∧ H I 0 1 2 3 4 5 6 7 8 9 D B A H I