二叉树的遍历操作（递归+非递归+层次遍历）

递归+非递归+层次遍历）"/>

二叉树的遍历操作（递归+非递归+层次遍历）

要想实现二叉树的各种操作，首先需要我们根据自己的要求创建一个二叉树，一般情况下我们要求二叉树的结构只需要包括要存储的数据，左子树和右子树三个部分，下面我们就根据这一结构进行创建。

typedef struct BiTNode{				//树的结构体 ElemType data;				//二叉树中存储的数据 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

创建有三种方法，前序插入式创建，中序插入式创建，后序插入式创建。这里主要讲前序插入式创建，另外两种创建方法同理，小伙伴们可以自己编写算法。下面看前序插入式创建：

void CreateBiTree(BiTree &T)	//先序创建二叉树 
{ElemType ch;cin >> ch;if (ch == '#')                       //我们以输入‘#’来表示空T = NULL; 			//保证是叶结点else{T = (BiTree)malloc(sizeof(BiTNode));if (!T)exit(OVERFLOW); 				//内存分配失败则退出。T->data = ch;			    	        //生成结点CreateBiTree(T->lchild);			//构造左子树CreateBiTree(T->rchild);			//构造右子树    }
}

对于二叉树的遍历，同样我们也有三种遍历方式，前序遍历，中序遍历和后序遍历。每种遍历方法又有递归式和非递归式。下面我先贴出来递归式的三种遍历方式，因为递归的方法比较简单，而且很容易想到。下面请看：

void Operation(ElemType date)				//此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据
{cout<<date<<" ";
}void PreOrderTraverse(BiTree T)				//先序递归遍历二叉树 
{if (T == NULL)return;									Operation(T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);
}void InOrderTraverse(BiTree T)				//中序递归遍历二叉树 
{if(T == NULL)return;InOrderTraverse(T->lchild);Operation(T->data);InOrderTraverse(T->rchild);
}void PostOrderTraverse(BiTree T)			//后序递归遍历二叉树 
{if(T == NULL)return;PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);Operation(T->data);
}

这三种遍历方法的主要区别是执行Operation()函数的顺序不同。

对于三种遍历方法的非递归算法，这里我们需要用到栈来实现，首先我们先来回忆一下栈的结构体和栈的基本操作。

typedef struct{						//栈的结构体 SElemType *base;				//栈的基底指针 SElemType *top;					//栈顶指针 int stacksize;					//存储栈的长度 
}SqStack;

Status InitStack(SqStack &S)                			//构造一个空栈 
Status PushStack(SqStack &S,BiTree e)				//插入元素e为新的栈顶元素 
Status PopStack(SqStack &S,BiTree &e)				//返回栈顶元素并删除栈顶元素 
Status GetTop(SqStack S,BiTree &e)				//将栈顶元素赋给e 
Status JudgeEmptyStack(SqStack S)				//返回栈的长度 
Status DestoryStack(SqStack &S)					//销毁此栈 

为了便于理解，这里以下图的二叉树为例，分析二叉树的三种遍历方式的实现过程。

​

根据先序遍历的顺序，先访问根节点，再访问左子树，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的先序遍历顺序为：ABDECF。非递归的实现思路如下：

对于任一节点P，

1）输出节点P，然后将其入栈，再看P的左孩子是否为空；

2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；

3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；

4）若不为空，则循环至1）操作；

5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；

6）直到当前节点P为NULL并且栈空，遍历结束。

 

下面以上图为例详细分析其先序遍历的非递归实现过程：

首先，从根节点A开始，根据操作1），输出A，并将其入栈，由于A的左孩子不为空，根据操作2），将B置为当前节点，再根据操作1），将B输出，并将其入栈，由于B的左孩子也不为空，根据操作2），将D置为当前节点，再根据操作1），输出D，并将其入栈，此时输出序列为ABD；

由于D的左孩子为空，根据操作3），将栈顶节点D出栈，但不输出，并将其右孩子置为当前节点；

由于D的右孩子为空，根据操作5），继续将栈顶节点B出栈，但不输出，并将其右孩子置为当前节点；

由于B的右孩子E不为空，根据操作1），输出E，并将其入栈，此时输出序列为：ABDE；

由于E的左孩子为空，根据操作3），将栈顶节点E出栈，但不输出，并将其右孩子置为当前节点；

由于E的右孩子为空，根据操作5），继续将栈顶节点A出栈，但不输出，并将其右孩子置为当前节点；

由于A的右孩子C不为空，根据操作1），输出C，并将其入栈，此时输出序列为：ABDEC；

由于A的左孩子F不为空，根据操作2），则将F置为当前节点，再根据操作1），输出F，并将其入栈，此时输出序列为：ABDECF；

由于F的左孩子为空，根据操作3），将栈顶节点F出栈，但不输出，并将其右孩子置为当前节点；

