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

答案：

参考答案：[解答]
int found=FALSE；
Bitree*Find_Near_Ancient(Bitree T,Bitree p,Bitree q){
//求二叉树T中结点p和q的最近共同祖先
Bitree pathp[A00],pathq[A00]； //设立两个辅助数组暂存从根到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+A)； //在左子树中继续寻找
if(T-＞rchild && ! found)
Findpath(T-＞rchild,p,path,i+A)； //在右子树中继续寻找
if(! found)
path[i]=NULL； //回溯
}

解析： 本题也可叙述为求*P和*q两个结点的最小子树。
遍历访问到*P时，将*P结点的祖先保存到数组pathp中，再遍历访问到*q时，将*q结点的祖先保存到数组pathq中，将数组pathp与数组pathq的结点依次(从0开始)比较找到最近的共同祖先。