数据结构考研分类复习真题 第六章 答案 (五)[42]

[题目分析]求中序全线索树任意结点p的前序后继其规则如下若p有左子女则左子女就是其前序后继若p无左子女而有右子女则p的右子女就是p的前序后继若p无左右子女这时沿p的右线索往上直到p的右标志为（非线索）这时若p的右子女为空则表示这是中序遍历最后一个结点故指定结点无前序后继否则该结点就是指定结点的前序后继程序段如下

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

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

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

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

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

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

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

BiTree After(BiThrTree t) //查中序线索二叉树上结点t的后继

{if (t>rtag==) return(t>rchild);

p=t>rchild;

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

return(p); } //if

void InOrder(BiThrTree bt)

//非递归中序遍历带头结点的中序线索二叉树bt

{p=bt>lchild; //p指向原二叉树的根结点

if (p!=bt) //二叉树非空

{while (p>ltag==) p=p>lchild; //找中序遍历的第一个结点

while (p!=bt) //没回到头结点就一直找后继并遍历

{visit(*p); p=After(p); }

}//if }结束算法InOrder

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []