非递归、递归遍历二叉树！

小鱼儿 2022-04-13 10:29 289阅读 0赞

**树的先、中、后、层序的遍历，需要用到栈结构和队结构。**

**首先来看树本身的定义：**

**typedef char TElemType;  
typedef struct BiTNode  
\{  
 TElemType data;  
 BiTNode \*lchild,\*rchild; // 左右孩子指针  
\}BiTNode,\*BiTree;**

**栈的定义如下：**

**typedef BiTree SElemType;   //栈元素为二叉树指针  
\#define STACK\_INIT\_SIZE 10 // 存储空间初始分配量  
\#define STACK\_INCREMENT 2 // 存储空间分配增量  
struct SqStack  
\{  
 SElemType \*base; // 在栈构造之前和销毁之后，base的值为NULL  
 SElemType \*top; // 栈顶指针  
 int stacksize; // 当前已分配的存储空间，以元素为单位  
\}; // 顺序栈**

**队的定义如下：**

**typedef BiTree QElemType//队列元素为二叉树指针;  
typedef struct QNode  
\{  
 QElemType data;  
 QNode \*next;  
\}\*QueuePtr;**

**struct LinkQueue  
\{  
 QueuePtr front,rear; // 队头、队尾指针  
\};**

**先序递归：**

**void PreOrderTraverse(BiTree T,void(\*Visit)(TElemType))  
\{ //递归先序  
 if(T) // T不空  
 \{  
  Visit(T->data); // 先访问根结点  
  PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树  
  PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树  
 \}  
\}**

**先序非递归：**

**算法描述：先序是根左右的顺序，首先每次都访问根结点并将其入栈，然后访问其左孩子，再将其左孩子看做是下一个根结点进行访问，若其左孩子的左孩子为空，则出栈（此时栈指针指向最初入栈的结点）。然后访问其右孩子，再将右孩子看做一个根结点依次按照上述方法进行访问。**

**\}  
void PreOrderTraverse1(BiTree T,void (\*Visit)(TElemType))  
\{//非递归(利用栈)实现先序遍历  
 SqStack S;  
 InitStack(S);  
 while(T||!StackEmpty(S))  
 \{  
  if (T)  
  \{   
      Visit(T->data);//第一个访问的永远是根，只要非空就输出  
       Push(S,T);//入栈根结点,若分支为空，方便返回路径  
       T=T->lchild;//遍历左分支  
  \}  
  else//左子树为空，说明已经遍历完根和左了，该右了  
  \{  
   Pop(S,T);//返回到栈顶元素  
   T=T->rchild;//访问它的右孩子  
  \}  
 \}  
\}**

**中序递归：**

**void InOrderTraverse(BiTree T,void(\*Visit)(TElemType))  
\{ //递归中序  
 if(T)  
 \{  
  InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树  
  Visit(T->data); // 再访问根结点  
  InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树  
 \}  
 \}**

**中序非递归：**

**算法描述：首先入栈根结点，若根结点的左孩子不空，就入栈左孩子，依次循环入栈左孩子，若发现左孩子的左孩子为空，则出栈弹出栈顶元素（此时其实访问到了最后一个左孩子，已是叶子结点了），访问其结点的值，再继续向右走，向右走的思路和上面一样，等于是在右子树上继续进行左中右顺序的访问。直到栈空为止。**

**void InOrderTraverse1(BiTree T,void (\*Visit)(TElemType))  
\{//非递归(利用栈)实现中序遍历  
 SqStack S;  
 InitStack(S);  
 while(T||!StackEmpty(S))  
 \{  
  if (T)  
  \{  
   Push(S,T);//入栈根结点  
   T=T->lchild;//遍历左分支  
  \}  
  else  
  \{  
   Pop(S,T);  
   Visit(T->data);  
   T=T->rchild;  
  \}  
 \}  
\}**

**后序递归：**

**void PostOrderTraverse(BiTree T,void(\*Visit)(TElemType))  
\{ //递归中序  
 if(T)  
 \{  
  PostOrderTraverse(T->lchild,Visit); // 先中序遍历左子树  
  PreOrderTraverse1(T->rchild,Visit); // 最后中序遍历右子树  
  Visit(T->data); // 再访问根结点  
 \}  
 \}**

**后序非递归：**

**算法描述：为了使输出的形式保持左右根的顺序，那么必须使得所有的左子树访问完成，然后所有的右子树访问完成后再访问根。为了准确描述，需要重新定义两个记录指针，cur和pre，前者是指示当前指针，后者是指向前一次位置的指针。遍历时首先先将根节点入栈，每次取栈顶元素的指针( 即top-1)为cur。这样一来可总结为：**

