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

/*-------二叉树的二叉链结点结构定义------*/

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

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

/*-------栈的基本操作函数-------*/

  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

  /*-----栈的基本操作函数结束-----*/

*------树的基本操作的函数------*/
//按照二叉树的定义初始化一个空树
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;
}
/*----树的基本操作的函数结束----*/

/*求距两个子结点最近的共同祖先结点*/
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;
}

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