Q1-数据结构

题目

(摘自王道考研数据结构5.3.3习题第五题)

在二叉树中有两个节点m和n，若m是n的祖先节点，则使用后序遍历可以找到m到n的路径。

分析

首先需要理解的是，前中后序遍历都是通过递归的方式，这里我们以非递归的代码来理解，将后来需要用到的结点保存在栈中，比如下面这颗树：

前序遍历：根左右，过程是：根节点m入栈并输出，访问m的左孩子a，a入栈并输出，访问a的左孩子c，c入栈并输出，c没有左孩子，无元素入栈，c没有右孩子，无元素入栈，c出栈，此时栈顶元素为a，访问a元素的右孩子d，d入栈并输出，d没有左孩子，无元素入栈，d没有右孩子，无元素入栈，d出栈，a左右子树都访问完了所以出栈，现在栈顶元素是m，m已经没有作用了所以出栈，访问m的右孩子b，m的右孩子b入栈并输出，接着访问b的左孩子e，e入栈并输出……

中序遍历：左根右，过程是：根节点m入栈，访问m的左孩子，所以m的左孩子a入栈，访问a的左孩子，所以a的左孩子c入栈，c没有左孩子，c现在输出并出栈，c没有右孩子所以没有元素入栈，现在栈顶元素是a，a输出并出栈，a的右孩子d入栈，此时d没有左孩子所以没有元素入栈，d输出并出栈，d没有右孩子所以没有元素入栈，现在栈顶元素是m，m输出，此时m已经没有作用了所以出栈，m的右孩子b入栈，访问b的左孩子，所以b的左孩子e入栈……

后序遍历：左右根，过程是：根节点m入栈，访问m的左孩子，所以m的左孩子a入栈，访问a的左孩子，所以a的左孩子入栈，c没有左孩子和右孩子，没有元素入栈，c现在输出并出栈。现在栈顶元素是a，a的右孩子d入栈，d没有左孩子和右孩子，没有元素入栈，d现在输出并出栈。此刻栈顶是a，且a的左孩子右孩子均已经访问过，所以此刻a输出并出栈。此刻栈顶元素是m，m的右孩子b入栈，访问b的左孩子，所以m的左孩子b入栈，b有左孩子e，所以e入栈，e有左孩子g，所以g入栈，g没有左孩子和右孩子，没有元素入栈，g此刻输出并出栈。此刻栈顶元素是e，e有右孩子n，即目标元素之一，所以n入栈，因为n没有左孩子和右孩子，所以输出n并出栈。此刻栈顶元素是e，且e的左右孩子均已经被访问，所以输出e并出栈。此刻栈顶是b，b有孩子f，所以f入栈，f没有左右孩子，所以输出f并出栈，此刻栈顶是b，且b的左右孩子均已被访问，所以输出b并出栈。此刻栈顶元素是m，m的左右孩子均已访问，所以m出栈。

所以在前序和中序的过程中，如果n在m的右子树部分，遍历过程中找到了n，但是m已经不在栈中，因为栈中只会保留等会需要用到的e和b结点，而m已经完成了访问根结点和m的左子树的任务，已经被出栈，所以无法追溯n如何走到m。

但是后序遍历就不一样啦，后序的顺序是左右根，所以只要m的左右子树还没遍历完成，m就不能出栈，在遍历m的左右子树过程中，无论在m的左边还是右边找到了n，都可以直接返回然后根据栈中的路径让n找到回到m的路，这样就能找到m到n的路径～

代码

//先序、中序和后序非递归遍历算法
typedef struct 
{	BTNode *data[MaxSize];			//存放栈中的数据元素
	int top;						//存放栈顶指针，即栈顶元素在data数组中的下标
} SqStack;	

