C语言数据结构-树和二叉树-共同祖先假设二叉树采用二叉链表方式存储， root指向根结点，p所指结点和q所指结点为二叉树中的两个结点，编写一个计算它们的最近的共同祖先

青旅半醒 2023-01-13 04:19 156阅读 0赞

# 共同祖先 #

假设二叉树采用二叉链表方式存储， root指向根结点，p所指结点和q所指结点为二叉树中的两个结点，编写一个计算它们的最近的共同祖先，函数定义如下：

BiTNode * nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q);

其中 root 指向二叉树的根结点，p 和 q 分别指向二叉树中的两个结点。  
提示：在完成本题时，可利用 path 函数获取p和q两个结点到根结点之间的路径，之后再计算两条公共路径得出最近的共同祖先。path函数及栈相关定义如下：

bool path(BiTNode* root, BiTNode* node, Stack* s);
    
    #define Stack_Size 50
    typedef BiTNode* ElemType;
    typedef struct{
        ElemType elem[Stack_Size];
        int top;
    }Stack;
    
    void init_stack(Stack *S); // 初始化栈
    bool push(Stack* S, ElemType x); //x 入栈
    bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
    bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
    bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false

**提供代码**

#include <stdlib.h>
    #include <stdio.h>
    #include "bitree.h" //请不要删除，否则检查不通过
    
    
    BiTNode * nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q){
    
    
    }

**参考代码**

BiTNode* nearest_ancestor(BiTree root, BiTNode* p, BiTNode* q)
    {
        Stack s1, s2;
        BiTNode* ancNode;
        init_stack(&s1);
        init_stack(&s2);
    	
        path(root, p, &s1);
        path(root, q, &s2);
    	
    	if (s1.elem[0] != s2.elem[0])
            return NULL;
    	
        ancNode = s1.elem[0];
        
        for (int i = 1; i < s1.top && i < s2.top; i++) 
    	{
            if (s1.elem[i] != s2.elem[i])
                return ancNode;
            ancNode = s1.elem[i];
        }
        return ancNode;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/59665e098eb449f5b1631ece6c5b5f24.png