已知一棵二叉树按顺序方式存储在数组 a [ 1 ··· n ] 中,设计一个C语言算法,求编号为 i 和 j 的两个结点的最近公共祖先结点的值。
时间: 2024-10-08 11:01:56 浏览: 36
在二叉树按照层次遍历顺序存储于数组a[1..n]的情况下,我们可以利用这种层次结构的特性来找到第i和j个节点的最近公共祖先(LCA)。首先,我们需要确定i和j的节点在树中的深度,然后从根节点开始逐层向下查找。以下是基于这个思路的C语言算法:
```c
#include <stdio.h>
// 定义二叉树节点结构
typedef struct Node {
int data;
struct Node* left, *right;
} Node;
// 计算给定节点的深度
int depth(Node* node) {
if (node == NULL) return 0;
return 1 + depth(node->left);
}
// 求解LCA的辅助函数,采用自底向上的策略
Node* lca(Node* root, int i, int j) {
if (root == NULL || i > depth(root) || j > depth(root)) return NULL; // 如果根为空或者目标在根以上,则返回NULL
int i_depth = depth(root) - i + 1;
int j_depth = depth(root) - j + 1;
// 如果两个节点在同一层,直接返回当前节点
if (i_depth == j_depth) return root;
// 否则,如果i在左,j在右,则左子树是它们的LCA
if (i_depth < j_depth) return lca(root->left, i, j);
// 否则,如果i在右,j在左,则右子树是它们的LCA
return lca(root->right, i, j);
}
// 主函数,输入为树的根节点和两个节点的编号
int findLCA(Node* root, int i, int j) {
return lca(root, i, j)->data;
}
int main() {
// 初始化树节点和填充数据...
Node* treeRoot = ...;
int i = ..., j = ...;
printf("The value of the LCA between nodes %d and %d is %d\n", i, j, findLCA(treeRoot, i, j));
return 0;
}
```
阅读全文