二叉树的遍历详述

所谓二叉树的遍历，就是按照某种次序访问二叉树中的每个节点，而且每个节点仅访问一次的过程。以L、N、R分别表示遍历左子树、访问根节点、遍历右子树，则可有NLR、LRN、NRL、RNL、RLN等6中遍历方式。若限定先左后右，则只有三种遍历，分别成为先序遍历、中序遍历和后序遍历，另外还有一种按层序的遍历方式。下面我们采用一个例子来完成的描述二叉树的遍历过程：

这是一个递归生成的二叉树，’#’表示节点为空。

#include<iostream>
#include<cstdlib>
#define MaxSize 30
using namespace std;
typedef char ElementType;
typedef struct node
{
    ElementType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;
void CreateBTree(BTNode* &T){ 
 //按先序输入二叉树中结点的值（一个字符），空格字符代表空树， 
 //构造二叉树表表示二叉树T。 
 char ch; 
 if((ch=getchar())=='#')T=NULL;//其中getchar（）为逐个读入标准库函数 
 else{ 
  T=(BTNode*)malloc(sizeof(BTNode));//产生新的子树 
  T->data=ch;//由getchar（A）逐个读入来 
  CreateBTree(T->lchild);//递归创建左子树 
  CreateBTree(T->rchild);//递归创建右子树 
 } 
}//CreateTree 
void PreOrder(BTNode *b)
{
    if(b!=NULL)
    {
        cout<<b->data<<" ";
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }
}
//先序非递归算法
void PreOrder1(BTNode *b)
{
    BTNode *St[MaxSize],*p;
    int top=-1;
    if(b!=NULL)
    {
        top++;
        St[top]=b;
        while(top!=-1)
        {
            p=St[top];
            top--;
            cout<<p->data<<" ";
            if(p->rchild!=NULL)
            {
                top++;
                St[top]=p->rchild;
            }
            if(p->lchild!=NULL)
            {
                top++;
                St[top]=p->lchild;
            }
        }
        cout<<endl;
    }
}
//中序非递归算法
void InOrder1(BTNode *b)
{
    BTNode *St[MaxSize],*p;
    int top=-1;
    if(b!=NULL)
    {
        p=b;
        while(top>-1||p!=NULL)
        {
            while(p!=NULL)
            {
                top++;
                St[top]=p;
                p=p->lchild;
            }
            if(top>-1)
            {
                p=St[top];
                top--;
                cout<<p->data<<" ";
                p=p->rchild;
            }
        }
        cout<<endl;
    }
}
void InOrder(BTNode *b)
{
    if(b!=NULL)
    {
        InOrder(b->lchild);
        cout<<b->data<<" ";
        InOrder(b->rchild);
    }
}
void PostOrder(BTNode *b)
{
    if(b!=NULL)
    {
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        cout<<b->data<<" ";
    }
}
//后序递归算法
void PostOrder1(BTNode *b)
{
    BTNode *St[MaxSize];
    BTNode *p=b,*q;
    int flag,top=-1;
    if(b!=NULL)
    {
        do
        {
            while(p!=NULL)
            {
                top++;
                St[top]=p;
                p=p->lchild;
            }
            q=NULL;
            flag=1;
            while(top!=-1&&flag==1)
            {
                p=St[top];
                if(p->rchild==q)
                {
                    cout<<p->data<<" ";
                    top--;
                    q=p;
                }else
                {
                    p=p->rchild;
                    flag=0;
                }
            }
        }while(top!=-1);
        cout<<endl;
    }
}
//层序遍历
void LevelOrder(BTNode *b)
{
    BTNode *p;
    BTNode *qu[MaxSize];
    int front,rear;
    front=rear=0;
    rear++;
    qu[rear]=b;
    while(front!=rear)
    {
        front=(front+1)%MaxSize;
        p=qu[front];
        cout<<p->data<<" ";
        if(p->lchild!=NULL)
        {
            rear=(rear+1)%MaxSize;
            qu[rear]=p->lchild;
        }
        if(p->rchild!=NULL)
        {
            rear=(rear+1)%MaxSize;
            qu[rear]=p->rchild;
        }
    }
}
int main()
{
    BTNode *b;
    CreateBTree(b);
    cout<<"先序遍历结果:"<<endl;
    //PreOrder(b);
    PreOrder1(b);
    cout<<"中序遍历结果:"<<endl;
    //InOrder(b);
    InOrder1(b);
    cout<<endl;
    cout<<"后序遍历结果:"<<endl;
    //PostOrder(b);
    PostOrder1(b);
    cout<<"层序遍历结果："<<endl;
    LevelOrder(b);
    return 0;
}

我们采用两种方式遍历二叉树，一种是递归方式，一种采用非递归方式（栈和队列）。

运行程序：

各种遍历得到的结果如图所示：

至此二叉树的遍历就已经讲完了，希望对大家有所帮助！