数据结构-二叉树的遍历

对于二叉树，有深度遍历和广度遍历两种。深度遍历有前序、中序以及后序三种遍历方法，广度遍历即通常所说的层次遍历。
因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。

四种主要的遍历思想如下

• 前序遍历：根结点 —> 左子树 —> 右子树
• 中序遍历：左子树—> 根结点 —> 右子树
• 后序遍历：左子树 —> 右子树 —>根结点
• 层次遍历：按层次遍历,从上到下，从左到右

二叉树的结构定义

typedef struct TreeNode *BinTree;
struct TreeNode{
	int Data;        // 数据
	BinTree Left;    // 左儿子结点 
	BinTree Right;   // 右儿子结点 
};

1.先序遍历

1.处理当前节点
2.搜索当前节点的左子树
3.左子树搜索完毕后搜索当前节点的右子树

1.1递归实现

void  PreOrderTraversal(BinTree BT)
{
	if(BT)
	{
		printf("%d",BT->Data);        // 打印根 
		PreOrderTraversal(BT->Left);  // 进入左子树 
		PreOrderTraversal(BT->Right); // 进入右子树 
	}
}

1.2 非递归实现

根据前序遍历的顺序，优先访问根结点，然后在访问左子树和右子树。所以，对于任意结点node，第一部分即直接访问，之后在判断左子树是否为空，不为空时即重复上面的步骤，直到其为空。若为空，则需要访问右子树。注意，在访问过左孩子之后，需要反过来访问其右孩子，所以，需要栈这种数据结构的支持。对于任意一个结点node，具体步骤如下：

• ①访问之，并把结点node入栈，当前结点置为左孩子；
• ②判断结点node是否为空，若为空，则取出栈顶结点并出栈，将右孩子置为当前结点；否则重复①步直到当前结点为空或者栈为空（可以发现栈中的结点就是为了访问右孩子才存储的）

void PreOrderTraversal(BinTree BT)
{
	BinTree T = BT;               //定义临时指针
	Stack S = CreateStack();      // 创建并初始化堆栈 S
	while(T || !IsEmpty(S))       // 当树不为空或堆栈不空 
	{  
		while(T)
		{     
			Push(S,T);             // 压栈，第一次遇到该结点 
			printf("%d",T->Data);  // 访问结点
			T = T->Left;           // 遍历左子树 
		}
		if(!IsEmpty(S))
		{  // 当堆栈不空 
			T = Pop(S);            // 出栈，第二次遇到该结点 
			T = T->Right;          // 访问右结点 
		}
	} 
} 

2.中序遍历

1.搜索当前节点的左子树
2.处理当前节点
3.左子树搜索完毕后搜索当前节点的右子树

2.1递归实现

类似先序遍历

void InOrderTraversal(BinTree BT)
{
	if(BT)
	{
		InOrderTraversal(BT->Left);   // 进入左子树 
		printf("%d",BT->Data);        // 打印根节点数据 
		InOrderTraversal(BT->Right);  // 进入右子树 
	} 
}

2.2非递归实现

与先序遍历相同的道理。只不过访问的顺序移到出栈时：

• 遇到一个节点，便把它压入栈中，并去遍历它的左子树
• 当左子树遍历结束后，从栈顶弹出该节点，并访问
• 然后按其右指针再去中序遍历该节点的右子树

void InOrderTraversal(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreateStack();         // 创建并初始化堆栈 S
	while(T || !IsEmpty(S)){         // 当树不为空或堆栈不空 
		while(T)                     //该循环一直往左边走，边走边把节点压入堆栈中
		{     
			Push(S,T);              // 压栈 
			T = T->Left;            // 遍历左子树 
		}
		if(!IsEmpty(S))             //左子树到底后，从栈中推出元素，打印出来，再指向右节点
		{  // 当堆栈不空 
			T = Pop(S);            // 出栈
			printf("%d",T->Data);  // 访问结点
			T = T->Right;          // 访问右结点 
		}
	} 
} 

3.后序遍历

根据上面遍历思路：左子树 —> 右子树 —> 根结点

3.1 递归实现

void PostOrderTraversal(BinTree BT)
{
	if(BT)
	{
		PostOrderTraversal(BT->Left);   // 进入左子树 
		PostOrderTraversal(BT->Right);  // 进入右子树 
		printf("%d",BT->Data);          // 打印根 
	} 
}

3.1 非递归实现

 暂略

4.层次遍历

实现过程：
从跟节点开始，首先将跟节点入队，然后开始执行循环，节点出队，访问该节点，其左右儿子节点入队。即:

• ① 根结点入队
• ② 从队列中取出一个元素
• ③ 访问该元素所指结点
• ④左、右孩子结点入队
• ⑤循环 ②- ④，直到队列中为空

注，下程序中所使用的函数Creat_Qnene() Add_Qnene(q,T->Left); 及队列结构体定义均来自博文数据结构-队列

void LevelOrderTraversal(BinTree BT)
{
	Qnene* q=Creat_Qnene();  //创建空队列
	BinTree T; //创建临时树
	if(!BT)  return;  //空树直接返回
	Add_Qnene(q,BT);//首节点放入队列
	while(q->front!=NULL)    //队列不空时
	{
		T = Delate_Qnene(q) ; // 访问队首元素 
		printf("%d",T->Data);
		if(T->Left)  // 如果存在左儿子结点
		    Add_Qnene(q,T->Left);
	 	if(T->Right)
	 	    Add_Qnene(q,T->Right);
	}
}

5.总结

5.1二叉树遍历的核心问题：二维结构的线性化

• 从节点访问其左右节点，访问了左节点右节点怎么办？

故需要一个存储结构（堆栈、队列）保留暂时不访问的节点。

5.2先序、中序和后序遍历过程中经过结点的路线一样，只是访问各结点的时机不同，即：

• 先序遍历是第一次"遇到"该结点时访问
• 中序遍历是第二次"遇到"该结点（此时该结点从左子树返回）时访问
• 后序遍历是第三次"遇到"该结点（此时该结点从右子树返回）时访问