第6章 - 数据结构习题题目及答案 - 树和二叉树 - 参考答案

一、基础知识题

6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。

【解答】 设度为m的树中度为0,1,2,?,m的结点数分别为n0, n1, n2,?, nm，结点总数为n，分枝数为B，则下面二式成立 n= n0+n1+n2+?+nm (1) n=B+1= n1+2n2 +?+mnm+1 (2)

由(1)和(2)得叶子结点数n0=1+

即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8

6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。

【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1

由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.

注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，??。虽然解法也对，但步骤多且复杂，极易出错。

6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。

【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。

6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。

【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。 若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。

6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。

【解答】由公式n=2n0+n1-1，得该二叉树的总结点数是69。

6.6 求一棵具有1025个结点的二叉树的高h。

【解答】该二叉树最高为1025（只有一个叶子结点），最低高为11。因为210-1<1025<211-1，故1025个结点的二叉树最低高为11。

6.7 一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有多少结点。

【解答】第一层只一个根结点，其余各层都两个结点，这棵二叉树最少结点数是2h-1。

6.8将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是多少。

【解答】设含n个结点的完全三叉树的高度为h，则有

<2n<

本题n=244, 故h=6。

6.9 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右

孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，是采用何种次序的遍历实现编号的。

【解答】后序遍历二叉树，因为后序遍历顺序为左子树-右子树-根结点。

6.10 高度为h(h>0)的满二叉树对应的森林由多少棵树构成。

【解答】因为在二叉树转换为森林时，二叉树的根结点，根结点的右子女，右子女的右子女，??，都是树的根，所以，高度为h(h>0)的满二叉树对应的森林由h棵树构成。

6.11 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括几棵树？

【解答】3棵树。（本题不需画出完整的二叉树，更不需要画出森林，只需画出二叉树的右子树就可求解。如上题所述，二叉树的根结点，根结点的右子女，右子女的右子女，??，在二叉树转为森林时，都是树的根。）

6.12 对任意一棵树，设它有n个结点，这n个结点的度数之和为多少？ 【解答】n-1。度数其实就是分支个数。根结点无分支所指，其余结点有且只有一个分支所指。

6.13 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是多少？ 【解答】对二叉树线索化时，只有空链域才可加线索。一棵左子树为空的二叉树在先序线索化时，根结点的左链为空，应加上指向前驱的线索，但根结点无前驱，故该链域为空。同样分析知道最后遍历的结点的右链域为空。故一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是2个。

6.14 一棵左、右子树均不空的二叉树在先序线索化后，其中空的链域的个数是多少?

【解答】1个。

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

【解答】n+1。森林中任何一个非终端结点在转换成二叉树时，其第一个子女结点成为该非终端结点的左子女，其余子女结点成为刚生成的左子女结点的右子女，右子女结点的右子女，??，最右子女结点的右链域为空。照此分析，n个非终端结点在转换后，其子女结点中共有n个空链域。另外，森林中各棵树的根结点可以看做互为兄弟，转换成二叉树后也产生1个空链域。因此，本题的答案是n+1。

6.16 试分别找出满足以下条件的所有二叉树： (1) 二叉树的前序序列与中序序列相同； (2) 二叉树的中序序列与后序序列相同； (3) 二叉树的前序序列与后序序列相同； (4) 二叉树的前序序列与层次序列相同； (5) 二叉树的前序、中序与后序序列均相同。

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

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

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

若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。 若二叉树的前序、中序与后序序列均相同，则或为空树，或为只有根结点的二叉树。

6.17 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树，对二叉树进行中序线索化，并将该二叉树转换为森林。

【解答】

6.18 已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。

6.20有n个结点的k叉树（k≥2）用k叉链表表示时，有多少个空指针？ 【解答】k叉树（k≥2）用k叉链表表示时,每个结点有k个指针，除根结点没有指针指向外，其余每个结点都有一个指针指向，故空指针的个数为： nk-(n-1)=n(k-1)+1

