树和二叉树习题

第四课 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（ ）。

A．-A+B*C/DE B．-A+B*CD/E C．-+*ABC/DE D．-+A*BC/DE 参考答案：D

2．当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（ ）。

A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i/2] D．无法确定 参考答案：D

3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A．250 B．500 C．254 D．505 E．以上答案都不对 参考答案：E

4．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为（ ）。

A．5 B．6 C．7 D．8 参考答案：D

5．在下述结论中，正确的是（ ）。

①只有一个结点的二叉树的度为0； ②二叉树的度为2；

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 参考答案：D

6．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（ ）。

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 参考答案：A

7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。

A．9 B．11 C．15 D．不确定 参考答案：B

8．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A．4 B．5 C．6 D．7 参考答案：C

9．设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A．M1 B．M1+M2 C．M3 D．M2+M3 参考答案：D

10．具有10个叶结点的二叉树中有（ ）个度为2的结点。

A．8 B．9 C．10 D．11 参考答案：B

11．下述编码中不是前缀码的是（ ）。

A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 参考答案：B

12．设给定权值总数有n个，其哈夫曼二叉树的结点总数为（ ）。

A．不确定 B．2n C．2n+1 D．2n-1 参考答案：D

13．下面几个符号串编码集合中，不是前缀编码的是（ ）。

A．{0,10,110,1111} B．{11,10,001,101,0001}

C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 参考答案：B

14．有关二叉树下列说法正确的是（ ）。

A．二叉树的度为2 B．一棵二叉树的度可以小于2

C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 参考答案：B

15．二叉树的第i层上最多含有结点数为（ ）。

A．2i B．2i-1-1 C．2i-1 D．2i -1 参考答案：C

16．一个具有1025个结点的二叉树的高h为（ ）。

A．11 B．10 C．11至1025之间 D．10至1024之间 参考答案：C

17．一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有（ ）结点。

A．2h B．2h-1 C．2h+1 D．h+1 参考答案：B

18．对于有n个结点的二叉树，其高度为（ ）。

A．nlog2n B．log2n C．?log2n?+1 D．不确定 参考答案：D

19．一棵具有n个结点的完全二叉树的树高度（深度）是（ ）。

A．?logn?+1 B．logn+1 C．?logn? D．logn-1 参考答案：A

