已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。

admin2013-07-12  27

问题 已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。

选项

答案 int.found=FALSEI Bitree*Find_Near_Ancient(Bitree T,Bitree P,Bitree q){ //求二叉树T中结点P和q的最近共同祖先 Bitree pathp[100],pathq[i00]; //设立两个辅助数组暂存从根到P,q的路径 Findpath(T,P,pathp,0); found=FALSE; Findpath(T,q,pathq,0); //求从根到p,q的路径放在pathp和pathq中 for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);, //查找两条路径上最后一个相同结点 return pathp[--i]; } void Findpath(Bitree T,Bitree P,Bitree path[],int i){ //求从T到P路径的递归算法 if(T==p) { found=TRUE; //找到 return; } path[i]=T; //当前结点存入路径 if(T->ichild) Findpath(T->ichild,P,path,i+1); //在左子树中继续寻找 if(T->rchild&&!found) Findpath(T->rchild,P,path,i+1); //在右子树中继续寻找 if(!found) path[i]=NULL; //回溯

解析 本题也可叙述为求,*p和*q两个结点的最小子树。
遍历访问到*p时,将*p结点的祖先保存到数组pathp中,再遍历访问到*q时,将*q结点的祖先保存到数组pathq中,将数组pathp与数组pathq的结点依次(从0开始)比较,找到最近的共同祖先。
转载请注明原文地址:https://kaotiyun.com/show/Juxi777K
0

最新回复(0)