void PreOrder1(BTNode *b)			//先序非递归遍历算法1
{
	BTNode *p;
	SqStack *st;					//定义一个顺序栈指针st
	InitStack(st);					//初始化栈st
	Push(st,b);					//根节点进栈
	while (!StackEmpty(st))		//栈不为空时循环
	{
		Pop(st,p);				//退栈节点p并访问它
		printf("%c ",p->data);	//访问节点p
		if (p->rchild!=NULL)	//有右孩子时将其进栈
			Push(st,p->rchild);
		if (p->lchild!=NULL)	//有左孩子时将其进栈
			Push(st,p->lchild);
	}
	printf("\n");
	DestroyStack(st);				//销毁栈
}
void PreOrder2(BTNode *b)			//先序非递归遍历算法2
{
	BTNode *p;
	SqStack *st;					//定义一个顺序栈指针st
	InitStack(st);					//初始化栈st
	p=b;
	while (!StackEmpty(st) || p!=NULL)
	{
		while (p!=NULL)				//访问节点p及其所有左下节点并进栈
		{
			printf("%c ",p->data);	//访问节点p
			Push(st,p);				//节点p进栈
			p=p->lchild;			//移动到左孩子
		}
		if (!StackEmpty(st))		//若栈不空
		{
			Pop(st,p);				//出栈节点p
			p=p->rchild;			//转向处理其右子树
		}
	}
	printf("\n");
	DestroyStack(st);				//销毁栈
}
void InOrder1(BTNode *b)				//中序非递归遍历算法
{
	BTNode *p;
	SqStack *st;						//定义一个顺序栈指针st
	InitStack(st);						//初始化栈st
	if (b!=NULL)
	{
		p=b;
		while (!StackEmpty(st) || p!=NULL)
		{
			while (p!=NULL)				//扫描节点p的所有左下节点并进栈
			{
				Push(st,p);				//节点p进栈
				p=p->lchild;			//移动到左孩子
			}
			if (!StackEmpty(st))		//若栈不空
			{
				Pop(st,p);				//出栈节点p
				printf("%c ",p->data);	//访问节点p
				p=p->rchild;			//转向处理其右子树
			}
		}
		printf("\n");
	}
	DestroyStack(st);				//销毁栈
}

void PostOrder1(BTNode *b)				//后序非递归遍历算法
{
	BTNode *p,*r;
	bool flag;
	SqStack *st;						//定义一个顺序栈指针st
	InitStack(st);						//初始化栈st
	p=b;
	do
	{
		while (p!=NULL)					//扫描节点p的所有左下节点并进栈
		{
			Push(st,p);					//节点p进栈
			p=p->lchild;				//移动到左孩子
		}
		r=NULL;							//r指向刚刚访问的节点，初始时为空
		flag=true;						//flag为真表示正在处理栈顶节点
		while (!StackEmpty(st) && flag)
		{
			GetTop(st,p);				//取出当前的栈顶节点p
			if (p->rchild==r)			//若节点p的右孩子为空或者为刚刚访问过的节点	
			{
				printf("%c ",p->data);	//访问节点p
				Pop(st,p);
				r=p;					//r指向刚访问过的节点
			}
			else
			{	
				p=p->rchild;			//转向处理其右子树
				flag=false;				//表示当前不是处理栈顶节点
			}
		}
	} while (!StackEmpty(st));			//栈不空循环
	printf("\n");
	DestroyStack(st);				//销毁栈
}

补充

Q:可是问题是这个方法会夹杂着不属于路径的节点，比如n的兄弟节点？

A:如果n是左叶子结点，则会先访问n，如果n是右叶子结点有左兄弟结点，左兄弟结点被访问后会提前出栈，然后才会访问n，所以访问到n的时候，栈中剩余的元素就可以找到从n到m的路径，中间无其他结点。

参考

1. 在二叉树中有两个结点m和n，若m是n的祖先，则使用后序遍历可以找到从m到n的路径 ↩
2. 在二叉树中有两个结点M,N，M是N祖先，为什么是后序遍历找到M到N的路径，而不是先序遍历呢？ ↩