二叉树 Q2 3 5 6 4 5 6 ③6③ 满二叉树 完全二叉树 11
二叉树 11 1 2 4 5 8 9 10 11 12 13 14 15 3 6 7 1 2 4 5 8 9 10 3 6 7 满二叉树 完全二叉树
二叉树 n性质4 口具有n个结点的完全二叉树的深度为log2n+1) 口证明: 设完全二叉树的深度为h,则有 上面h-1层结点数包括h层的最大结点数 2h-1-1<n≤2h-1 3 2h-1<n+1≤2h h-1<log2+1)≤h 6 h=「0og4r+1)1 ⑩⑤ 性质4也适用于理想平衡二叉树12
二叉树 ◼ 性质4 具有n个结点的完全二叉树的深度为log2 (n+1) 证明： ➢ 设完全二叉树的深度为h，则有 ➢ 2 h-1-1＜n≤ 2 h-1 ➢ 2 h-1＜n+1≤2 h ➢ h-1＜log2 (n+1)≤h ➢ h = log2 (n+1) 12 上面h-1层结点数 包括h层的最大结点数 1 2 4 5 10 13 15 3 6 7 性质4也适用于理想平衡二叉树
Q2 二叉树 ④⑥⑦ n性质5 8)(9 口若将一棵有n个结点的完全二叉树自顶向下,同 层自左向右连续给结点编号1,2,3,,n,则有: 若i=1,则i无父结点; 若i>1,则i的父结点为i2; 若2*i≤n,则i的左子女为2*i 若2H+1≤n,则i的右子女为2*1; 若i为奇数,且il=1,则其左兄弟为i-1 若i为偶数,且i=n,则其右兄弟为+1 所在层次为log2(+1(或者logi+1,两者等效) 13
二叉树 ◼ 性质5 若将一棵有n个结点的完全二叉树自顶向下，同一 层自左向右连续给结点编号1,2,3,…,n，则有： ➢ 若i = 1, 则 i 无父结点； ➢ 若i > 1, 则 i 的父结点为i/2； ➢ 若2*i ≤ n, 则 i 的左子女为 2*i； ➢ 若2*i+1 ≤ n, 则 i 的右子女为2*i+1； ➢ 若 i 为奇数, 且i !=1, 则其左兄弟为i-1； ➢ 若 i 为偶数, 且i != n，则其右兄弟为i+1。 ➢ i所在层次为log2 (i+1)（或者log2 i +1，两者等效） 13 1 2 4 5 8 9 10 3 6 7
二叉树的存储表示 n二叉树的数组存储表示 众 2 3 Q2 3 5 6 5 6 8 234 67 9 1315 般二叉树的顺序表示 234 789101112 完全二叉树的顺序表示 14
二叉树的存储表示 ◼ 二叉树的数组存储表示 14 1 2 4 5 8 9 10 11 12 3 6 7 1 2 4 5 8 9 10 11 12 13 14 15 3 6 7 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 6 7 8 9 13 15 完全二叉树的顺序表示 一般二叉树的顺序表示
二叉树的存储表示 n二叉树的数组存储表示 完全二又树适用于数组存储表示Q 口一般二叉树不适用 3 5 !8:!9101111112113114 3 15 单支树的顺序表示 15
二叉树的存储表示 ◼ 二叉树的数组存储表示 完全二叉树适用于数组存储表示 一般二叉树不适用 15 1 2 4 5 8 9 10 11 12 13 14 15 3 6 7 1 3 7 15 单支树的顺序表示