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

．BiThrTree InSucc(BiThrTree Tp) //在对称序穿线树T中查找给定结点p的中序后继

{if（p>rtag==）q=p>rchild; //若p的右标志为用其右指针指向后继

else {q=p>rchild; while(q>ltag==) q=q>lchild; }//p的后继为其右子树中最左下的结点

return (q);

}//结束InSucc

．[题目分析]在后序序列中若结点p有右子女则右子女是其前驱若无右子女而有左子女则左子女是其前驱若结点p左右子女均无设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点）若f有左子女则其左子女是结点p在后序下的前驱若f无左子女则顺其前驱找双亲的双亲一直继续到双亲有左子女（这时左子女是p的前驱）还有一种情况若p是中序遍历的第一个结点结点p在中序和后序下均无前驱

BiThrTree InPostPre (BiThrTree tp)

//在中序线索二叉树t中求指定结点p在后序下的前驱结点q

{BiThrTree q;

if (p>rtag==) q=p>rchild; //若p有右子女则右子女是其后序前驱

else if (p>ltag==) q=p>lchild; //若p无右子女而有左子女左子女是其后序前驱

else if(p>lchild==null) q=null;//p是中序序列第一结点无后序前驱

else //顺左线索向上找p的祖先若存在再找祖先的左子女

{while(p>ltag== && p>lchild!=null) p=p>lchild;

if(p>ltag==) q=p>lchild; //p结点的祖先的左子女是其后序前驱

else q=null; //仅右单枝树（p是叶子）已上到根结点p结点无后序前驱

}

return(q); }//结束InPostPre

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