20．深度为h的满m叉树的第k层有（ ）个结点。(1=

A．mk-1 B．mk-1 C．mh-1 D．mh-1 参考答案：A

21．在一棵高度为k的满二叉树中，结点总数为（ ）。

A．2k-1 B．2k C．2k-1 D．?log2k?+1 参考答案：C

22．高度为k的二叉树最大的结点数为（ ）。

A．2k B．2k-1 C．2k-1 D．2k-1-1 参考答案：C

23．一棵树高为k的完全二叉树至少有（ ）个结点。

A．2k–1 B．2k-1–1 C．2k-1 D．2k 参考答案：C

24．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）。

A．4 B．5 C．6 D．7 参考答案：C

25．利用二叉链表存储树，则根结点的右指针是（ ）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空 参考答案：C

26．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）次序的遍历实现编号。

A．先序 B．中序 C．后序 D．从根开始按层次遍历 参考答案：C

27．树的后根遍历序列等同于该树对应的二叉树的（ ）。

A．先序序列 B．中序序列 C．后序序列 参考答案：B

28．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次 参考答案：C

29．下述二叉树中，（ ）满足从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆 参考答案：D

30．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。

A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 参考答案：B 31．已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。

A．CBEFDA B．FEDCBA C．CBEDFA D．不定 参考答案：A

32．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（ ）。

A．acbed B．decab C．deabc D．cedba 参考答案：D

33．某二叉树中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是（ ）。

A．EGFACDB B．EACBDGF C．EAGCFBD D．上面的都不对 参考答案：B

34．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）。

A．先序 B．中序 C．后序 D．层序 参考答案：B

35．若二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（ ）。

A．E B．F C．G D．H 参考答案：C

36．将一棵树T转换为孩子兄弟链表表示的二叉树H，则T的后序遍历序列与H的（ ）序列相同。

A．前序遍历 B．中序遍历 C．后序遍历 参考答案：B

37．某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1,2, ... ,n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（ ）编号的。

A．中序遍历序列 B．前序遍历序列 C．后序遍历序列 D．层次顺序 参考答案：B

38．下面的说法中正确的是（ ）。

(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； (2)按二叉树定义，具有三个结点的二叉树共有6种。

A．(1)(2) B．(1) C．(2) D．(1)、(2)都错 参考答案：B

39．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。

A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 参考答案：C

40．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）

A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 参考答案：B

41．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。

A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树

参考答案：C

42．由3个结点可以构造出（ ）种不同的二叉树。

A．2 B．3 C．4 D．5 参考答案：D

43．设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A．n-1 B．n C．n+1 D．n+2 参考答案：C

44．一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：（ ）。

A．不确定 B．0 C．1 D．2 参考答案：D

45．一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：（ ）。

A．0 B．1 C．2 D．不确定 参考答案：C

46．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。

A．X的双亲 B．X的右子树中最左的结点

C．X的左子树中最右结点 D．X的左子树中最右叶结点 参考答案：C

47．引入二叉线索树的目的是（ ）。

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 参考答案：A

48．线索二叉树是一种（ ）结构。

A．逻辑 B．逻辑和存储 C．物理 D．线性 参考答案：C

49．n个结点的线索二叉树上含有的线索数为（ ）。

A．2n B．n-1 C．n+1 D．n 参考答案：C

50．（ ）的遍历仍需要栈的支持。

A．前序线索树 B．中序线索树 C．后序线索树 参考答案：C

51．二叉树在线索后，仍不能有效求解的问题是（ ）。

A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继 参考答案：D

52．由3个结点可以构造出（ ）种不同的有序树。

A．2 B．3 C．4 D．5 参考答案：A

二、应用题

1．设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？ 参考答案：

方法有二。一是对该算术表达式（二叉树）进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、-、*、/ 等）进行最后求值。

2．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。 参考答案：

*

++ +fgh +*

a+bc

de

3．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域?为什么? 参考答案：

n（n>0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。

4．试证明一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。 参考答案：

设二叉树度为0和2的结点数及总的结点数分别为n0，n2和n，则n=n0+n2 (1)

再设二叉树的分支数为B，除根结点外，每个结点都有一个分支所指，则n=B+1 (2)

度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此(2)式可写为n=2*n2+1 (3) 由(1)、(3)得n2=n0-1，代入(1)，并由(1)和(2)得B=2*(n0-1)。

5．证明任一结点个数为n的二叉树的高度至少为O(log2n)。 参考答案：

最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1

6．有n个结点并且其高度为n的二叉树的数目是多少? 参考答案：2n-1

7．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 参考答案：235。

8．高度为10的二叉树，其结点最多可能为多少？ 参考答案：1023。

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 C E G D F I

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

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??

三、算法设计题

1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。 参考答案：

以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值，最后就可以根据根结点的运算符的要求，计算出表达式的最后结果。 typedef struct node

{ElemType data; float val;

char optr; //只取‘+’， ‘-’， ‘*’，‘/’ struct node *lchild，*rchild }BiNode,*BiTree;

float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值 {float lv,rv; if(bt!=null)

{lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch(bt->optr)

{case ‘+’: value=lv+rv; break; case ‘-’: value=lv-rv;break; case ‘*’: value=lv*rv;break; case ‘/’: value=lv/rv; } } return(value); }

2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 参考答案：

本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。

int Precede(char optr1, char optr2)

// 比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回-1 {switch(optr1)

{case‘+’:case‘-’:if(optr2==‘+’||optr2==‘-’)return(0);else return(-1); case‘*’:case‘/’:if(optr1==‘*’||optr2==‘/’)return(0);else return(1);

} }

void InorderExp (BiTree bt)

//输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名 {int bracket; if(bt)

{if(bt->lchild!=null)

{bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左子女运算符优先级

if(bracket==1) printf(‘(’);

InorderExp(bt->lchild); //输出左子女表示的算术表达式 if(bracket==1)printf(‘)’); //加上右括号 }

printf(bt->data); //输出根结点

if(bt->rchild!=null) //输出右子树表示的算术表达式 {bracket=Precede(bt->data,bt->rchild->data)

if (bracket==1)printf(“(”); //右子女级别低，加括号 InorderExp (bt->rchild); if(bracket==1)printf(“)”); } }

}//结束Inorder Exp

3．要求二叉树按二叉链表形式存储，(1)写一个建立二叉树的算法；(2)写一个判别给定的二叉树是否是完全二叉树的算法。 参考答案： (1)

BiTree Creat() //建立二叉树的二叉链表形式的存储结构

{ElemType x;BiTree bt;

scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0)

{bt=(BiNode *)malloc(sizeof(BiNode));

bt->data=x; bt->lchild=creat(); bt->rchild=creat(); }

else error(“输入错误”)； return(bt); }//结束 BiTree

(2)int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0

{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1);

QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q))

{ p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队

else {if (p->lchild) return 0; //前边已有结点为空，本结点不空

else tag=1; } //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0;

else tag=1; } //while return 1;

} //JudgeComplete

4．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 参考答案：

方法一：BiTree Creat(ElemType A[],int i)

//n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树 {BiTree tree;

if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];