由于F的右孩子为空，根据操作5），继续将栈顶元素C出栈，但不输出，并将其右孩子置为当前节点；

此时栈空，且C的右孩子为NULL，因此遍历结束。

下面来看先序遍历非递归算法：

void NONPreOrderTraverse(BiTree T)		//先序非递归遍历二叉树 
{SqStack S;								  InitStack(S);				//创建一个空栈BiTree ff;				//用来保存出栈的节点while(tt || JudgeEmptyStack(S)){//从根节点开始，输出当前节点，并将其入栈，  //同时置其左孩子为当前节点，直至其没有左孩子，即当前节点为NULL  cout<<tt->data<<" ";PushStack(S,tt);tt = tt->lchild;//如果当前节点pCur为NULL且栈不空，则将栈顶节点出栈  //同时置其右孩子为当前节点,循环判断，直至tt不为空 while(!tt && JudgeEmptyStack(S)){PopStack(S,tt);				//删除栈顶元素并赋给tt tt = tt->rchild;}}DestoryStack(S);
}

 

​

 

根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的中序遍历顺序为：DBEAFC。非递归的实现思路如下：

对于任一节点P，

1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；

2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；

3）若不为空，则重复1）和2）的操作；

4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；

5）直到当前节点P为NULL并且栈为空，则遍历结束。

 

下面以上图为例详细分析其中序遍历的非递归实现过程：

首先，从根节点A开始，A的左孩子不为空，根据操作1）将A入栈，接着将B置为当前节点，B的左孩子也不为空，根据操作1），将B也入栈，接着将D置为当前节点，由于D的左子树为空，根据操作2），输出D；

由于D的右孩子也为空，根据操作4），执行出栈操作，将栈顶结点B出栈，并将B置为当前节点，此时输出序列为DB；

由于B的右孩子不为空，根据操作3），将其右孩子E置为当前节点，由于E的左孩子为空，根据操作1），输出E，此时输出序列为DBE；

由于E的右孩子为空，根据操作4），执行出栈操作，将栈顶节点A出栈，并将节点A置为当前节点，此时输出序列为DBEA；

此时栈为空，但当前节点A的右孩子并不为NULL，继续执行，由于A的右孩子不为空，根据操作3），将其右孩子C置为当前节点，由于C的左孩子不为空，根据操作1），将C入栈，将其左孩子F置为当前节点，由于F的左孩子为空，根据操作2），输出F，此时输出序列为：DBEAF；

由于F的右孩子也为空，根据操作4），执行出栈操作，将栈顶元素C出栈，并将其置为当前节点，此时的输出序列为：DBEAFC；

由于C的右孩子为NULL，且此时栈空，根据操作5），遍历结束。

同理我们可以得到中序遍历非递归算法：

void NONInOrderTraverse(BiTree T)			//中序非递归遍历二叉树 
{SqStack S;								  InitStack(S);					//创建一个空栈BiTree tt = T;					//指向当前访问节点的指针 while(tt || JudgeEmptyStack(S))			//直到当前节点tt为NULL且栈空时，循环结束 {if(tt->lchild)			//如果tt的左孩子不为空，则将其入栈，并置其左孩子为当前节点  {PushStack(S,tt);tt = tt->lchild;}else{//如果pCur的左孩子为空，则输出tt节点，并将其右孩子设为当前节点，看其是否为空cout<<tt->data<<" ";tt = tt->rchild;while(!tt && JudgeEmptyStack(S)){//如果为空，且栈不空，则将栈顶节点出栈，并输出该节点，  //同时将它的右孩子设为当前节点，继续判断，直到当前节点不为空  PopStack(S,tt);cout<<tt->data<<" ";tt = tt->rchild;}}}
}

最后让我们来看一看后序遍历的非递归算法，它和之前的两种遍历方式不同，这个略微复杂一点，不容易想到。下面请看：

​

根据后序遍历的顺序，先访问左子树，再访问右子树，后访问根节点，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的后序遍历顺序为：DEBFCA。后序遍历的非递归的实现相对来说要难一些，要保证根节点在左子树和右子树被访问后才能访问，思路如下：

对于任一节点P，

1）先将节点P入栈；

2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；

3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；

4）直到栈空，遍历结束。

 

下面以上图为例详细分析其后序遍历的非递归实现过程：

首先，设置两个指针：Cur指针指向当前访问的节点，它一直指向栈顶节点，每次出栈一个节点后，将其重新置为栈顶结点，Pre节点指向上一个访问的节点；

Cur首先指向根节点A，Pre先设为NULL，由于A存在左孩子和右孩子，根据操作3），先将右孩子C入栈，再将左孩子B入栈，Cur改为指向栈顶结点B；

由于B的也有左孩子和右孩子，根据操作3），将E、D依次入栈，Cur改为指向栈顶结点D；

