假设二叉树采用链式方法存储,root为其根节点,p和q分别指向二叉树中任意两个结点,编写一个函数,返回p和q最近的共同祖先,用C语言编写详细的程序
时间: 2024-12-19 08:25:33 浏览: 15
在C语言中,我们可以创建一个递归函数来解决这个问题。首先,我们需要定义一个结构体`Node`表示二叉树的节点,并提供一些辅助函数用于查找最近公共祖先。以下是详细的步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} TreeNode;
// 创建一个新的节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!newNode) return NULL;
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// 插入节点到二叉树
TreeNode* insertNode(TreeNode* root, int value) {
if (root == NULL) return createNode(value);
if (value < root->data)
root->left = insertNode(root->left, value);
else
root->right = insertNode(root->right, value);
return root;
}
// 获取两个节点最近公共祖先
TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果根为空,或者p或q已经空了,说明它们没有公共祖先,直接返回NULL
if (!root || !p || !q) return NULL;
// 比较p和q与当前节点的关系
if (root == p || root == q)
return root;
// 分别沿着左子树和右子树查找
TreeNode* left = findLCA(root->left, p, q);
TreeNode* right = findLCA(root->right, p, q);
// 如果左子树和右子树都找到了p和q,则当前节点就是LCA
if (left && right) return root;
// 否则,继续沿着找到的那个方向搜索
return left ? left : right;
}
int main() {
// 初始化示例二叉树
TreeNode* root = NULL;
// 插入节点...
// ...
// 使用findLCA函数寻找最近公共祖先
TreeNode* lca = findLCA(root, p, q); // 假设p和q是二叉树中的实际节点指针
if (lca)
printf("The lowest common ancestor of %d and %d is %d\n", p->data, q->data, lca->data);
else
printf("Nodes %d and %d do not have a common ancestor.\n", p->data, q->data);
return 0;
}
```
注意,这个程序假设你已经有了一个已插入元素的二叉树,并且`p`和`q`是该二叉树中的有效节点。如果你需要在主函数里构建整个二叉树,你需要添加适当的插入操作。最后,别忘了处理`main`函数中的输入节点`p`和`q`。
阅读全文