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

[题目分析]后序遍历最后访问根结点即在递归算法中根是压在栈底的采用后序非递归算法栈中存放二叉树结点的指针当访问到某结点时栈中所有元素均为该结点的祖先本题要找p和q 的最近共同祖先结点r 不失一般性设p在q的左边后序遍历必然先遍历到结点p栈中元素均为p的祖先将栈拷入另一辅助栈中再继续遍历到结点q时将栈中元素从栈顶开始逐个到辅助栈中去匹配第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先

typedef struct

{BiTree t;int tag;//tag= 表示结点的左子女已被访问tag=表示结点的右子女已被访问

}stack;

stack s[]s[];//栈容量够大

BiTree Ancestor(BiTree ROOTpqr)//求二叉树上结点p和q的最近的共同祖先结点r

{top=; bt=ROOT;

while(bt!=null ||top>)

{while(bt!=null && bt!=p && bt!=q) //结点入栈

{s[++top]t=bt; s[top]tag=; bt=bt>lchild;} //沿左分枝向下

if(bt==p) //不失一般性假定p在q的左侧遇结点p时栈中元素均为p的祖先结点

{for(i=;i<=top;i++) s[i]=s[i]; top=top; }//将栈s的元素转入辅助栈s 保存

if(bt==q) //找到q 结点

for(i=top;i>;i)//将栈中元素的树结点到s去匹配

{pp=s[i]t;

for (j=top;j>;j)

if(s[j]t==pp) {printf(p 和q的最近共同的祖先已找到)return (pp);}

｝

while(top!= && s[top]tag==) top; //退栈

if (top!=)｛s[top]tag=;bt=s[top]t>rchild;｝ //沿右分枝向下遍历

}//结束while(bt!=null ||top>)

return(null);//ｑp无公共祖先

｝//结束Ancestor

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