二叉树遍历算法总结（递归与非递归）

一：前言
二叉树的遍历方法分四种:前序，中序，后序以及层次遍历。
其中，前中后遍历方法的实现分递归和非递归，非递归遍历的实现需要借助于栈。
实际上，递归的调用就是一种栈的实现，所以，非递归遍历就需要人工借助栈结构来实现。
而层次遍历需要借助队列。

二：前中后序遍历
递归遍历：
递归遍历的思想和方法很简单，通过调整输出语句来实现前，中，后三种遍历。

代码如下：

void show(BiTree T)
{
    if(T)
    {
        printf("%c ",T->data);//修改这三个语句的顺序分别实现三种遍历
        show(T->lchild);
        show(T->rchild);
    }
}

非递归遍历：

总结了5总不同的非递归遍历算法，四种思路，都需要借助栈来完成。

第一种遍历算法：
算法的思路：
1.从根结点开始，若当前结点的左孩子不为空，则遍历左孩子并进栈。
2.结点的左孩子为空时，出栈并遍历当前结点的右孩子结点
3.以右孩子结点为根结点，又沿着左孩子不断遍历，重复1.2步骤
此算法为前序遍历

void preorder1(BiTree T)//前序遍历1
{
    LinkStack s;
    InitStack(&s);
    BiTree temp;
    temp = T;
    while(temp || !EmptyStack(s)) //第一个条件temp是为了进入循环
    {
        if(temp)    //一直遍历左子树到底部
        {
            Push(&s,temp);
            printf("%c",temp->data);
            temp = temp->lchild;
        }
        else      //lchild为空，跳转到rchild
        {
            Pop(&s,&temp);
            temp = temp->rchild;
        }
    }
}

第二种遍历算法：

算法思路与第一种遍历算法一致，只是改变了遍历语句的位置，不是在进栈的时候输出，而是在出栈的时候输出，前序遍历则为中序遍历

1.从根结点开始，当前结点左孩子不为空时，左孩子进栈。

2.当前结点左孩子为空时，出栈并输出当前结点，然后跳转该结点的右孩子

3.重复1，2步骤直到栈空

void inorder(BiTree T)//中序遍历 
{
    LinkStack s;
    InitStack(&s);
    BiTree temp = T;
    while(temp || !EmptyStack(s))
    {
        if(temp)
        {
            Push(&s,temp);
            temp = temp->lchild;
        }
        else
        {
            Pop(&s,&temp);
            printf("%c ",temp->data); //出栈时输出则为中序遍历
            temp = temp->rchild;
        }
    }
}

第三种遍历算法：

此种算法为前序遍历

算法思路：1.先将根结点入栈

　　　2.出栈栈顶并输出，先入栈当前结点的右孩子结点，在入栈当前结点的左孩子结点

                  3.重复第2步直到栈空

void preorder2(BiTree T)
{
    LinkStack s;
    InitStack(&s);
    BiTree temp = T;
    Push(&s,temp);
    while(!EmptyStack(s))
    {
        Pop(&s,&temp);            //出栈顶并输出
        printf("%c ",temp->data);
        if(temp->rchild)        //入栈右孩子
        {
            Push(&s,temp->rchild);
        }
        if(temp->lchild)        //入栈左孩子
        {
            Push(&s,temp->lchild);
        }
    }
}

第四种遍历算法：

后序遍历的非递归实现比较复杂，要保证输出当前结点时左右孩子结点已经输出（或者左右孩子为空）

即每输出一个结点要满足以下两个条件之一：

 　　　　1.此结点的左右孩子为空

2.此结点的左右孩子已经遍历

算法思路：1.先将根结点入栈，以栈空为循环停止的条件

　　　2. 用结点指针pre记录上一个输出结点地址，cur记录当前结点地址

　　　　　2.1 当前结点的左右孩子为空时，或者pre记录的结点为当前结点的左（右）孩子时，出栈并输出当前结点，并更新pre

　　　　　2.2 否则按照右孩子，左孩子的顺序入栈

　　　3.循环第2步直到栈空

void postorder(BiTree T)
{
    BiTree pre,cur;
    LinkStack s;
    InitStack(&s);
    cur = pre = T;
    Push(&s,cur);
    while(!EmptyStack(s))
    {
        GetTop(s,&cur);            //当前结点的左右孩子都为空，pre为cur的左孩子或者右孩子时，出栈并输出当前结点
        if((cur->lchild == NULL && cur->rchild == NULL) || cur->lchild == pre || cur->rchild == pre)
        {
            Pop(&s,&cur);
            printf("%c ",cur->data);
            pre = cur;            //更新当前结点
        }
        else
        {
            if(cur->rchild)        //否则入栈右孩子，左孩子
            {
                Push(&s,cur->rchild);
            }
            if(cur->lchild)
            {
                Push(&s,cur->lchild);
            }
        }
    }
}

第五种遍历算法：

此种非递归遍历算法思想可以像递归遍历一样通过修改部分的顺序做到：前中后序三种遍历。

不过便利往往带来的是代码结构上的复杂，此种算法所借助的栈和上面的遍历算法借助的栈不同。

