c语言编写算法,在二叉排序树上找出任意两个不同结点的最近公共祖先。
时间: 2025-01-06 20:51:19 浏览: 8
在C语言中,要在二叉搜索树(BST)上找到任意两个不同节点的最近公共祖先(LCA),可以采用递归的方法。以下是基本步骤:
1. **基本情况**:如果根节点为空,说明输入的两个节点都不在这个树里,返回空;或者其中一个节点为空,另一个节点就是它自身,直接返回该节点。
2. **递归查找**:对于非空根节点,首先检查根节点是否既是第一个节点p的祖先,也是第二个节点q的祖先。如果是,则根节点即为最近公共祖先。如果不是,分别在左子树(小于根节点的值)和右子树(大于根节点的值)对p和q进行递归查找。
3. **递归终止条件**:当找到其中一方在左子树而另一方在右子树时,说明找到了一个分界点,最近公共祖先就在这个分界点的父节点上。
这里是一个简单的伪代码示例:
```c
struct TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) return NULL;
// 如果p或q小于root, 那么LCA肯定在左子树
if (p->val < root->val && q->val < root->val) {
return findLCA(root->left, p, q);
}
// 否则, LCA肯定在右子树或者根节点本身
else if (p->val > root->val && q->val > root->val) {
return findLCA(root->right, p, q);
} else {
return root; // 根节点同时满足p和q的条件
}
}
```
阅读全文