考试网 >> IT认证 >> 等级 >> 三级考试 >> 数据结构：求最近的公共祖先结点的值

发布时间：2006-06-27 04:52     点击：

【题目】已知一棵二叉树按顺序方式存储在数组 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 交替追赶，直到相等。

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。