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

．[题目分析]在中序穿线二叉树中求某结点p的后序后继q需要知道p的双亲结点f的信息（中序线索树的性质若p是f的左子女则f是p的最右子孙的右线索若p是f的右子女则f是p的最左子孙的左线索）找到f后若p是f的右子女则p的后继是f若p是f的左子女且f无右子女则p的后继也是f若p是f的左子女且f有右子女则f的右子树中最左边的叶子结点是p的后继因此算法思路是先找p的双亲f根据p是f的左/右子女再确定p的后序后继

BiThrTree InThrPostSucc(BiThrTree rp)

//在中序线索二叉树r上求结点p（假定存在）的后序后继结点q）

{if(p==r)return(null) //若p为根结点后序后继为空

T=p

while(T>LT==) T=T>LL; //找p的最左子孙的左线索

q=T>LL; //q是 p最左子孙的左线索是p的祖先

if(q>RL==p) return(q); //p是q的右子女则q是p后序后继

T=p;

while(T>RT==) T=T>RL; //找p的最右子孙的右线索

q=T>RL; //q是p最右子孙的右线索

if(q>LL=p) //若p是q的左子女

if(q>RT==) return(q);//若p是q的左子女且q无右子女则p的后序后继是q

else //p的双亲q有右子树则q的右子树上最左下的叶子结点是p的后继

{q=q>RL;

while(q>LT==||q>RT==) //找q右子树中最左下的叶子结点

{while(q>LT==) q=q>LL; //向左下

if(q>RT==) q=q>RL; //若q无左子女但有右子女则向右下直到叶子结点

}

return(q); //q是的p后继

}

} //结束InThrPostSucc

[算法讨论] 请注意本题条件标记为时是线索而为时是指向子女

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