第4课 树和二叉树(2)

9．已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？ 参考答案：

根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是?i/2?，故A[i]和A[j]的最近公共祖先可如下求出：

while(i/2!=j/2)

if(i>j) i=i/2; else j=j/2;

退出while后，若i/2=0，则最近公共祖先为根结点，否则最近公共祖先是i/2。

10．给定K(K>=1)，对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最小高度。 参考答案：

N个结点的K叉树，最大高度N（只有一个叶结点的任意k叉树）。设最小高度为H，第i(1<=i<=H)层的结点数Ki-1，则N=1+k+k2+?+ kH-1，由此得H=?logK(N(K-1)+1)?

11．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 参考答案：

结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。

12．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。 参考答案：

设分支结点和叶子结点数分别是为nk和n0，因此有n=n0+nk (1) 另外从树的分枝数B与结点的关系有n=B+1=K*nk +1 (2) 由(1)和(2)有n0=n-nk=(n(K-1)+1)/K。

13．若一棵完全二叉树中叶子结点的个数为n，且最底层结点数≧2，求其深度。 参考答案：?log2n?+1。

14．已知完全二叉树有30个结点，则其中度为0的结点有多少个？ 参考答案：15。

15．试证明，在具有n(n>=1)个结点的m次树中，有n(m-1)+1个指针是空的。 参考答案：

n个结点的m次树，共有n*m个指针。除根结点外，其余n-1个结点均有指针所指，故空指针数为n*m-(n-1)=n*(m-1)+1。

16．假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？

参考答案：结点数的最大值2h-1（满二叉树），最小值2h-1（第一层根结点，其余每层均两个结点）。

17．试证明同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc后序bca中序bac。 参考答案：前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。

18．试找出满足下列条件的二叉树：(1)先序序列与后序序列相同；(2)中序序列与后序序列相同；(3)先序序列与中序序列相同；(4)中序序列与层序序列相同。 参考答案：

(1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树；(2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树；(3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树；(4)若中序序列与层次遍历序列相同，则或为空树，

或为任一结点至多只有右子树的二叉树

19．将如下由三棵树组成的森林转换为二叉树。 D G A J H I E B C L M K N O F 参考答案：

P A

B D E G C

H F I KO J L M

P N

O

20．设一棵二叉树的先序遍历序列为A B D F C E G H、中序遍历序列为B F D A G E H C，试：(1)画出这棵二叉树；(2)画出这棵二叉树的后序线索二叉树；(3)将这棵二叉树转换成对应的树（或森林）。 参考答案：

21．设某二叉树的前序遍历序列为ABCDEFGGI，中序遍历序列为BCAEDGHFI，试画出该二叉树。 参考答案：

A

B D

F C E

G I

H

22．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 参考答案：

先序序列是“根左右”，后序序列是“左右根”，可见对任意结点，若至多只有左孩子或至多只有右孩子，均可使前序序列与后序序列相反。

23．已知一个森林的先序遍历序列为ABCDEFGHIJKLMNO，后序遍历序列为CDEBFHIJGAMLONK，试构造出该森林。 参考答案：

A B C D E F H G I J L MG K N O

24．画出同时满足下列两个条件的两棵不同的二叉树：(1)先序遍历序列为ABCDE；(2)高度为5，而其对应的树/森林的高度最大为4。

参考答案：

A B C D E E

D C A B

25．一棵二叉树的先序遍历序列为_ _ C D E _ G H I _ K、中序遍历序列为C B _ _ F A _ J K I G、后序遍历序列为_ E F D B _ J I H _ A，其中一部分未标出，试画出该二叉树。 参考答案：

A

G B H C D I E F J

K

26．用一维数组存放的一棵完全二叉树如下图所示： A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序。 参考答案：HIDJKEBLFGCA。

27．设二叉树T的存储结构如下：

1 2 3 4 5 6 7 8 9 10 Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 9 7 B 4 5 A 0 8 C 0 0 E 0 10 G 0 1 I 0 其中Lchild、Rchild分别为结点的左、右孩子指针域，Data为结点的数据域，若根指针T的值为6，试：(1)画出二叉树的逻辑结构；(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列；(3)画出二叉树的后序线索树。 参考答案：

前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA

28．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 参考答案：1个

29．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句。结点结构为(ltag,lc,data,rtag,rc)。 参考答案：

if(p->ltag==0) return(p->lchild); //左孩子不空，左孩子为直接后继结点 else return(p->rchild); //左孩子空，右孩子（或右线索）为后继

30．对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱？ 参考答案：

后序线索树中结点的后继（根结点无后继），要么是其右线索（当结点的rtag=1时），要么是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点，若其左标记等于1,则左子女为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。

31．假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。

参考答案：

各字母编码如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011 注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。

32．设有正文AADBAACACCDACACAAD，字符集为{A,B,C,D}，试设计一套二进制编码，使得上述正文的编码最短。 参考答案：

字符A、B、C、D出现的次数分别为9、1、5、3，其哈夫曼编码如下A:1、B:000、C:01、D:001。

33．设T是一棵二叉树，除叶子结点外，其它结点的度皆为2，若T中有6个叶结点，试问：(1)树T的最大深度和最小可能深度分别是多少？(2)树T中共有多少非叶结点？(3)若叶结点的权值分别为1、2、3、4、5、6，请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 参考答案：

(1)最大深度6，最小深度4； (2)非叶结点数5；

(3)哈夫曼树见下图，其带权路径长度wpl=51。

34．一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，问：(1)第ｉ层上有多少个结点？(2)编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？(3)编号为ｐ的结点的双亲结点（若存在）的编号是多少？ 参考答案： (1)ki?1个

(2)（１＋（ｐ－１）＊ｋ）＋ｉ (3)??p?k?2?（ｐ≠１） 】 ?k??

三、算法设计题

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第4课 树和二叉树(2)在线全文阅读。