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

题目要求及思路分析

  • 题目要求：已知在二叉树中， 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;
    }

    ​