6.21 一棵高度为h的满k叉树有如下性质：根结点所在层次为0；第h层上的结点都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问： (1)各层的结点个数是多少?

(2)编号为i的结点的双亲结点（若存在）的编号是多少? (3)编号为i的结点的第m个孩子结点（若存在）的编号是多少？ (4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？ 【解答】

(1)kl(l为层数，按题意，根结点为0层)

（2）因为该树每层上均有kl个结点，从根开始编号为1，则结点i的从右向左数第２个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2<=n<=ik+1成立，因i是整数，故结点i的双亲的编号为?(i-2)/k?+1。 (3) 结点i(i>1)的前一结点编号为i-1（其最右边子女编号是(i-1)*k+1），故结点 i的第 m个孩子的编号是(i-1)*k+1+m。

(4) 根据以上分析，结点i有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (i-1)%k!=0，其右兄弟编号是i+1。

6.22．证明任一结点个数为n(n>0) 的二叉树的高度至少为?(logn)?+1。 【解答】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1≦n≦2h-1关系式。解此不等式，并考虑h是整数，则有h=?logn?+1，即任一结点个数为n 的二叉树的高度至少为?(logn)?+1。

6.23 已知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。

6.24已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？

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

6.25求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结

点的下标。要求写出简要步骤。

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

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

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

6.27设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于4的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。

【解答】若前序序列是abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14 种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。例如：若取中序序列dcab就不能。 该14棵二叉树的形态及中序序列略。

6.28已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为：JFDBACEHXIK；后序序列为：ACBEDXIHFKJ。请给出该二叉树的中序序列，并画出相应的二叉树树形。

【解答】一般说来，仅仅知道二叉树的前序遍历序列和后序遍历序列并不能确定这棵二叉树，因为并不知道左子树和右子树两部分各有多少个结点。但本题有特殊性，即每个结点“要么其左、右子树皆为空，要么其左、右子树皆不空”。具体说，前序序列的第一个结点是二叉树的根，若该结点后再无其它结点，则二

叉树只有根结点；否则，该结点必有左右子树，且根结点后的第一个结点就是“左子树的根”。到后序序列中查找这个“左子树的根”，它将后序序列分成左右两部分：左部分(包括所查到的“左子树的根结点”)是二叉树的左子树(可能为空)，右部分(除去最后的根结点)则是右子树(可能为空)。这样，在确定根结点后，就可以将后序遍历序列（从而也将前序遍历序列）分成左子树和右子树两部分了。 本题中，先看前序遍历序列，第一个结点是J，所以J是二叉树的根，J后面还有结点，说明J有左、右子树，J后面的F必是左子树的根。到后序遍历序列中找到F,F将后序遍历序列分成两部分：左面ACBEDXIH，说明FACBEDXIH是根J的左子树；右面K(K的右面J已知是根)，说明K是根J的右子树。这样，问题就转化为“以前序序列FDBACEHXI和后序序列ACBEDXIHF去构造根J的左子树”，以及“以前序序列K和后序序列K去构造根J的右子树”了。如此构造下去，所构造的二叉树如下。易见，中序序列为ABCDEFXHIJK。

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

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

6.30 画出同时满足下列两条件的两棵不同的二叉树。 (1)按先根序遍历二叉树顺序为ABCDE。 (2)高度为5其对应的树（森林）的高度最大为4。 【解答】

6.31用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的结点访问序列。

【解答】后序遍历该二叉树的结点访问序列为：DECGHFBKJLIA

6.32一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。

先序序列为： C D E G H I K 中序序列为：C B F A _ J K I G 后序序列为： E F D B J I H A 【解答】

{int num=0; ∥记叶子结点数 for(i=0;i

{if(BT[2*i]==0 && 2*i+1<=n && BT[2*i+1]==0) num++;} ∥若结点无孩子，则是叶子

else if(BT[i]!=0) num++; ∥存储在数组后一半的元素是叶子结点 }

return num; }∥结束Leaves

6.43已知二叉树以一维数组作为存储结构。试编写算法求下标为i和j的两个结点的最近共同祖先结点的值。

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

void Ancestor(ElemType bt[],int n,i,j,)

∥求顺序存储在bt[1..n]的二叉树中下标为i和j的两个结点的最近公共祖先结点

{if(i<1 || j<1) {printf(“参数错误\\n”);exit(0);}; if(i==j)

{if(i==1) {printf(“所查结点为根结点，无祖先\\n”);exit(0);}; else {printf (“结点的最近公共祖先是%d，值是%d”,i/2,A[i/2]);exit(0)} } while(i!=j)

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

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

6.44已知一棵完全二叉树顺序存储于向量s[1..n]中，试编写算法由此顺序存储结构建立该二叉树的二叉链表。 【算法6.44】

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。

6.45编写算法判别给定二叉树是否为完全二叉树。

【题目分析】判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。具体说，在层次遍历时，若碰到一个空指针后，在遍历结束前又碰到结点，则结论为该二叉树不是完全二叉树。 【算法6.45】

int JudgeComplete(BiTree bt)

∥判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; ∥出现空指针时，置tag=1

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

[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。

6.46设树以双亲表示法存储，编写计算树的深度的算法。

【题目分析】以双亲表示法作树的存储结构，对每一结点，找其双亲，双亲的双亲，直至（根）结点,就可求出每一结点的层次，取其结点的最大层次就是树的深度。 【算法6.46】

int Depth(Ptree t)

∥求以双亲表示法为存储结构的树的深度 {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.47已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。

【题目分析】后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归遍历。栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（相等）的元素就是结点p 和q的最近公共祖先。 【算法6.47】

先设二叉树的结点结构为： typedef struct {BiTree t;

int tag; ∥tag=0表示结点的左子女已访问，tag=1为右子女已访问 }stack;

stack s[],s1[];∥栈，容量足够大

BiTree Ancestor(BiTree root, BiTree p, BiTree q, BiTree r) ∥求二叉树上结点p和q的最近的共同祖先结点r {

top=0; bt=root;

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

while(bt!=null && bt!=p && bt!=q) ∥结点入栈 {

s[++top].t=bt; s[top].tag=0; bt=bt->lchild; } ∥沿左分枝向下 if(bt==p)

∥不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {

for(i=1;i<=top;i++) s1[i]=s[i]; top1=top;

∥将栈s的元素转入辅助栈s1保存, top1记住栈顶 }

if(bt==q) ∥找到q 结点

for(i=top;i>0;i--) ∥将栈中元素的树结点到s1去匹配 {

pp=s[i].t;

for(j=top1;j>0;j--) if(s1[j].t==pp) {

printf(“共同的祖先已找到\\n”)； return (pp); }

｝

while(top!=0 && s[top].tag==1)

top--; ∥退栈 if(top!=0)｛

s[top].tag=1; bt=s[top].t->rchild; ｝∥沿右分枝向下遍历 }∥结束while(bt!=null ||top>0) return(null);∥ｑ、p无公共祖先 ｝∥结束Ancestor

6.48以二叉链表作为存储结构，设计按层次遍历二叉树的算法。 【算法6.48】

void Level(BiTree bt) ∥层次遍历二叉树 {if(bt)

{QueueInit(Q); ∥Q是以二叉树结点指针为元素的队列 QueueIn(Q,bt)；

while(!QueueEmpty(Q))

{p=QueueOut(Q); ∥出队 printf(p->data); ∥访问结点 if(p->lchild) QueueIn(Q,p->lchild); ∥非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); ∥非空右子女入队 } }∥if(bt) }

6.49编写算法查找二叉链表中数据域值为x的结点（假定各结点的数据域值各不相同），并打印出x所有祖先的数据域值。

【题目分析】后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。 【算法6.49】

void Search(BiTree bt,ElemType x)

∥在二叉树bt中，查找值为x的结点，并打印其所有祖先

{typedef struct {BiTree t;

int tag; ∥tag=0表示左子女被访问，tag=1右子女被访问 }stack;

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; } ∥输出祖先值后结束

while(top!=0 && s[top].tag==1) top--; ∥退栈（空遍历） if(top!=0)

{s[top].tag=1;bt=s[top].t->rchild;} ∥沿右分枝向下遍历 }∥ while(bt!=null||top>0) }结束search

6.50设计这样的二叉树，用它可以表示父子、夫妻和兄弟三种关系，并编写一个查找任意父亲结点的所有儿子结点的过程。

【题目分析】用二叉树表示出父子，夫妻和兄弟三种关系，可以用根结点表示父（祖先），根结点的左子女表示妻，妻的右子女表示子。这种二叉树可以看成类似树的孩子兄弟链表表示法；根结点是父，根无右子女，左子女表示妻，妻的右子女（右子女的右子女等）均可看成兄弟（即父的所有儿子），兄弟结点又成为新的父，其左子女是兄弟（父的儿子）妻，妻的右子女（右子女的右子女等）又为儿子的儿子等等。首先递归查找某父亲结点，若查找成功，则其左子女是妻，妻的右子女及右子女的右子女等均为父亲的儿子。 【算法6.50】

BiTree Search(BiTree t,ElemType father) ∥在二叉树上查找值为father的结点 {int tag=0;

if(t==null) p=null; ∥二叉树上无father结点 else if(t->data==father) {tag=1; p=t;}∥查找成功

else{p=Search(t->lchild,father); if(tag==0)p=Search(t->rchild,father);}

return p; }∥结束Search

void PrintSons(BiTree t,ElemType x) ∥在二叉树上查找结点值为x的所有的儿子

{p=Serach(t,x); ∥在二叉树t上查找父结点x if(p && p->lchild) ∥存在父结点,且有妻

{q=p->lchild; q=q->rchild; ∥先指向其妻结点，再找到第一个儿子 while(q!=null)

{printf(q->data); q=q->rchild;}∥输出父的所有儿子 }

}∥结束PrintSons

6.51 编写递归算法判定两棵二叉树是否相等。

【题目分析】首先判断二叉树的根是否相等，如是，再判断其左、右子树是否相等。 【算法6.51】

int BTEqual(BiTree t, BiTree x) {∥判定二叉树t和二叉树x是否相等 if(!t && !x) return true;

if(t && x && t->data==x->data && BTEqual(t->lchild,x->lchild) && BTEqual(t->rchild,x->rchild) return ture;

else return false; }

6.52已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储，编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。

【题目分析】二叉树中最大序号的叶子结点,是在顺序存储方式下编号最大的结点

【算法6.52】

void Ancesstor(ElemType bt[]) ∥打印最大序号叶子结点的全部祖先 {c=m; ∥m=2K-1

while(bt[c]==0) c--;∥找最大序号叶子结点,该结点存储时在最后 f=c/2; ∥c的双亲结点f

while(f!=0) ∥从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点 {printf(bt[f]); f=f/2; }∥逆序输出，最老的祖先最后输出 }∥结束

6.53设二叉树以二叉链表作为存储结构，编写算法对二叉树进行非递归的中序遍历。 【算法6.53】

void InOrder(BiTree bt) ∥对二叉树进行非递归中序遍历

{BiTree s[],p=bt; ∥s是元素为二叉树结点指针的栈，容量足够大 int top=0; while(p || top>0)

{while(p) {s[++top]=p; bt=p->lchild;} ∥沿左子树向下

if(top>0)

{p=s[top--]; printf(p->data); p=p->rchild;} ∥退栈，访问，转右子树

} }∥结束

6.54设T是一棵满二叉树，写一个把T的后序遍历序列转换为先序遍历序列的递归算法。

【题目分析】对一般二叉树，仅根据一个先序（或中序、或后序）遍历，不能确定另一个遍历序列。但由于满二叉树“任一结点的左右子树均含有数量相等的结点”，根据此性质，可将任一遍历序列转为另一遍历序列。 【算法6.54】

void PostToPre(ElemType post[],pre[],int l1,h1,l2,h2)

∥将满二叉树的后序序列转为先序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)

{pre[l2]=post[h1]; ∥根结点 visit(pre[l2]); ∥访问根结点 half=(h1-l1)/2; ∥左或右子树的结点数 PostToPre(post,pre,l1,l1+half-1,l2+1,l2+half) ∥将左子树后序序列转为先序序列

PostToPre(post,pre,l1+half,h1-1,l2+half+1,h2) ∥将右子树后序序列转为先序序列 }

}∥ PostToPre t

6.55若二叉树BT的每个结点，其左、右子树都为空，或者其左、右子树都不空，这种二叉树有时称为“严格二叉树”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。写出根据这种二叉树的前序序列和后序序列确定该二叉树的递归算法。

【问题分析】前序序列的第一个结点是二叉树的根，若该结点后再无其它结点，则该结点是叶子；否则，该结点必有左、右子树，且根结点后的第一个结点就是

左子树的根。到后序序列中查找这个左子树的根，它将后序序列分成左、右两部分：左部分(包括所查到的结点)是二叉树的左子树(可能为空)，右部分(除去最后的根结点)则是右子树(可能为空)。这样，在确定根结点后，可递归确定左、右子树。 【算法6.55】

void creat(BiTree *BT,char pre[n],char post[n],int l1,int h1,int l2,int h2)

∥由严格二叉树的前序序列pre(l1:h1)和后序序列post(l2:h2)建立二叉树 { BiTree p=*BT; if(l1<=h1)

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

p->data=pre[l1];∥前序序列的第一个元素是根 if(l1==h1) {p->lchild=p->rchild=null; }∥叶子结点 else ∥分支结点

{for(int i=l2;i<=h2;i++) ∥到后序序列中查左子树的根 if(post[i]==pre[l1+1] break;

L=i-l2+1; ∥左子树结点数

creat(&(p->lchild), pre,post,l1+1,l1+L,l2,i); creat(&(p->rchild), pre,post,l1+L+1,h1,i+1,h2-1); }∥else }∥if }∥结束

6.56编写一个递归算法，利用叶结点中空的右链指针域rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址（链头）。

【题目分析】叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 【算法6.56】

LinkedList head,pre=null; ∥全局变量 LinkedList InOrder(BiTree bt)

∥中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); ∥中序遍历左子树 if(bt->lchild==null && bt->rchild==null)∥叶子结点

