所谓二叉树的遍历，就是按照某种次序访问二叉树中的每个节点，而且每个节点仅访问一次的过程。以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;
}
我们采用两种方式遍历二叉树，一种是递归方式，一种采用非递归方式（栈和队列）。
运行程序：
各种遍历得到的结果如图所示：
至此二叉树的遍历就已经讲完了，希望对大家有所帮助！