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

．[题目分析]第题已讨论了在中序线索树中查找结点p的后序后继问题本题要求在中序线索树上进行后序遍历因后序遍历是左右根最后访问根结点即只有从右子树返回时才能访问根结点为此设一标志returnflag当其为时表示从右侧返回可以访问根结点为了找当前结点的后继需知道双亲结点的信息在中序线索树中某结点最左子孙的左线索和最右子孙的右线索均指向其双亲因此设立两个函数LeftMost和RightMost求结点的最左和最右子孙为了判定是否是从右子树返回再设一函数IsRightChild

BiThrTree LeftMost(BiThrTree t) //求结点t最左子孙的左线索

{BiThrTree p=t;

while(p>ltag==) p=p>lchild; //沿左分枝向下

if (p>lchild!=null) return(p>lchild); else return(null);

}//LeftMost

BiThrTree RightMost（BiThrTree t）//求结点t最右子孙的右线索

{BiThrTree p=t;

while(p>rtag==) p=p>rchild; //沿右分枝向下

if (p>rchild!=null) return (p>rchild); else return(null);

}//RightMost

int IsRightChild(BiThrTree tfather) //若t是father 的右孩子返回否则返回

{father=LeftMost(t);

if(father &&f ather>rchild==t) return(); else return();

}//Is RightChild;

void PostOrderInThr (BiThrTree bt) //后序遍历中序线索二叉树bt

{BiThrTree father p=bt;

int flag;

while(p!=null)

{while(p>ltag== ) p=p>lchild; // 沿左分枝向下

if(p>rtag==) flag=;//左孩子为线索右孩子为链相当从左返回

else flag=; //p为叶子相当从右返回

while(flag==)

{visit(*p);//访问结点

if(IsRightChild(pfather)) {p=father; flag=;} //修改p指向双亲

else //p是左子女用最右子孙的右线索找双亲

{p=RightMost(p);

if(p&&p>rtag==) flag=; else flag=;

}

}// while(flag==)

if(flag== && p!=null) p=p>rchild; //转向当前结点右分枝

} }//结束PostOrderInThr

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