4.满二叉树( full binary tree) 深度为k且有2-1个结点的二叉树。 ③○ ③③ T2 T3 T4 (1)n个结点的满二叉树的深度=10g2(n+1) 设深度为k 2k-1=n 2k=n+1 k=log2(n+1)
4.满二叉树（full binary tree)---- 深度为k且有2 k -1个结点的二叉树。 T1 T2 T3 T4 (1) n个结点的满二叉树的深度=log2(n+1) 设深度为k ∵ 2 k - 1＝n 2 k＝n + 1 ∴ k=log2(n+1)
(2)顺序编号的满二叉树 6 ②③④⑤⑥⑦(8⑩①四④ T2 T3 T4 设满二叉树有n个结点,编号为1,2 ··· ●左小孩为偶数,右小孩为奇数; ●结点i的左小孩是2i, 2i≤n 结点i的右小孩是2i+1 2i+1≤n 结点的双亲是i/2」 2≤i≤n 结点的层号=L1og2i+1=「1og2(i+1)11≤i≤n
(2)顺序编号的满二叉树 1 2 3 1 2 4 5 8 9 10 11 3 6 7 12 13 14 15 1 2 3 4 5 6 7 1 设满二叉树有n个结点,编号为1,2,...,n ● 左小孩为偶数，右小孩为奇数； ● 结点i的左小孩是2i， 2i≤n 结点i的右小孩是2i+1, 2i+1≤n 结点i的双亲是i/2； 2≤i≤n ● 结点i的层号= log2 i + 1 = log2(i+1) 1≤i≤n T1 T2 T3 T4
LⅩ」=不大于X的最大整数,取X的下限/地板 ●「Ⅹ7=不小于X的最小整数,取X的上限/天花板 「3.11=4,「3.91 5.完全二叉树( full binary tree) 深度为k的有n个结点的二叉树,当且仅当每一个结点 都与同深度的满二叉树中编号从1至n的结点一一对应,称 之为完全二叉树(其它教材称为“顺序二叉树”) 例.完全二叉树 ① B T2 ①⑥④⑤6⑦ T3 T4 T5
● X = 不大于X的最大整数，取X的下限/地板 ● X = 不小于X的最小整数，取X的上限/天花板 例 3.1 = 3, 3.9 = 3, 3 = 3 3.1 = 4, 3.9 = 4 3 = 3 5.完全二叉树（full binary tree)---- 深度为k的有n个结点的二叉树,当且仅当每一个结点 都与同深度的满二叉树中编号从1至n的结点一一对应,称 之为完全二叉树（其它教材称为“顺序二叉树”）。 例. 完全二叉树: 1 2 1 1 2 3 4 5 T1 T2 T3 T4 T5 A B E D C F 1 2 3 4 5 6 7