【题目】已知一棵二叉树按顺序方式存储在数组 A[1..n]中。设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。
【来源】武汉大学2000年第五（1）题（8’）
【解答】
#inlcude <stdio.h>
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(i<j){j=j/2;m=1;} // 结点 j 的最近祖先结点是 ┗ j/2 ┛
else if(j<i){i=i/2;k=1;}
else 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 交替追赶，直到相等。