算法与数据结构 - 求二叉树两结点最近的共同祖先结点 - 《一大堆数据》

题目要求及思路分析
算法实现
define TElemType char

题目要求及思路分析

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

两种数据类型的结构体定义 ```c /———-二叉树的二叉链结点结构定义———/
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. 
用到的栈的基本操作函数
```c
/*-------栈的基本操作函数-------*/
   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
   /*-----栈的基本操作函数结束-----*/

用到的树的基本操作函数 ```c /———树的基本操作的函数———/ //按照二叉树的定义初始化一个空树 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. 
利用栈来存储访问目标结点的路径
```c
/*求距两个子结点最近的共同祖先结点*/
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;
}

对 p、 q 分别调用第 4 步中的函数，将得到的两个路径栈逆置，在逆置后的栈中出栈顶元素同时进行比较，得到公共祖先结点

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;
}

瓦雀

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

题目要求及思路分析

算法实现

define TElemType char