第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=ëlog₃244û+1=6

6. 在结点个数为n(n>1)的四叉树中，高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？

【解答】

最大高度为n；有1个叶结点；n-1个分支结点；

最小高度为；

叶结点的个数为；

分支结点的个数为。

7．试分别找出满足以下条件的所有二叉树：

(1) 二叉树的前序序列与中序序列相同， 则或为空树，或为任一结点至多只有右子树的二叉树；

(2) 二叉树的中序序列与后序序列相同， 则或为空树，或为任一结点至多只有左子树的二叉树；

(3) 二叉树的前序序列与后序序列相同， 则或为空树，或为只有根结点的二叉树。

8． 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树。

【解答】