性质4具有n(n≥0)个结点的完全二叉树 的深度为Llog2(n)」+1 证明: 设完全二叉树的深度为h,则根据性 质2和完全二叉树的定义有 2h-1-1<n≤2h-1或2h-1≤n<2h 取对数h-1<log2n≤h,又h是整数 因此有h=Llog2m)」+
性质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无双亲 若>0,则的双亲为L(i-1)2」 若2*计+1<n,则i的左子女为2*计+1,若2*计+2<n,则i的 右子女为2*+2 若结点编号i偶数,且=0,则左兄弟结点i-1 若结点编号i奇数,且=n-1,则右兄弟结点为i+1 结点所在层次为Log2(i+1)」 6 680
性质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
二叉树的存储结构 顺序表示 3 3 89⑩ 619 1234567890234s678090 完全二叉树 一般二叉树 的顺序表示 的顺序表示
完全二叉树 一般二叉树 的顺序表示 的顺序表示 二叉树的存储结构 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
m链表表示 IChild data rChild 含两个指针域的结点结构 CHild data parent rChild 含三个指针域的结点结构 parent datal data CHild rChild 二叉链表 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 二叉树 二叉链表 三叉链表