第6章 综合练习
6.2综合练习
1. 设在树中,结点x 是结点y 的双亲时,用<x,y>来表示边。已知一棵树边的集合为:{<a,b>,<a,c>,<a,d>,<a,e>,<c,f>,<c,g>,<c,h>,<d,i>,<e,j>,<e,k>,<g,l>,<l,m>,<l,n>},用树形表示法画出此树,并回答下列问题:
(1)哪个是根结点? (2)哪些是叶子结点?
(3)哪个是e的孩子? (4)哪些是g的祖先?
(5)哪些是c的子孙? (6)哪些是f的兄弟?
(7)结点b和j的层次各是多少? (8)树的深度是多少?
(9)树的度数是多少?
【解答】

(1)a是根结点
(2)b,f,h,i,j,k,l,m,n是叶结点
(3)j,k是e的孩子
(4) a,c是g的祖先
(5)f,g,h,l,m,n是c的子孙
(6) g,h是f的兄弟
(7)b的层次是2,j的层次是3 (8)树的深度是5。
(9)树的度是4
2.
列出图6.12所示二叉树的叶结点、分支结点和每个结点的层次。
【解答】
E、I、H是叶结点;A、B、C、D、F、G是分支结点;
A的层次是1,B、F的层次是2,C、G、H的层次是3,D、I的层次是4,E的层次是5。
3.使用 (1) 顺序表示 (2) 二叉链表表示法(3)三叉链表分别画出图6.13所示二叉树的存储表示。

1 2 3 4 5 6 7 8 9 10 11 12 13
A
B D C φ E F φ φ φ φ φ G
4 某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点数是多少。
【解答】
∵ n=n0+n1+n2 且 n2=n0-1
∴ n=2n0+n1-1=2*20+30-1=69
5.
将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度是多少。
【解答】
H=ëlog3244û+1=6
6. 在结点个数为n(n>1)的四叉树中,高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?高度最小的树的高度是多少?它有多少个叶结点?多少个分支结点?
【解答】
最大高度为n;有1个叶结点;n-1个分支结点;
最小高度为
;
叶结点的个数为
;
分支结点的个数为
。
7.试分别找出满足以下条件的所有二叉树:
(1) 二叉树的前序序列与中序序列相同, 则或为空树,或为任一结点至多只有右子树的二叉树;
(2) 二叉树的中序序列与后序序列相同, 则或为空树,或为任一结点至多只有左子树的二叉树;
(3)
二叉树的前序序列与后序序列相同, 则或为空树,或为只有根结点的二叉树。
8. 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。
【解答】