x->rchild= _____________; if (x->lchild!=NULL) && (x->lchild->rtag==1) x->lchild->rchild=_____________; 【答案】（1）1 （2）y->lchild （3）0 （4）x （5）1 （6）y （7）x

6.3 判断题

1．二叉树是度为2的有序树（ ） 【答案】×

2．完全二叉树一定存在度为1的结点（ ） 【答案】×

3．深度为K的二叉树中结点总数≤2k-1（ ） 【答案】√

4．由一棵二叉树的先序序列和后序序列可以惟一确定它（ ） 【答案】×

5．完全二叉树中，若一个结点没有左孩子，则它必是树叶（ ） 【答案】√

6．用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（ ） 【答案】√

7．完全二叉树的存储结构通常采用顺序存储结构（ ） 【答案】√

8．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（ ） 【答案】√

9．在中序线索二叉树中，每一非空的线索均指向其祖先结点（ ） 【答案】√

【解析】在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。

10．二叉树中序线索化后，不存在空指针域（ ） 【答案】×

【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

6.4 应用题

1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。

2．若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作： （1）寻找某个结点双亲 ； （2）寻找某个结点的子女； 请问应该用何种结构来存储该二叉树？

【答案】用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是?i/2?(i=1时无双亲)，其左子女是2i(若2i≤n，否则i无左子女)，右子女是2i+1(若2i+1≤n，否则无右子女)。

3．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。

33

【答案】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是?n/2?，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是?n/2?+1。

4．试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如先序abc，后序bca，中序bac。

【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。

5．试找出满足下列条件的二叉树：

1）先序序列与后序序列相同； 2）中序序列与后序序列相同； 3）先序序列与中序序列相同； 4）中序序列与层次序列相同；

【答案】先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根”，根据以上原则，解答如下：

1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

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

6．已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA （1）给出这棵二叉树；（2）转换为对应的森林。

7．一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。

【答案】先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使先序序列与后序序列相反，图示如下：

8．假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。

【答案】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。

9．已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK

【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，

34

再构造出森林。

10．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A 【答案】

11．设有正文AADBAACACCDACACAAD，字符集为A，B，C，D，设计一套二进制编码，使得上述正文的编码最短。【答案】字符A，B，C，D出现的次数为9，1，5，3。其哈夫曼编码如下：A:1，B:000，C:01，D:001 。

12．已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

6.5 算法设计题

35

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

二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲…等等，直至找到最近的公共祖先。 【算法源代码】

typedef int ElemType;

void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j)

if(i>j) i=i/2; /*下标为i的结点的双亲结点的下标*/ else j=j/2; /*下标为j的结点的双亲结点的下标*/ printf(\所查结点的最近公共祖先的下标是%d,值是%d\ }/* Ancestor*/

2．编程求以孩子兄弟表示法存储的森林的叶子结点数，要求描述结构。 【算法分析】

当森林（树）以孩子兄弟表示法存储时，若结点没有左子树（fch=NULL），则它必是叶子，否则，总的叶子结点个数是左子树（fch）上的叶子数和右子树（nsib）上叶结点个数之和。 【算法源代码】

typedef struct node{ ElemType data; /*数据域*/ struct node *fch, *nsib; /*孩子与兄弟域 */ }*Tree;

int Leaves (Tree t){/*计算以孩子-兄弟表示法存储的森林的叶子数*/ if(t)

if(t->fch==NULL) /*若结点无孩子，则该结点必是叶子*/ return(1+Leaves(t->nsib)); else

return (Leaves(t->fch)+Leaves(t->nsib)); }/*结束Leaves*/

3．假定用两个一维数组L[N]和R[N]作为有N个结点1，2,…， N的二叉树的存储结构。L[i]和R[i]分别指示结点 i的左子女和右子女；L[i]=0（R[i]=0）表示i的左（右）子女为空。设计一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。 【算法分析】

由指示结点i 左子女和右子女的两个一维数组L[i]和R[i]，很容易建立指示结点i 的双亲的一维数组T[i]，根据T数组，判断结点U是否是结点V后代的算法，转为判断结点V是否是结点U的祖先的问题。 【算法源代码】

int generation (int u, int v, int n, int l[],int r[],int t[]){

/*l[]和r[]是含有n个元素且指示二叉树结点i左子女和右子女的一维数组本算法据此建立结点i的双亲数组t，并判断结点u是否是结点v的后代*/ int parent,i;

for(i=1;i<=n;i++) t[i]=0; /*t数组初始化*/ for (i=1;i<=n;i++){ /*根据l和r填写t*/

if(l[i]!=0) t[l[i]]=i; /*若结点i的左子女是l，则结点l的双亲是结点i*/ if (r[i]!=0) t[r[i]]=i; /*i的右子女是r，则r的双亲是i*/ parent=u; /*判断u是否是v的后代*/ while (parent!=v && parent!=0) parent=t[parent]; if (parent==v)

{printf(\结点u是结点v的后代\ else

{ printf(\结点u不是结点v 的后代\ }

}/*结束generation*/

4．要求二叉树按二叉链表形式存储： （1）写一个建立二叉树的算法。

（2）写一个判别给定的二叉树是否是完全二叉树的算法。 【算法分析】

二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完

36