数据�l�构�W�六章算法设计题[9]_跨考网

1�Q�设一���二叉树(w��i)的结点结构�ؓ(f��) (LLINK,INFO,RLINK),ROOT为指向该二叉�?w��i)根�l�点的指针，p�?/span>q分别为指向该二叉�?w��i)中��L��两个�l�点的指针，试编写一���法ANCESTOR�Q?/span>ROOT�Q?/span>p,q,r�Q?/span>,该算法找�?/span>p�?/span>q的最�q�共同祖先结�?/span>r。�?a target="_blank">吉林大学 2000 二�?/span>3 �Q?/span>12分）(j��)】�?a target="_blank">中山大学 1994 六（15分）(j��)�?/span>

　　【参考答案�?/span>

　　.[题目分析]后序遍历最后访问根�l�点�Q�即在递归���法中，�Ҏ(gu��)��压在栈底的。采用后序非递归���法�Q�栈中存放二叉树(w��i)�l�点的指针，当访问到某结�Ҏ(gu��)���Q�栈中所有元素均������l�点的祖先。本题要�?/span>p�?/span>q 的最�q�共同祖先结�?/span>r ,不失一般性，�?/span>p�?/span>q的左辏V��后序遍历必然先遍历到结�?/span>p�Q�栈中元素均�?/span>p的祖先。将栈拷入另一辅助栈中。再�l�箋(hu��)遍历到结�?/span>q�Ӟ�����栈中元素从栈顶开始逐个到辅助栈中去匚w���Q�第一个匹配（即相�{�）(j��)的元素就是结�?/span>p �?/span>q的最�q�公��q��先�?/span>

　　typedef struct

　　{BiTree t;int tag;//tag=0 表示�l�点的左子女已被讉K���Q?/span>tag=1表示�l�点的右子女已被讉K��

　　}stack;

　　stack s[],s1[];//栈，定w��够大

　　BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树(w��i)上结�?/span>p�?/span>q的最�q�的共同���先�l�点r�?/span>

　　{top=0; bt=ROOT;

　　while(bt!=null ||top>0)

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

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

　　if(bt==p) //不失一般性，假定p�?/span>q的左�?/span>,遇结�?/span>p�Ӟ��栈中元素均�ؓ(f��)p的祖先结�?/span>

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

　　if(bt==q) //扑ֈ�q �l�点�?/span>

　　for(i=top;i>0;i--)//�Q�将栈中元素的树(w��i)�l�点�?/span>s1��d���?/span>

　　{pp=s[i].t;

　　for (j=top1;j>0;j--)

　　if(s1[j].t==pp) {printf(�?/span>p �?/span>q的最�q�共同的���先已找到�?/span>)�Q?/span>return (pp);}

　　�?/span>

　　while(top!=0 && s[top].tag==1) top--; //退�?/span>

　　if (top!=0)�?/span>s[top].tag=1;bt=s[top].t->rchild;�?/span> //沿右分枝向下遍历

　　}//�l�束while(bt!=null ||top>0)

　　return(null);//ｑ�?/span>p无公��q���?/span>

　　�?/span>//�l�束Ancestor