C语言实现每行给出一对整数键值U和V,求找到最近公共祖先结点的键值A。
时间: 2024-03-02 10:52:32 浏览: 14
要实现这个功能,可以采用二叉树的数据结构,然后利用树的性质,通过递归遍历的方式来查找最近公共祖先。
具体的实现步骤如下:
1. 定义一个二叉树的结构体,包含键值和左右子节点指针。
2. 采用递归的方式遍历二叉树,查找节点U和V的位置。
3. 如果当前节点为NULL或者等于U或V,则返回当前节点。
4. 递归遍历左右子树,如果左右子树均返回非空节点,则当前节点为最近公共祖先。
5. 如果左右子树中只有一个返回非空节点,则继续向上递归。
6. 最终返回最近公共祖先节点的键值即可。
下面是实现代码的示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* left;
struct Node* right;
} Node;
Node* create_node(int key) {
Node* node = (Node*) malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
return node;
}
Node* find_lca(Node* root, int u, int v) {
if (root == NULL || root->key == u || root->key == v) {
return root;
}
Node* left = find_lca(root->left, u, v);
Node* right = find_lca(root->right, u, v);
if (left != NULL && right != NULL) {
return root;
}
return left != NULL ? left : right;
}
int main() {
Node* root = create_node(1);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(4);
root->left->right = create_node(5);
root->right->left = create_node(6);
root->right->right = create_node(7);
int u = 4, v = 5;
Node* lca = find_lca(root, u, v);
printf("LCA of %d and %d is %d\n", u, v, lca->key);
u = 4, v = 6;
lca = find_lca(root, u, v);
printf("LCA of %d and %d is %d\n", u, v, lca->key);
u = 3, v = 7;
lca = find_lca(root, u, v);
printf("LCA of %d and %d is %d\n", u, v, lca->key);
return 0;
}
```
输出结果如下:
```
LCA of 4 and 5 is 2
LCA of 4 and 6 is 1
LCA of 3 and 7 is 3
```