求二叉树两结点最近的共同祖先结点

题目要求及思路分析

  • 题目要求:已知在二叉树中, root 为根结点, p 和* q 为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。 —-《数据结构习题集(C 语言版)》
  • 思路:
    • 显然在这个题目中,递归遍历不适用。同时先中后三种顺序,先序遍历比较合适。
    • 要利用栈的特性来存储访问目标结点的路径,以便于最后查找它的祖先结点。
    • p 和 q 的路径都找到后,我们可以看到根结点在栈底,而目标结点在栈顶,这样的话不利于我们比较两条路径上共同的祖先结点。所以,要将两个目标结点的路径栈逆置,使栈顶元素都为根结点,这样在出栈的时候可以比较两个栈顶元素指向的结点。直到出现第一个不同的结点时,取上一个出栈元素,即为距两目标结点最近的共同祖先结点。

算法实现

  1. 两种数据类型的结构体定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /*-------二叉树的二叉链结点结构定义------*/
    #define TElemType char

    typedef struct BiTNode{ // 结点结构
    TElemType data; // 结点数据
    struct BiTNode *lchild, *rchild; // 左右 孩子指针
    } BiTNode, *BiTree;

    /------栈的数据结构预定义------/
    define MAXSIZE 100 // 存储空间初始分配量

    typedef struct{

    BiTree data[MAXSIZE];

    int top; //用于栈顶指针

    }SqStack;

    /---------------------------/

  2. 用到的栈的基本操作函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /*-------栈的基本操作函数-------*/

    Status Push(SqStack *S, BiTree e){
    //插入元素e 为新的栈顶元素
    if (S->top = MAXSIZE - 1)return ERROR;
    S->top++;
    S->data[S->top] = e; //将新插入元素赋值给栈顶空间
    return OK;
    }

    BiTree Pop(SqStack *S){
    //若栈不空,则删除S的栈顶元素,用e返回其值,变返回oK;否则返回ERROR
    if (S->top == -1)return ERROR;
    BiTree e = S->data[S->top]; //将要删除的栈顶元素赋给e
    S->top--; //栈顶指针减一
    return e;
    } //pop

    /*-----栈的基本操作函数结束-----*/
  3. 用到的树的基本操作函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    /*------树的基本操作的函数------*/
    //按照二叉树的定义初始化一个空树
    Status InitBiTree(BiTree *bt){

    *bt = (BiTree)malloc(sizeof(BiTNode));
    if (!bt)return OVERFLOW;

    *bt = NULL;

    return OK;
    }

    //构造二叉链表表示的二叉树T
    //按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
    Status CreateBiTree(BiTree *T){
    TElemType ch;

    printf_s("请输入数据:");
    scanf_s("%c", &ch);
    getchar(); //getchar()用于处理回车占字符的问题
    if (ch == '#')
    *T = NULL;
    else{
    *T = (BiTree)malloc(sizeof(BiTNode));

    if (!T)return OVERFLOW; // 若内存分配失败,则返回OVERFLOW

    (*T)->data = ch; // 生成根结点
    CreateBiTree(&((*T)->lchild)); //构建左子树
    CreateBiTree(&((*T)->rchild)); //构建右子树
    }

    return OK;
    }
    /*----树的基本操作的函数结束----*/

  4. 利用栈来存储访问目标结点的路径

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    /*求距两个子结点最近的共同祖先结点*/
    Status FindPath(BiTree root, BiTree target, SqStack *path){

    SqStack* s;
    s = (SqStack *)malloc(sizeof(SqStack));

    BiTree node = root;

    while (1){
    Push(path, node); //将当前结点入栈
    if (node == target)return OK; //若当前结点即为目标结点,则可直接结束

    //若左孩子存在,则再看右孩子。若右孩子也存在,将右孩子存入栈s;若右孩子不存在,则直接访问下一个左孩子。
    //若左孩子不存在,则访问右孩子。若左右孩子都不存在,则去查看栈s中的栈顶元素所指结点。
    //重复操作,直到找到目标结点。这时栈path中存储的元素为访问到目标结点的所有元素。
    if (node->lchild){
    if (node->rchild){
    Push(s, node->rchild);
    }
    node = node->lchild;
    }else if (node->rchild){
    node = node->rchild;
    }else if (s){
    while (path->data[path->top]->rchild != s->data[s->top]){
    Pop(path);
    }
    node = s->data[s->top];
    Pop(s);
    }else{
    break;
    }
    }
    return OK;
    }
  5. p、 q 分别调用第 4 步中的函数,将得到的两个路径栈逆置,在逆置后的栈中出栈顶元素同时进行比较,得到公共祖先结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    Status CommentParent(BiTree* parent, BiTree root, BiTree p, BiTree q){
    SqStack *path_p, *path_q;
    path_p = (SqStack *)malloc(sizeof(SqStack));
    path_q = (SqStack *)malloc(sizeof(SqStack));

    FindPath(root, p, path_p);
    FindPath(root, q, path_q);

    SqStack *reverse_p, *reverse_q;
    reverse_p = (SqStack *)malloc(sizeof(SqStack));
    reverse_q = (SqStack *)malloc(sizeof(SqStack));

    while (path_p){
    Push(reverse_p, Pop(path_p));
    }
    while (path_q){
    Push(reverse_q, Pop(path_q));
    }

    while (reverse_p->data[reverse_p->top] == reverse_q->data[reverse_q->top]){
    *parent = reverse_p->data[reverse_p->top];
    Pop(reverse_p);
    Pop(reverse_q);
    }
    return OK;
    }