用c语言编写给定一个二叉树, 编写算法计算二叉树中任意两个结点的公共祖先。其中,输入第一行为二叉树序列,第二行和第三行分别为两个节点数据;输出:两个节点的公共祖先(最近的父节点)
时间: 2024-05-15 10:18:30 浏览: 99
好的,我已经理解了你的问题。下面是C语言的代码实现:
```
#include<stdio.h>
//定义二叉树结点的数据结构
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
//搜索二叉树中指定值的结点
struct TreeNode* searchNode(struct TreeNode* root, int val) {
if (!root || root->val == val) {
return root;
}
if (val < root->val) {
return searchNode(root->left, val);
} else {
return searchNode(root->right, val);
}
}
//计算两个结点的公共祖先
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (!root || root == p || root == q) {
return root;
}
if ((root->val > p->val && root->val < q->val) ||
(root->val > q->val && root->val < p->val)) {
return root;
}
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
} else {
return lowestCommonAncestor(root->right, p, q);
}
}
int main() {
//构建二叉树
struct TreeNode a = {6, NULL, NULL};
struct TreeNode b = {2, NULL, NULL};
struct TreeNode c = {0, NULL, NULL};
struct TreeNode d = {4, NULL, NULL};
struct TreeNode e = {3, NULL, NULL};
struct TreeNode f = {5, NULL, NULL};
struct TreeNode g = {8, NULL, NULL};
struct TreeNode h = {7, NULL, NULL};
struct TreeNode i = {9, NULL, NULL};
a.left = &b;
a.right = &g;
b.left = &c;
b.right = &d;
d.left = &e;
d.right = &f;
g.left = &h;
g.right = &i;
//读取输入
int node1, node2;
scanf("%d", &node1);
scanf("%d", &node2);
//搜索二叉树中指定值的结点
struct TreeNode* p = searchNode(&a, node1);
struct TreeNode* q = searchNode(&a, node2);
//计算两个结点的公共祖先
struct TreeNode* result = lowestCommonAncestor(&a, p, q);
//输出结果
printf("%d", result->val);
return 0;
}
```
其中,我们通过searchNode函数来查找二叉树中对应值的结点,然后通过lowestCommonAncestor函数来计算两个结点的公共祖先,最后输出结果即可。
阅读全文