第4课 树和二叉树

参考答案：

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

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