用c语言编程实现在二叉排序树T中,打印a, b两个结点的公共祖先
时间: 2024-05-14 11:17:17 浏览: 91
可以按照以下步骤实现:
1. 首先判断a和b是否都在二叉排序树T中,如果有一个不在,则无法找到公共祖先,直接返回NULL。
2. 从根节点开始遍历二叉排序树T,比较a和b的值与当前节点的值的大小关系,如果都小于当前节点的值,则说明a和b的公共祖先在当前节点的左子树中,递归遍历左子树;如果都大于当前节点的值,则说明a和b的公共祖先在当前节点的右子树中,递归遍历右子树;如果一个大于当前节点的值,一个小于当前节点的值,则说明当前节点就是a和b的公共祖先,直接返回当前节点。
3. 如果遍历到了叶子节点还没有找到公共祖先,则说明无法找到公共祖先,返回NULL。
下面是C语言实现的代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 判断节点是否在二叉排序树中
int is_in_tree(TreeNode *root, int val) {
if (root == NULL) {
return 0;
}
if (root->val == val) {
return 1;
}
if (val < root->val) {
return is_in_tree(root->left, val);
} else {
return is_in_tree(root->right, val);
}
}
// 找到a和b的公共祖先
TreeNode *find_common_ancestor(TreeNode *root, int a, int b) {
if (root == NULL) {
return NULL;
}
if (!is_in_tree(root, a) || !is_in_tree(root, b)) {
return NULL;
}
if (root->val > a && root->val > b) {
return find_common_ancestor(root->left, a, b);
} else if (root->val < a && root->val < b) {
return find_common_ancestor(root->right, a, b);
} else {
return root;
}
}
// 创建二叉排序树
TreeNode *create_tree(int val) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点到二叉排序树中
void insert_tree(TreeNode *root, int val) {
if (root->val > val) {
if (root->left == NULL) {
root->left = create_tree(val);
} else {
insert_tree(root->left, val);
}
} else {
if (root->right == NULL) {
root->right = create_tree(val);
} else {
insert_tree(root->right, val);
}
}
}
int main() {
// 创建二叉排序树
TreeNode *root = create_tree(6);
insert_tree(root, 2);
insert_tree(root, 8);
insert_tree(root, 0);
insert_tree(root, 4);
insert_tree(root, 7);
insert_tree(root, 9);
insert_tree(root, 3);
insert_tree(root, 5);
// 找到a和b的公共祖先
TreeNode *common_ancestor = find_common_ancestor(root, 3, 5);
if (common_ancestor == NULL) {
printf("No common ancestor found!\n");
} else {
printf("The common ancestor is: %d\n", common_ancestor->val);
}
return 0;
}
```
阅读全文