打印本文 打印本文  关闭窗口 关闭窗口  
数据结构：求最近的公共祖先结点的值
作者：佚名  文章来源：不详  点击数  更新时间：2007/12/21 18:06:32  文章录入：杜斌  责任编辑：杜斌
【题目】已知一棵二叉树按顺序方式存储在数组 a[1..n]中。设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。

【解答】
#inlcude
parent(int a[],int i,int j)
{int k,m;
m=k=0;
if(i==1||j==1||a[i]==0||a[j]==0||i==j) // a[i]==0或a[j]==0表示不存在该结点
{printf('error./n');return;}
while(i!=1&&j!=1){
if(ielse if(jelse if(j==i){i=j;break;} // i=j 表示找到共同祖先
}
if(j==1||i==1)i=1; // i 或 j 有一个到了根结点
else if(m==0||k==0)i=i/2; // m、k 中有一个为 0 ，说明在查找过程中 i 或 j 有一个没移动
printf('the nearest common parent is a[%d]./n',i);
}


【分析】本题思路是使 i 和 j 交替追赶，直到相等。
打印本文 打印本文  关闭窗口 关闭窗口