题目描述:已知二叉树采用顺序存储,求编号为 i和j的结点的最近公共祖先结点编号。
分析: 令两个下标从两个初始点开始,你追我赶的交替向上,直到在某地相遇。即先令较大的下标(对应位置较低的点)p通过p/2向上访问父节点——这是顺序存储树带来的最大方便——可以通过简单的计算得到父节点的位置——直到这个p超过了另一个下标,就令另一个下标开始往上访问。
int Ancestor(int i,int j){
while(i != j){
if(i > j)
i = i / 2;
else if(j > i)
j = k / 2;
else
return i;
}
}