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

．BiThrTree InOrder(BiThrTree TElemType x)

//先在带头结点的中序线索二叉树T中查找给定值为x的结点假定值为x的结点存在

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

while(p!=T)

{while(p>ltag== && pdata!=x) p=p>lc;

if(p>data==x)return(p);

while(p>rtag== && p>rc!=T) {p=p>rc; if(p>data== x) return(p);}

p=p>rc; }

}//结束InOrder

BiThrTree AfterXNode(BiThrTree T)//在中序线索二叉树T中求给定值为 x的结点的后继结点

{BiThrTree p=InOrde(Tx); //首先在T 树上查找给定值为x 的结点由p指向

if(p>rtag==) return(p>rc); //若p 的左标志为则p的rc指针指向其后继

else {q=p>rc; while(q>ltag==)q=q>lc; return(q); }

//结点p的右子树中最左面的结点是结点p的中序后继

} }//结束AfterXnode

．[题目分析]后序遍历是左右根因此若结点有右子女则右子女是其后序前驱否则左子女（或左线索）指向其后序前驱

BiThrTree PostSucc (BiThrTree Tp)//在后序线索二叉树T中查找指定结点p的直接前驱q

{if(p>Rtag==) q=p>Rchild;//若p有右子女则右子女为其前驱

else q=p>Lchild; //若p无右子女左子女或左线索就是p的后序前驱

return (q);

}//结束PostSucc

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