{if(pre==null) {head=bt; pre=bt;} ∥处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } ∥将叶子结点链入链表 }

InOrder(bt->rchild); ∥中序遍历右子树 }

pre->rchild=null; ∥设置链表尾 return(head); } ∥InOrder

6.57已知有一棵二叉链表表示的二叉树，编写算法，输出从根结点到叶子结点的最长一枝上的所有结点。

【题目分析】后序遍历时栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针大于已保存的最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 【算法6.57】

void LongestPath(BiTree bt)

∥求二叉树从根结点到叶子结点的最长一枝上的所有结点 {BiTree p=bt,l[],s[];

∥l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag[],longest=0; while(p || top>0)

{while(p){s[++top]=p；tag[top]=0; p=p->lchild;}∥沿左分枝向下 if(tag[top]==1) ∥当前结点的右分枝已遍

历

{if(!s[top]->lchild && !s[top]->rchild) ∥只有到叶子结点时，才查看路径长度 if(top>longest)

{for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--; }

}∥保留当前最长路径到l栈，记住最高栈顶指针，退栈 while(top>0 && tag[top]==1) top--; ∥退栈 if(top>0)

{tag[top]=1; p=s[top].rchild;} ∥沿右子分枝向下 }∥while(p!=null||top>0) }∥结束LongestPath