if(2*i>n) tree->lchild=null;else tree->lchild=Creat(A,2*i);

if(2*i+1>n) tree->rchild=null;else tree->rchild=Creat(A,2*i+1); }

return (tree); }//Creat 初始调用时i=1。

5．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注：树中结点数已知。 参考答案：

由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。

int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材 {int maxdepth=0; for(i=1;i<=t.n;i++) {temp=0; f=i;

while(f>0) {temp++; f=t.nodes[f].parent; } // 深度加1,并取新的双亲

if(temp>maxdepth) maxdepth=temp; //最大深度更新 }

return(maxdepth);//返回树的深度 } //结束Depth 6．二叉树采用二叉链表存储：(1)编写计算整个二叉树高度的算法；(2)编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 参考答案： (1)

int Height(BiTree bt)//求二叉树bt的深度 {

int hl,hr;

if (bt==null) return(0); else {

hl=Height(bt->lch); hr=Height(bt->rch); if(hl>hr) return (hl+1); else return(hr+1); } }

(2)求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。

int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else

{ BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大

front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)

{p=Q[front++]; temp++; //同层元素数加1

if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队

if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear;

if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度

temp=0;

}//if }//while

return (maxw); }//结束width

7．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。 参考答案：

二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。 void Ancestor(ElemType A[],int n,int i,int j)

//二叉树顺序存储在数组A[1..n]中，本算法求下标分别为i和j的结点的最近公共祖先结点的值。 {while(i!=j)

if(i>j) i=i/2; //下标为i的结点的双亲结点的下标 else j=j/2; //下标为j的结点的双亲结点的下标

printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,A[i]);//设元素类型整型。 }// Ancestor

8．在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度（若不加分析，直接写出结果，按零分算）。 参考答案：

后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。 void Search(BiTree bt,ElemType x) //在二叉树bt中，查找值为x的结点，并打印其所有祖先 {typedef struct

{BiTree t; int tag; }stack;//tag=0表示左子女被访问，tag=1表示右子女被访问 stack s[]; //栈容量足够大 top=0;

while(bt!=null||top>0)

{while(bt!=null && bt->data!=x) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下 if(bt->data==x)

{ printf(“所查结点的所有祖先结点的值为:\\n”); //找到x for(i=1;i<=top;i++) printf(s[i].t->data);

return;

} //if输出祖先值后结束

本文来源：https://www.bwwdw.com/article/buwo.html