第4章 树与二叉树

1、 A11 A21 A22 A31A32A33A34A35 A11 A21 A22 A31A32A33A34A35 A11 A21 A22 A31A32A33A34A35 A11 A21 A22 A31A32A33A34A35 共两棵 共五棵 第 层 1=2 第 层 12=2 第i层 2i-1 20+21+22+2k-1=2k-1 1log 2 + +n 高度为k的满二叉树有2k-1个结点； 1 23 456 7 8 9 10111213 2/ i 2i2i+1 2/ i 根据性质5，从编号51到100都是叶子。 共有50个叶子。 1 100 50 a)共有26-1+10=73个结点； b)37

2、到73都是叶子，共37个叶子结点； c)度为1的结点数为0。 1 73 36 A GFED CB HI 10 2 1 3 4 5 67 8 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 A C B 1 3 7 54 2 6 bnode lchild data rchild A G F E DC B A B E C D F G T n个结点的二叉链表共有2n个指针域。 其中n-1个不空，剩下2n-(n-1)=n+1个指针域为空。 (1)若T为，遍历；否则转(2) D LR (2) 设二叉树的形态如右图： 假设左右子树能遍历（用 L， R分别表示其遍历），

3、则整个二叉树 可有如下形式的遍历： 先左后右：DLR LDR LRD 先右后左：DRL RDL RLD 根序 根序 根序 对于左右子树的遍历，可按照 与相同的方式遍历（递归调用） (1) A _ _ AA (2) AB _ _ G _ _ GBBG (3) ABC_ _ D _ _ G H I C C DD 先序：ABCEDFGHI (4) ABC E D F G H I A G FE DC B HI 分别写出右图二叉树的 先序、中序和后序序列。 中序：CEBDFAHGI (4) C E B D F A H G I (1) _A_ AA (2) _ B _ A _ G _ GBBG (3) _

4、C_ B_D_ A H G I CCDD A G FE DC B HI 分别写出右图二叉树的 先序、中序和后序序列。 (4) E C F D B H I GA (1) _ _ A AA (2) _ _ B_ _GA GBBG (3) _ _ C _ _D B H I GA CCDD 后序：ECFDBHIGA A G FE DC B HI 分别写出右图二叉树的 先序、中序和后序序列。 A B C E D F G H I 先序：ABCDEFGHI 中序：CBEDFAGIH 后序：CEFDBIHGA A CDBEGF E B A CDG F G F D C B A E A C B A ED G F

5、G F D C B A E 思考思考：只有先序和后序能否唯一还原二叉树？ A B C E D F G H I n个结点的二叉链表共有2n个指针域。 其中n-1个不空，剩下2n-(n-1)=n+1个指针域为空。 A G F E DC B A B E C D F G T 中序线索二叉树 A B C E D F G H I 先序线索二叉树 A B C E D F G H I 左左 A G FE DCB H I A B C D E F G H I 1 2 3 4 5 6 7 8 9 data parents 0 1 1 2 3 0 8 1 2 BCD EF G I A B C D E F G H I

6、data firstchild A G FE DCB H I A B C D E F G I H A G FE DCB H I firstson data nextbrother 引用：tnode *T 稍变形后与二叉链表结构相同 所以任意一棵树（森林） 必然与的一棵二叉树一一对应。 A B C D E F G I H A B F G E C D I H firstson data nextbrother lchild data rchild A B I DGF H CE A GFE DCB H I K L K L A B CE D F G A B C E D F G A GFE DCB H

7、I K L 先序序列：ABEFCGDHIKL 后序序列：EFBGCIHDALK ：树（森林）的后序遍历序列 与对应的二叉树相同。 A GFE DCB H I K L = n i iil w 1 A B CE D K G H JI F0.05 0.6 0.1 0.10.10.05 WPL=0.6*4+0.1*4+0.05*3+0.05*2+0.1*2+0.1*2 66 34121085618T= 34 7 56 11 8 15 10 21 12 27 18 39 WPL= (3+4+5+6)* 4+(8+10)*3+(18+12)*2 =186 WPL=66+27+39+15+21+7+11=186 101 811 19 56 1115 26 20 39 36 62101+62+39+26+19+11 =258 WPL= 101 1511 26 56 118 1920 39 101+62+39+26+