由于D没有左孩子，也没有右孩子，根据操作2），直接输出D，并将其出栈，将Pre指向D，Cur指向栈顶结点E，此时输出序列为：D；

由于E也没有左右孩子，根据操作2），输出E，并将其出栈，将Pre指向E，Cur指向栈顶结点B，此时输出序列为：DE；

由于B的左右孩子已经被输出，即满足条件Pre==Cur->lchild或Pre==Cur->rchild，根据操作2），输出B，并将其出栈，将Pre指向B，Cur指向栈顶结点C，此时输出序列为：DEB；

由于C有左孩子，根据操作3），将其入栈，Cur指向栈顶节点F；

由于F没有左右孩子，根据操作2），输出F，并将其出栈，将Pre指向F，Cur指向栈顶结点C，此时输出序列为：DEBF；

由于C的左孩子已经被输出，即满足Pre==Cur->lchild，根据操作2），输出C，并将其出栈，将Pre指向C，Cur指向栈顶结点A，此时输出序列为：DEBFC；

由于A的左右孩子已经被输出，根据操作2），输出A，并将其出栈，此时输出序列为：DEBFCA；

此时栈空，遍历结束。

void NONPostOrderTraverse(BiTree T)		//后序非递归遍历二叉树
{SqStack S;InitStack(S);BiTree pop;				//保存出栈的节点  BiTree pCur;				//指向当前节点BiTree pPre=NULL;			//指向上一个访问的节点 PushStack(S,T);				//先将树的根节点入栈 while(JudgeEmptyStack(S))	//直到栈空时结束循环 {GetTop(S,pCur);if((!pCur->lchild && !pCur->rchild) || (pPre!=NULL && (pCur->lchild == pPre || pCur->rchild == pPre))){//如果当前节点没有左右孩子，或者有左孩子或有孩子，但已经被访问输出 cout<<pCur->data<<" ";		//输出数据 PopStack(S,pop);		//将出栈的几点记录下来，好像并没有什么用处？只是为了函数的格式？？？ pPre = pCur;			//将该节点设为上一个访问的节点，后边会用到 }else{//如果不满足上边的两种情况，则将其右孩子左孩子按顺序入栈 if(pCur->rchild)PushStack(S,pCur->rchild);if(pCur->lchild)PushStack(S,pCur->lchild);}}
}

以上就是二叉树的三种遍历方法的递归写法和非递归写法，看着代码是不是又多又长啊！

虽然我们平时用不到这么多遍历方法，像非递归遍历的代码又臭又长又复杂我们更是不愿意用了，但是我们可以从算法中学习栈的使用，能让我们更熟悉栈，这对我们也是有很对帮助的。

其实呢，我们还有一种遍历方法，这种方法叫做“层次遍历”，所谓层次遍历，就是按照二叉树的结构一层一层的往下遍历，这样的遍历过程使得二叉树更具有树的层次感！层次遍历就用不到栈了，但是需要用到另外一种结构队列，首先先让我们回顾一下队列的结构的队列的基本操作吧！

typedef struct queue{			//队列的结构体 QElemType *base;		//数组首地址int front,rear;			//一个头下标，一个尾下标
}SqQueue;

Status InitQueue(SqQueue &Q)     	//构造一个空队列
Status EnQueue(SqQueue &Q,BiTree e)	//插入树e的data为新的队尾元素 
Status DeQueue(SqQueue &Q,BiTree &e)	//出队列（队头元素） 
Status QueueLength(SqQueue &Q)	        //返回队列的长度
Status DestoryQueue(SqQueue &Q)		//销毁队列

​

 如果按照层次遍历来遍历此图，顺序是：ABCDEF

 

void  Translevel(BiTree T)		//层次遍历，运用队列 
{SqQueue Q;InitQueue(Q);EnQueue(Q,T);while(QueueLength(Q)){BiTree t;DeQueue(Q,t); if(t->lchild)EnQueue(Q,t->lchild);	//将左孩子入队列 if(t->rchild)EnQueue(Q,t->rchild);	//将右孩子入队列 cout<<t->data<<" ";	}DestoryQueue(Q);
}

对了，多亏我的小伙伴提醒，我忘了贴上头文件和一些重要的声明：

#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue> 
#define ElemType	char
#define QElemType 	BiTree				//队列中的元素设为二叉树类型 
#define SElemType 	BiTree				//栈中的元素设为二叉树类型 
#define Status		char
#define OVERFLOW 	-2
#define OK			1
#define ERROR		0						
#define MAXQSIZE	100					//队列的初始化长度 
#define STACK_INIT_SIZE 100				//栈的初始化长度 
#define STACK_INCREMENT 10				//栈溢出时增加栈的存储长度 

嘻嘻可能还有小问题哦，就允许我慢慢改正⑧！