文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

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->Lc;} //沿左分枝向下

if(tag[top]==1) //当前结点的右分枝已遍历

{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}

//保留当前最长路径到l栈，记住最高栈顶指针，退栈 }

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

61.[题目分析]在线索二叉树上插入结点,破坏了与被插入结点的线索。因此,插入结点时,必须修复线索。在结点y的右侧插入结点x，因为是后序线索树，要区分结点y有无左子树的情况。

void TreeInsert(BiTree t,y,x)//在二叉树t的结点y的右侧，插入结点x {if(y->ltag==0) //y有左子女

{p=y->lchild; if (p->rtag==1) p->rchild=x; //x是y的左子女的后序后继 x->ltag=1; x->lchild=p; //x的左线索是y的左子女 }

else //y无左子女

{x->ltag=1; x->lchild=y->lchild;//y的左线索成为x的左线索 if(y->lchild->rtag==1) //若y的后序前驱的右标记为1 y->lchild->rchild=x; //则将y的后序前驱的后继改为x }

x->rtag=1; x->rchild=y; y->rtag=0; y->rchild=x; //x作y的右子树 }//结束 TreeInsert

62.[题目分析]在中序全线索化T树的P结点上，插入以X为根的中序全线索化二叉树，要对X有无左右子树进行讨论，并修改X左(右)子树上最左结点和最右结点的线索。在中序线索树上查找某结点p的前驱的规律是：若p->ltag=1，则p->lchild就指向前驱，否则，其前驱是p的左子树上按中序遍历的最后一个结点；查找某结点p的后继的规律是：若p->rtag=1，则p->rchild就指向后继，否则，其后继是p的右子树上按中序遍历的第一个结点。

int TreeThrInsert(BiThrTree T,P,X) //在中序全线索二叉树T的结点P上，插入以X为根的中序全线索二叉树，返回插入结果信息。

{if(P->ltag==0 && P->rtag==0) {printf(“P有左右子女，插入失败\\n”)； return(0); }

if(P->ltag==0) //P有左子女，将X插为P的右子女

{if(X->ltag==1) X->lchild=P; //若X无左子树， X的左线索(前驱)是P

36文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

else //寻找X的左子树上最左（下）边的结点 {q=X->lchild;

while(q->ltag==0) q=q->lchild; q->lchild=P; }

if(X->rtag==1) //修改X的右线索

X->rchild=P->rchild; //将P的右线索改为X的右线索 else //找X右子树最右面的结点

{q=X->rchild; while(q->rtag==0) q=q->rchild; q->rchild=P->rchild; }

P->rtag=0;P->rchild=X; //将X作为P的右子树 } //结束将X插入为P的右子树

else //P有右子女，将X插入为P的左子女 {if(X->ltag==1) //X无左子女

X->lchild=P->lchild; //将P的左线索改为X的左线索 else //X有左子女，找X左子树上最左边的结点 {q=X->lchild;

while(q->ltag==0) q=q->lchild; q->lchild=P->lchild; }

if(X->rtag==1) X->rchild=P; //若X无右子树，则X的右线索是P

else //X有右子树，查其右子树中最右边的结点，将该结点的后继修改为P {q=X->rchild;

while(q->rtag==0) q=q->rchild; q->rchild=P; }

P->ltag=0; //最后将P的左标记置0 P->lchild=X; //P的左子女链接到X } //结束将X插入为P的左子女 } //结束Tree Thrfnsert

63.[题目分析]在中序线索树中，非递归查找数据域为A的结点（设该结点存在，其指针为P）并将数据域为x的Q结点插入到左子树中。若P无左子女，则Q成为P的左子女,原P的左线索成为Q的左线索，Q的右线索为P；若P有左子树，设P左子树中最右结点的右线索是结点Q，结点Q的右线索是P。

void InThrInsert(BiThrTree T,Q; ElemType A)

//在中序线索二叉树T中,查找其数据域为A的结点，并在该结点的左子树上插入结点Q

{BiThrTree P=T;

while(P)

{while(P->LT==0 && P->data!=A) P=P->LL; //沿左子树向下 if (P->data==A) break; //找到数据域为A的结点,退出循环

while(P->RT==1) P=P->RL; //还没找到数据域为A的结点沿右线索找后继 P=P->RL; //沿右子树向下

37文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

}

if(P->LT==1) //P没有左子树，Q结点插入作P的左子女 {Q->LL=P->LL; Q->LT=1； //将P的左线索作为Q的左线索 }

else //P有左子树，应修改P的左子树最右结点的线索 {Q->LL=P->LL;Q->LT=0; //Q成为P的左子女 s=Q->LL; //s指向原P的左子女

while(s->RT==0) s=s->RL; //查找P的左子树最右边的结点

s->RL=Q; //原P左子树上最右结点的右线索是新插入结点Q }

P->LT=0;P->LL=Q; //修改P的标记和指针

Q->RT=1;Q->RL=P; //将Q链为P的左子女,其中序后继是P; }//结束InThrInsert 64.[题目分析] “双链”就利用二叉树结点的左右指针，重新定义左指针为指向前驱的指针，右指针是指向后继的指针，链表在遍历中建立，下面采用中序遍历二叉树。

BiTree head=null,pre; //全局变量链表头指针head,pre

void CreatLeafList(BiTree bt) //将BiTree 树中所有叶子结点链成带头结点的双链表，

{if（bt） //若bt不空

{CreatLeafList（bt->lchild）; //中序遍历左子树 if(bt->lchild==null && bt->rchild==null) //叶子结点 if(head==null)//第一个叶子结点

{head=(BiTree)malloc(sizeof(BiNode)); //生成头结点

head->lchild=null; head->rchild=bt; //头结点的左链为空,右链指向第一个叶子结点

bt->lchild=head; pre=bt; //第一个叶子结点左链指向头结点，pre指向当

前叶子结点

}

else //已不是第一个叶子结点

{pre->rchild=bt; bt->lchild=pre; pre=bt;} //当前叶子结点链入双链表 CreatLeafList(bt->rchild); //中序遍历右子树

pre->rchild=null; //最后一个叶子结点的右链置空（链表结束标记） }//if(bt) }//结束CreatLeafList;

65.[题目分析]求中序全线索树任意结点p的前序后继，其规则如下：若p有左子女，则左

子女就是其前序后继；若p无左子女而有右子女，则p的右子女就是p的前序后继；若p无左右子女，这时沿p的右线索往上，直到p的右标志为0（非线索），这时若p的右子女为空，则表示这是中序遍历最后一个结点，故指定结点无前序后继，否则，该结点就是指定结点的前序后继。程序段如下：

if(p->ltag==0 && p->lchild!=null) return(p->lchild); //p的左子女是p的前序后继

else if(p->rtag==0) && p->rchild!=null) return(p->rchild);//p右子女是其前序后继

else //p无左右子女，应沿右线索向上（找其前序后继），直到某结点右标记为0

38文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

{while (p->rtag==1) p=p->rchild;

if (p->rchild) return(p->rchild);else return(null); }//指定结点的前序

后继

[算法讨论]请注意题目“中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空”的说明。若无这一说明，只要结点的左标记为0，其左子女就是其前序后继。最后，当p无子女，沿右线索向上找其前序后继时，若最后结点的右标志为０，但对应指针为空，p也无前序后继。

66.[题目分析] 不借助辅助堆栈实现中序遍历，必须解决如何查找后继的问题。使用线索树就行。为此，将结点结构修改为(ltag,lchild,data,rchild,rtag)。各字段的含义在上面已多次使用，不再介绍。设二叉树已中序线索化。下面首先编写一查中序后继的函数，接着是中序遍历的非递归算法。

BiTree After(BiThrTree t) //查中序线索二叉树上结点t的后继 {if (t->rtag==1) return(t->rchild); p=t->rchild;

while(p->ltag==0) p=p->lchild; //p右子树中最左下的结点是p的中序后继 return(p); } //if

void InOrder(BiThrTree bt)

//非递归中序遍历带头结点的中序线索二叉树bt {p=bt->lchild; //p指向原二叉树的根结点 if (p!=bt) //二叉树非空

{while (p->ltag==0) p=p->lchild; //找中序遍历的第一个结点 while (p!=bt) //没回到头结点，就一直找后继并遍历 {visit(*p); p=After(p); } }//if }结束算法InOrder

67.[题目分析]在中序穿线树中找结点的双亲，最简单情况是顺线索就可找到。例如，结点的左子女的右线索和右子女的左线索都指向双亲。但对于有左右子女的结点来说，则要利用中序穿线树中线索“向上”指向祖先的特点：若结点p是结点q右子树中中序遍历最左下的结点，p的左线索指向q；若结点p是结点q左子树上中序遍历最右下的结点，p的右线索指向是q。反过来，通过祖先找子女就容易了。另外，若结点q的后继是中序穿线树的头结点，则应特殊考虑。

void FFA(BiThrTree t,p,q)//在中序穿线树t上，求结点p的双亲结点q {q=p; //暂存

while(q->RTAG==0) q=q->RLINK; //找p的中序最右下的结点

q=q->RLINK; //顺右线索找到q的后继（p的祖先结点） if (q==t) q=t->LLINK; //若后继是头结点，则转到根结点 if (q==p) {printf(“根结点无双亲\\n”)；return; }

if (q->LLINK==p) return(q); else q=q->LLINK; //准备到左子树中找p

while (q->RLINK!=p) q=q->RLINK；return(q); } //找最右结点的过程中回找到p }//结束FFA

[算法讨论]本题也可以先求结点p最左下结点的前驱线索，请读者自己写出算法。 68.[题目分析]带头结点的中序线索树，其头结点的lchild指向二叉树的根结点，头结点的rchild域指向中序遍历的最后一个结点。而二叉树按中序遍历的第一个结点的lchild和最后一个结点的rchild指向头结点。故从头结点找到根结点后，顺“后继”访问二叉树。在中序线索树中，找前序的后继，已在第65题进行了详细的讨论，这里不再赘述。中序线索

39文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

树在上面的“四、应用题”已画过多个，这里也不重复。

void PreorderInThreat(BiTrhTree tbt)

//前序遍历一中序全线索二叉树tbt，tbt是头结点指针 {bt=tbt->lchild; while(bt)

{while(bt->ltag==0){printf(bt->data); bt=bt->lchild;}//沿左分枝向下 printf(bt->data); //遍历其左标志为1的结点，准备右转

while(bt->rtag==1 && bt->rchild!=tbt) bt=bt->rchild;//沿右链向上 if (bt->rchild!=tbt) bt=bt->rchild;//沿右分枝向下 }

}//结束PreorderInThreat 时间复杂度O(n)。

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

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 70. 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); //右子树中序线索化 } }//结束InOrderThreat

71. void InOrderThreat(BiThrTree thrt)

//thrt是指向中序全线索化头结点的指针，本算法中序遍历该二叉树

{p=thrt->lchild; //p指向二叉树的根结点，当二叉树为空时，p指向thrt whild(p!=thrt)

{while（p->ltag==0) p=p->lchild;//沿左子女向下

visit(*p);//访问左子树为空的结点 while(p->rtag==1 && p->rchild!=thrt){p=p->rchild;visit(*p);}//沿右线索访问后继结点

40文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.