c语言二叉树共同祖先
时间: 2023-11-24 21:05:54 浏览: 32
以下是两种C语言实现二叉树共同祖先的方法:
方法一:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 查找p或q结点是否在以root为根的二叉树中
bool findNode(BiTree root, BiTNode *p) {
if (root == NULL) {
return false;
}
if (root == p) {
return true;
}
if (findNode(root->lchild, p) || findNode(root->rchild, p)) {
return true;
}
return false;
}
// 查找p和q的最近公共祖先
BiTNode *nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
if (root == NULL || p == NULL || q == NULL) {
return NULL;
}
if (!findNode(root, p) || !findNode(root, q)) {
return NULL;
}
if (root == p || root == q) {
return root;
}
BiTNode *left = nearest_ancestor(root->lchild, p, q);
BiTNode *right = nearest_ancestor(root->rchild, p, q);
if (left != NULL && right != NULL) {
return root;
} else if (left != NULL) {
return left;
} else {
return right;
}
}
```
方法二:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef struct {
BiTNode *elem[100];
int top;
} Stack;
// 初始化栈
void init_stack(Stack *s) {
s->top = -1;
}
// 入栈
void push(Stack *s, BiTNode *node) {
s->top++;
s->elem[s->top] = node;
}
// 出栈
void pop(Stack *s) {
s->top--;
}
// 获取栈顶元素
BiTNode *get_top(Stack *s) {
return s->elem[s->top];
}
// 查找从根结点到指定结点的路径
bool path(BiTree root, BiTNode *node, Stack *s) {
if (root == NULL) {
return false;
}
push(s, root);
if (root == node) {
return true;
}
if (path(root->lchild, node, s) || path(root->rchild, node, s)) {
return true;
}
pop(s);
return false;
}
// 查找p和q的最近公共祖先
BiTNode *nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
Stack s1, s2;
BiTNode *Node1;
init_stack(&s1);
init_stack(&s2);
path(root, p, &s1);
path(root, q, &s2);
Node1 = get_top(&s1);
if (get_top(&s1) != get_top(&s2)) {
return NULL;
}
for (int i = 1; i < s1.top && i < s2.top; i++) {
if (s1.elem[i] != s2.elem[i]) {
return Node1;
}
Node1 = s1.elem[i];
}
return Node1;
}
```