6.58试编写一算法对二叉树进行前序线索化。

【题目分析】线索化是在遍历中完成的，因此，对于二叉树进行前序、中序、后序遍历，在“访问根结点”处进行加线索的改造，就可实现前序，中序和后序的线索化。 【算法6.58】

BiThrTree pre=null;∥设置前驱 void PreOrderThreat(BiThrTree BT)

∥对以线索链表为存储结构的二叉树BT进行前序线索化 {if(BT!=null)

{if(BT->lchild==null){BT->ltag=1; BT->lchild=pre;}∥设置左线索 if(pre!=null && pre->rtag==1) pre->rchild=BT; ∥设置前驱的右线索； if(BT->rchild==null) BT->rtag=1; ∥为建立右链作准备 pre=BT; ∥前驱后移

if(BT->ltag==0) PreOrderThreat(BT->lchild); ∥左子树前序线索化

PreOrderThreat(BT->rchild); ∥右子树前序线索化 }∥if(BT!=null) }∥结束PreOrderThreat

6.59试编写一算法对二叉树进行中序线索化。 【算法6.59】 BiThrTree pre==null;

void InOrderThreat(BiThrTree T)∥对二叉树进行中序线索化 {if(T)

{InOrderThreat(T->lchild); ∥左子树中序线索化 if(T->lchild==null){T->ltag=1; T->lchild=pre;} ∥左线索为pre if(pre!=null && pre->rtag==1) pre->rchild=T;} ∥给前驱加后继线索 if(T->rchild==null) T->rtag=1; ∥置右标记，为右线索作准备

pre=BT; ∥前驱指针后移 InOrderThreat(T->rchild); ∥右子树中序线索化 }∥if

}∥结束InOrderThreat