上面的算法使用的栈存储的数据时一个二叉树结点指针，而此算法栈储存的是一个结构体

栈数据类型定义：

typedef struct {        // 栈数据定义
        BiTree ptr;
        int task;
}Datatype;

                其中，task有两个值，0表示访问，1表示遍历。所有结点的task的初始值为1

算法思路：

1.根结点先进栈，task初始化为1

2.出栈，若当前结点的task为0 则访问当前结点，task为1，则修改task为0，并按想要的遍历顺序入栈左右孩子结点。

　　例如：若中序遍历，则先入栈右孩子结点，当前结点，左孩子结点。（其他遍历顺序则改一下入栈顺序）

3.直到栈空，停止循环

 　　　　　此算法完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct binode{      //二叉树结点定义
        char data;
        struct binode * lchild,*rchild;
}BiNode,*BiTree;

//非递归遍历所要用到的栈
#define MAX 50
typedef struct {        // 栈数据定义
        BiTree ptr;
        int task;
}Datatype;

typedef struct {
    Datatype * arr;
    int top;
    int stacksize;
}SqStack;//顺序栈

void InitStack(SqStack *S) //初始化字符栈
{
    S->arr = (Datatype*)malloc(sizeof(Datatype)*MAX);
    if(S->arr == NULL)
    {
        printf("初始化失败....\n");
        exit(0);
    }
    S->top = -1;
    S->stacksize = MAX;
}

int Push(SqStack *S,Datatype ch)//进栈(字符栈)
{
    Datatype *p;
    int select;
    if(S->top+1 == S->stacksize)    //先判断栈是否已满
    {
        printf("栈的容量已满，无法进栈");
        return 0;
    }
    S->arr[++S->top] = ch;
    return 1;
}

int Pop(SqStack *S,Datatype *ch)//出栈（字符栈）
{
    if(S->top < 0)
    {
        printf("栈为空....\n");
        return 0;
    }
    *ch = S->arr[S->top];
    S->top--;
    return 1;
}

int GetTopStack(SqStack S,Datatype *ch) //取字符栈顶
{
    if(S.top < 0)
    {
        return 0;
    }
    *ch = S.arr[S.top];
    return 1;
}

int EmptyStack(SqStack S) //判断栈空
{
    if(S.top < 0)
    {
        return 1;
    }
    return 0;
}

/******************************栈结束*********************************/

void CreateBitree(BiTree *T)  //前序创建二叉树
{
  char ch;
  scanf(" %c",&ch);
  getchar();
  if(ch == '#')
  {
      *T = NULL;
  }
  else
  {
    *T =(BiTree)malloc(sizeof(BiNode));
    (*T)->data = ch;
    CreateBitree(&((*T)->lchild));
    CreateBitree(&((*T)->rchild));
  }
}
   

void View(BiTree T)//非递归遍历  实现不同的遍历顺序修改第一个else语句的结点入栈顺序
{
    Datatype temp;
    BiTree p;
    temp.task = 1;
    temp.ptr = T;
    SqStack S;
    InitStack(&S);
    if(T == NULL) return ;
    Push(&S,temp);
    while(!EmptyStack(S))
    {
        Pop(&S,&temp);      //先把根出栈
        p = temp.ptr;          //记录根地址
        if(temp.task == 0)    //task为0  则访问输出
        {
            printf("%c ",temp.ptr->data);
        }
        else                        //task为1 则将孩子进栈
        {
            if(p->rchild)              //右孩子进栈
            {
                temp.task = 1;
                temp.ptr = p->rchild;
                Push(&S,temp);
            }
            temp.task = 0;          //根的状态由遍历改为访问，然后进栈
            temp.ptr = p;
            Push(&S,temp);
            if(p->lchild)              //左孩子进栈
            {
                temp.ptr = p->lchild;
                temp.task = 1;
                Push(&S,temp);
            }
        }
    }
    printf("\n");
}

int main()//二叉树创建：a b d # # e # # c f # # g # #
{
    BiTree T;
    CreateBitree(&T);
    printf("中序遍历为：");
    View(T);
    return 0;
}

三：层次遍历

层次遍历需要使用队列

算法思路比较结单，即对每个结点按左孩子，右孩子的顺序进队列即可，出队列时访问即为层次遍历。

此处就不赘述算法思路步骤了，直接上代码。

void DispLayer(BiTree T) //层次遍历
{
    LinkQueue rear;                //装二叉树的结点地址的队列
    BiTree view = NULL;
    InitQueue(&rear);
    if(T == NULL)
    {
        return ;
    }
    EnQueue(&rear,T);              //先将总树根地址装进去
    while(!EmptyQueue(rear))    //队列为空则遍历完毕
    {
        DeQueue(&rear,&view);          //小树根出队列
        printf("%c ",view->data);          //输出小树根
        if(view->lchild)                          //小树根左右孩子存在则入队列
        {
            EnQueue(&rear,view->lchild);
        }
        if(view->rchild)
        {
            EnQueue(&rear,view->rchild);
        }
    }
    printf("\n");
}

以上即为二叉树的各种遍历算法。