性质4具有n(n≥0)个结点的完全二叉树 的深度为log2(n)」+1 证明: 设完全二叉树的深度为h,则根据性 质2和完全二叉树的定义有 2h-1-1<n≤2h-1或2h-1≤n<2 取对数h-1<log2n≤h,又h是整数 因此有h=Log2n)」+
性质4 具有 n (n 0) 个结点的完全二叉树 的深度为log2 (n) ＋1 证明： 设完全二叉树的深度为h，则根据性 质2和完全二叉树的定义有 2 h－1 - 1 < n 2 h- 1或 2 h－1 n < 2h 取对数 h－1 < log2n h，又h是整数， 因此有 h = log2 (n) ＋1
性质5如将一棵有n个结点的完全二叉树自页向 下,同一层自左向右连续给结点编号0,1,2, n-1,则有以下关系 若i=0,则i无双亲 若i>0,则的双亲为(i-1)/2」 n若2*计+1<n,则i的左子女为2*计1,着2*计+2<n,则i的 右子女为2*计+2 若结点编号为偶数,且!=0,则左兄弟结点i-1 若结点编号i奇数,且i=n-1,则右兄弟结点为+1 结点所在层次为log2i+1) 03 8⑨
性质5 如将一棵有n个结点的完全二叉树自顶向 下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系： ◼ 若i = 0, 则 i 无双亲 若i > 0, 则 i 的双亲为(i -1)/2 ◼ 若2*i+1 < n, 则 i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的 右子女为2*i+2 ◼若结点编号i为偶数，且i!=0,则左兄弟结点i-1. ◼若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1. ◼结点i 所在层次为log2(i+1) 0 7 1 2 3 4 5 6 8 9
二叉树的存储结构 顺序表示 89⑩ 9)0 123456789012340567800910 完全二叉树 一般二叉树 的顺序表示 的顺序表示
完全二叉树 一般二叉树 的顺序表示 的顺序表示 二叉树的存储结构 1 1 2 3 4 5 6 7 8 910 9 1 2 3 4 0 5 6 7 8 0 0 910 2 4 8 9 10 5 6 7 3 1 2 3 4 5 6 7 8 ▪顺序表示 109
链表表示 IChild data rChild 含两个指针域的结点结构 CHild data parent rChild 含三个指针城的结点结构 parent datal data Child child 二叉链表 CHild rChild 三叉链表
▪链表表示 lChild data rChild data lChild rChild 二叉链表 含两个指针域的结点结构 lChild data parent rChild 含三个指针域的结点结构 parent data lChild rChild 三叉链表
二叉树链表表示的示例 root root root △ @巫四区四下 二叉树 二叉链表 三叉链表
二叉树链表表示的示例 A A A B B B C D C D C D E F E F E F root root root 二叉树 二叉链表 三叉链表