**    若，**

**     \{**

**       1、当前左孩子和右孩子均为空（只有根节点）。**

**       2、当前的结点已经访问过。（下面有说明）**

**     \}**

**     \{则指针访问该结点的值；\}**

**    否则（说明有左右孩子），**

**    \{哪个孩子非空就入栈哪个孩子；\}**

**    什么叫已经访问过的结点？这里说明一下。根据上述的压栈顺序，比如我们现在分别压入根a，右a，左a。假设现在左a和右a都没有孩子了，这个子树已经是树的结尾了。那么栈顶的前三个元素依次为左a，右a，根a。首先取栈顶元素左a，发现其已经是叶子节点了，没有左右孩子，直接访问，退栈到右a，发现右a也没有左右孩子，也可以访问，然后退栈到根a，这时问题就来了，根a是有孩子的啊（左a和右a），理论上是不能访问的，可是我们已经按照左右根的顺序访问过了它的孩子，应该轮到他了呀。这里就需要对已经访问的结点做出判断，即满足pre=cur->lchild ||pre=cur->rchild时也可以访问。**

**   ** **void PostOrderTraverse1(BiTree T,void(\*Visit)(TElemType))  
\{//对于任意节点，先将其入栈。如果它没有左孩子和右孩子则直接访问它；若它有  
 // 左孩子或者右孩子，但是已经被访问过了(是否访问用两个指针之间的关系判断)也可以访问它；  
 //如果都不是上述两种情况，则先访问它的右孩子，再访问它的左孩子，以此来保证能够左、右、根的输出。  
 SqStack S;  
 InitStack(S);  
 BiTree cur;//当前指针  
 BiTree pre=NULL;//前一个指针  
 Push(S,T);//根节点入栈  
 while(!StackEmpty(S))//只要栈不空  
 \{//如果当前没有左孩子和右孩子，或者说当前节点是已经访问过的  
  cur=GetTop(S,T);//每次都取栈顶元素  
  if ((cur->lchild==NULL && cur->rchild==NULL)||  
   (pre!=NULL && (pre==cur->lchild)|| pre==cur->rchild))  
  \{  
   Visit(cur->data);  
   Pop(S,T);//出栈下移栈顶指针，准备下次访问  
   pre=cur;//记录走过的路径  
  \}  
  else  
  \{//保证压栈的顺序为先右后左，才能左根右的输出  
   if (cur->rchild!=NULL)  
    Push(S,cur->rchild);  
   if (cur->lchild!=NULL)  
    Push(S,cur->lchild);  
  \}  
 \}**

**层序遍：**

**算法描述：层序遍历需要用到队列，访问顺序是子根，左孩子1，右孩子1，左孩子1的左孩子和右孩子，右孩子1的左孩子和右孩子.............由于队列具有先进先出的特点，所以我们入队的顺序就是访问结点的顺序。只要哪个孩子不空就入队哪个孩子，出队时直接出队就行，顺序就会保持。**

**void LevelOrderTraverse(BiTree T,void(\*Visit)(TElemType))  
\{  
 LinkQueue q;  
 QElemType a;  
 if(T)  
 \{  
  InitQueue(q); // 初始化队列q  
  EnQueue(q,T); // 根指针入队  
  while(!QueueEmpty(q)) // 队列不空  
  \{  
   DeQueue(q,a); // 出队元素(指针),赋给a  
   Visit(a->data); // 访问a所指结点  
   if(a->lchild!=NULL) // a有左孩子  
    EnQueue(q,a->lchild); // 入队a的左孩子  
   if(a->rchild!=NULL) // a有右孩子  
    EnQueue(q,a->rchild); // 入队a的右孩子  
  \}  
  printf("\\n");  
   \}  
\}**

**下面是代码的全部实现：**

**其中头文件head.h为如下定义：**

\#include<string.h>  
\#include<ctype.h>  
\#include<malloc.h> // malloc()等  
\#include<limits.h> // INT\_MAX等  
\#include<stdio.h> // EOF(=^Z或F6),NULL  
\#include<stdlib.h> // atoi()  
\#include<io.h> // eof()  
\#include<math.h> // floor(),ceil(),abs()  
\#include<process.h> // exit()  
\#include<iostream.h> // cout,cin  
// 函数结果状态代码  
\#define TRUE 1  
\#define FALSE 0  
\#define OK 1  
\#define ERROR 0  
\#define INFEASIBLE -1  
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等  
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

#include "head.h"//头文件
    //树结构定义
    typedef char TElemType;
    TElemType Nil=' ';
    typedef struct BiTNode
    {
    	TElemType data;
    	BiTNode *lchild,*rchild; // 左右孩子指针
    }BiTNode,*BiTree;
    /*-------栈操作开始-------*/
    typedef BiTree SElemType;   //栈元素为二叉树指针
    #define STACK_INIT_SIZE 10 // 存储空间初始分配量
    #define STACK_INCREMENT 2 // 存储空间分配增量
    struct SqStack
    {
    	SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
    	SElemType *top; // 栈顶指针
    	int stacksize; // 当前已分配的存储空间，以元素为单位
    }; // 顺序栈
    
    void InitStack(SqStack &S)
    { // 构造一个空栈S
    	if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))
    		exit(OVERFLOW); // 存储分配失败
    	S.top=S.base;
    	S.stacksize=STACK_INIT_SIZE;
    }
    
    void Push(SqStack &S,SElemType e)
    { // 插入元素e为新的栈顶元素
    	if(S.top-S.base>=S.stacksize) // 栈满，追加存储空间
    	{
    		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
    		if(!S.base)
    			exit(OVERFLOW); // 存储分配失败
    		S.top=S.base+S.stacksize;
    		S.stacksize+=STACK_INCREMENT;
    	}
    	*(S.top)++=e;
    }
    
    Status Pop(SqStack &S,SElemType &e)
    { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
    	if(S.top==S.base)
    		return ERROR;
    	e=*--S.top;
    	return OK;
    }
    
    BiTree GetTop(SqStack S,SElemType &e)
    { // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
    	if(S.top>S.base)
    	{
    		e=*(S.top-1);
    		return e;
    	}
    	else
    		return NULL;
    }
    
    Status StackEmpty(SqStack S)
    { // 若栈S为空栈，则返回TRUE，否则返回FALSE
    	if(S.top==S.base)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    /*---------栈操作结束--------------*/
    
    /*---------队操作开始----------*/
    typedef BiTree QElemType;
    typedef struct QNode
    {
    	QElemType data;
    	QNode *next;
    }*QueuePtr;
    
    struct LinkQueue
    {
    	QueuePtr front,rear; // 队头、队尾指针
    };
    
    void InitQueue(LinkQueue &Q)
    { // 构造一个空队列Q
    	if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
    		exit(OVERFLOW);
    	Q.front->next=NULL;
    }
    
    Status QueueEmpty(LinkQueue Q)
    { // 若Q为空队列，则返回TRUE，否则返回FALSE
    	if(Q.front->next==NULL)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    void EnQueue(LinkQueue &Q,QElemType e)
    { // 插入元素e为Q的新的队尾元素
    	QueuePtr p;
    	if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败
    		exit(OVERFLOW);
    	p->data=e;
    	p->next=NULL;
    	Q.rear->next=p;
    	Q.rear=p;
    }
    
    Status DeQueue(LinkQueue &Q,QElemType &e)
    { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
    	QueuePtr p;
    	if(Q.front==Q.rear)
    		return ERROR;
    	p=Q.front->next;
    	e=p->data;
    	Q.front->next=p->next;
    	if(Q.rear==p)
    		Q.rear=Q.front;
    	free(p);
    	return OK;
    }
    /*---------队操作结束----------*/
    
    /*------二叉树操作开始------*/
    
    void visitT(TElemType e)
    {
    	printf("%c ",e);
     }
    void PreOrderTraverse(BiTree T,void(*Visit)(TElemType))
    { //递归先序
    	if(T) // T不空
    	{
    		Visit(T->data); // 先访问根结点
    		PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
    		PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
    	}
    }
    void PreOrderTraverse1(BiTree T,void (*Visit)(TElemType))
    {//非递归(利用栈)实现先序遍历
    	SqStack S;
    	InitStack(S);
    	while(T||!StackEmpty(S))
    	{
    		if (T)
    		{  
    		  Visit(T->data);//第一个访问的永远是根，只要非空就输出
    	      Push(S,T);//入栈根结点,若分支为空，方便返回路径
    	      T=T->lchild;//遍历左分支
    		}
    		else//左子树为空，说明已经遍历完根和左了，该右了
    		{
    			Pop(S,T);//返回到栈顶元素
    			T=T->rchild;
    		}
    	}
    }
    void InOrderTraverse(BiTree T,void(*Visit)(TElemType))
    { //递归中序
    	if(T)
    	{
    		InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
    		Visit(T->data); // 再访问根结点
    		InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
    	}
     }
    void InOrderTraverse1(BiTree T,void (*Visit)(TElemType))
    {//非递归(利用栈)实现中序遍历
    	SqStack S;
    	InitStack(S);
    	while(T||!StackEmpty(S))
    	{
    		if (T)
    		{
    			Push(S,T);//入栈根结点
    			T=T->lchild;//遍历左分支
    		}
    		else
    		{
    			Pop(S,T);
    			Visit(T->data);
    			T=T->rchild;
    		}
    	}
    }
    void PostOrderTraverse(BiTree T,void(*Visit)(TElemType))
    { //递归中序
    	if(T)
    	{
    		PostOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
    		PostOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
    		Visit(T->data); // 再访问根结点
    	}
     }
    //非递归后序遍历
    void PostOrderTraverse1(BiTree T,void(*Visit)(TElemType))
    {//对于任意节点，先将其入栈。如果它没有左孩子和右孩子则直接访问它；若它有
    	// 左孩子或者右孩子，但是已经被访问过了(是否访问用两个指针之间的关系判断)也可以访问它；
    	//如果都不是上述两种情况，则先访问它的右孩子，再访问它的左孩子，以此来保证能够左、右、根的输出。
    	SqStack S;
    	InitStack(S);
    	BiTree cur;//当前指针
    	BiTree pre=NULL;//前一个指针
    	Push(S,T);//根节点入栈
    	while(!StackEmpty(S))//只要栈不空
    	{//如果当前没有左孩子和右孩子，或者说当前节点是已经访问过的
    		cur=GetTop(S,T);//每次都取栈顶元素
    		if ((cur->lchild==NULL && cur->rchild==NULL)||
    			(pre!=NULL && (pre==cur->lchild)|| pre==cur->rchild))
    		{
    			Visit(cur->data);
    			Pop(S,T);//出栈下移栈顶指针，准备下次访问
    			pre=cur;//记录走过的路径
    		}
    		else
    		{//保证压栈的顺序为先右后左，才能左右根的输出
    			if (cur->rchild!=NULL)
    				Push(S,cur->rchild);
    			if (cur->lchild!=NULL)
    				Push(S,cur->lchild);
    		}
    	}
    }
    void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType))
    {
    	LinkQueue q;
    	QElemType a;
    	if(T)
    	{
    		InitQueue(q); // 初始化队列q
    		EnQueue(q,T); // 根指针入队
    		while(!QueueEmpty(q)) // 队列不空
    		{
    			DeQueue(q,a); // 出队元素(指针),赋给a
    			Visit(a->data); // 访问a所指结点
    			if(a->lchild!=NULL) // a有左孩子
    				EnQueue(q,a->lchild); // 入队a的左孩子
    			if(a->rchild!=NULL) // a有右孩子
    				EnQueue(q,a->rchild); // 入队a的右孩子
    		}
    		printf("\n");
       }
    }
    void InitBiTree(BiTree &T)
    { // 操作结果：构造空二叉树T
    	T=NULL;
    }
    
    void CreateBiTree(BiTree &T)
    { //递归先序生成二叉树
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch==Nil) // 空
    		T=NULL;
    	else
    	{
    		T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
    		if(!T)
    			exit(OVERFLOW);
    		T->data=ch;
    		CreateBiTree(T->lchild); // 构造左子树
    		CreateBiTree(T->rchild); // 构造右子树
    	}
     }
    /*-------二叉树操作结束----------*/
    
    
    
    /************************************************************************/
    /*                              主函数开始                              */
    /************************************************************************/
    void main()
    {    
    	BiTree T;
    	InitBiTree(T);
    	printf("先序输入构造二叉树:\n");
    	CreateBiTree(T);
    	printf("利用队----层序遍历----二叉树:\n");
        LevelOrderTraverse(T,visitT);
    	printf("\n");
    	printf("递归法---先序遍历---二叉树:\n");
    	PreOrderTraverse(T,visitT);
    	printf("\n");
    		printf("非递归---先序遍历---二叉树:\n");
    		PreOrderTraverse1(T,visitT);
    		printf("\n");
    			printf("递归法---中序遍历---二叉树:\n");
    			InOrderTraverse(T,visitT);
    			printf("\n");
    				printf("非归法---中序遍历---二叉树:\n");
    				InOrderTraverse(T,visitT);
    				printf("\n");
    					printf("递归法---后序遍历---二叉树:\n");
    					PostOrderTraverse(T,visitT);
    					printf("\n");
    						printf("非递归---后序遍历---二叉树:\n");
    						PostOrderTraverse1(T,visitT);
    						printf("\n");
    }

![1357180359_5454.png][]

[1357180359_5454.png]: https://img-my.csdn.net/uploads/201301/03/1357180359_5454.png