几种算法
已知一棵二叉树按顺序方式存储在数组 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==1j==1A[i]==0A[j]==0i==j) // A[i]==0或A[j]==0表示不存在该结点
{printf("Error.");return;}
while(i!=1&&j!=1){
if(ij){j=j/2;m=1;} // 结点 j 的最近祖先结点是 ┗ j/2 ┛
else if(ji){i=i/2;k=1;}
else if(j==i){i=j;break;} // i=j 表示找到共同祖先
}
if(j==1i==1)i=1; // i 或 j 有一个到了根结点
else if(m==0k==0)i=i/2; // m、k 中有一个为 0 ，说明在查找过程中 i 或 j 有一个没...[ 查看全文 ]
