杭州交通信息网2017年大学生摄影大赛:关于binarytreenode的一个问题。
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/05 18:35:57
同理找出q的，然后比较两个栈中的节点，如果弹出的有不相等的，那么前一个就是所要求的。不知道代码如何写，大家帮帮忙！
看来没有人愿意帮忙啊！
struct
{ BiTree t;
int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问
}stack;
stack s[],s1[];
BiTree Ancestor(BiTree root,p,q)
{top=0; bt=root;
while(bt!=null ||top>0){
while(bt!=null && bt!=p && bt!=q){
s[++top].t=bt;
s[top].tag=0;
bt=bt->lchild;
} //沿左分枝向下
if(bt==p){
for(i=1;i<=top;i++)
s1[i]=s[i];
top1=top;
}//将栈s的元素转入辅助栈s1 保存
if(bt==q) //找到q 结点。
for(i=top;i>0;i--){
pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);}
｝
while(top!=0 && s[top].tag==1) top--; //退栈
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历
}//结束while(bt!=null ||top>0)
return(null);//q、p无公共祖先
｝//结束Ancestor
hehe
朋友不是我们不帮你啊
我们真的不懂
有余力不足
我们只有祝你早日解决疑难了~！