6.60设p指向前序线索二叉树t的某结点，编写算法求*p结点的后继结点。 【题目分析】在前序线索二叉树中，求*p结点的后继结点，若*p结点有左子女，则左子女是其后继结点；若*p结点无左子女而有右子女，则右子女是其后继；若*p结点无左、右子女，线索p->rchild指向其后继。 【算法6.60】

BiThrTree PreorderNext(BiThrTree p) {if (p->ltag==0) // 结点有左子女

return(p->lchild); //结点的左子女为其前序后继 else

return(p->rchild);//p->rchild为其前序后继 } // PreorderNext

6.61设p指向后序线索二叉树t的某结点，编写算法求*p结点的前驱结点。 【题目分析】在后序线索二叉树中，求*p结点的前驱结点，若*p结点有右子女，则右子女是其前驱结点；若*p结点无右子女而有左子女，则左子女是其前驱；若*p结点既无右子女又无左子女，线索p->lchild指向其前驱。 【算法6.61】

BiThrTree PostorderPre(BiThrTree p) { if (p->rtag==0) // 结点有右子女

return(p->rchild); //结点的右子女为其后序前驱 else

return(p->lchild) ;//p->lchild为其后序前驱 } // PreorderPre

6.62设计算法求中序线索二叉树中指针P所指结点的前驱结点的指针。 【题目分析】中序线索二叉树中，指针P所指结点的前驱结点的特征是：若p->ltag=1,p->lchild指向其前驱，否则，P的左子树上按中序遍历的最后结点是其中序前驱。 【算法6.62】

BiThrTree InPre(BiThrTree T, BiThrTree p) ∥在中序线索树T中，查找给定结点p的中序前驱

{if（p->ltag==1）q=p->lchild; ∥若p的左标志为1，用其左指针指向前驱 else {q=p->lchild; while(q->rtag==0)

q=q->rchild; ∥p的前驱为其左子树中最右下的结点 }

return (q); }∥结束InPre

6.63设计算法求中序线索二叉树中指针P所指结点的后继结点的指针。

【题目分析】中序线索二叉树中，指针P所指结点的后继结点的特征是：若p->rtag=1,p->rchild指向其后继，否则，P的右子树上按中序遍历的第一个结点是其中序后继。 【算法6.63】

BiThrTree InSucc(BiThrTree T, BiThrTree p) ∥在中序线索二叉树T中，查找给定结点p的中序后继 {if（p->rtag==1）

q=p->rchild; ∥若p的右标志为1，用其右指针指向后继 else {q=p->rchild; while(q->ltag==0)

q=q->lchild; ∥p的后继为其右子树中最左下的结点 }

return (q); }∥结束InSucc

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