二叉树遍历递归与非递归实现

说明：本文仅供学习交流，转载请标明出处，欢迎转载！

二叉树遍历是二叉树中非常基础的部分，也是学习二叉树必须熟练掌握的部分，下面我们先给出二叉树三种遍历方式的定义，并通过举例来说明二叉树遍历的过程。

二叉树的遍历分为：前序遍历（也叫先序遍历）、中序遍历、后序遍历。所谓前、中、后都是根据当前子树根结点相对左右孩子的位置而言，也就是说：

前序遍历：根结点在前，即：根 ----->左------->右；

中序遍历：根结点在中间，即：左------>根------>右；

后序遍历：根结点在最后，即：左------->右------根。

从上面的定义可以看出，这三种遍历中，左子树总是比右子树优先访问。

下图是我们给一个例子：

代码如下：

#include<iostream>
#include<stack>
using namespace std;
struct Node
{
 int data;
 Node *left;
 Node *right;
 bool FirstVisited;
 Node(int data)
 {
  this->data=data;
  this->left=NULL;
  this->right=NULL;
  FirstVisited=true;
 }
};
class BinTree
{
public:
 Node *root;
 Node* CreateTree();
 void preOrder(Node *r);//递归实现先序遍历
 void preOrder1(Node *r);//先序遍历非递归实现

 void InOrder(Node *r);//递归实现中序遍历
 void InOrder1(Node *r);//中序遍历的非递归实现

 void PostOrder(Node *r);//递归实现后续遍历
 void PostOrder1(Node *r);//后序遍历非递归算法
};

Node* BinTree::CreateTree()//创建一棵二叉树
{
 Node *p1=new Node(1);
 Node *p2=new Node(2);
 Node *p3=new Node(3);
 Node *p4=new Node(4);
 Node *p5=new Node(5);
 Node *p6=new Node(6);
 Node *p7=new Node(7);
 Node *p8=new Node(8);
 Node *p9=new Node(9);
 p1->left=p2;
 p1->right=p3;
 p2->left=p4;
 p2->right=p5;
 p5->left=p6;
 p3->left=p7;
 p3->right=p8;
 p8->right=p9;
 root=p1;
 return p1;
}

void BinTree::preOrder(Node *r)//递归实现先序遍历
{
 if(r==NULL)
 {
  return ;
 }
 else
 {
  cout<<r->data<<" ";
  preOrder(r->left);
  preOrder(r->right);
 }
}
void BinTree::preOrder1(Node *root)//先序遍历的非递归实现
{
 if(root!=NULL)
 {
  Node *p=root;
  stack<Node*>s;
  while(p!=NULL ||!s.empty())
  {
   while(p)
   {
    cout<<p->data<<" ";
    s.push(p);
    p=p->left;
   }
   if(!s.empty())
   {
    if(s.top()->right)//如果最左端的结点有右孩子
    {
     p=s.top()->right;
    }
    s.pop();//出栈
   }
  }
 }
 cout<<endl;
}

void BinTree::InOrder(Node *r)//递归实现中序遍历
{
 if(r==NULL)
 {
  return ;
 }
 else
 {
  InOrder(r->left);
  cout<<r->data<<" ";
  InOrder(r->right);
 }
}

void BinTree::InOrder1(Node *r)//中序遍历的非递归实现
{
 if(r!=NULL)
 {
  Node *p=r;
  stack<Node*>s;
  while(p || !s.empty())
  {
   while(p)
   {
    s.push(p);
    p=p->left;
   }
   if(!s.empty())
   {
    Node *q=s.top();
    cout<<q->data<<" ";
    s.pop();
    if(q->right)
    {
     p=q->right;
    }
   }
  }
 }
 cout<<endl;
}

void BinTree::PostOrder(Node *r)//递归实现后序遍历
{
 if(r==NULL)
 {
  return ;
 }
 else
 {
  PostOrder(r->left);
  PostOrder(r->right);
  cout<<r->data<<" ";
 }
}

void BinTree::PostOrder1(Node *r)//后序遍历的非递归实现
{
 if(r==NULL)
  return ;
 Node *p=r;
 stack<Node*>s;
 while(p || !s.empty())
 {
  while(p)//先将所有的左孩子压入栈中
  {
   s.push(p);
   p=p->left;
  }
  if(!s.empty())
  {
   Node *q=s.top();
   if(q->FirstVisited)//如果是第一次访问
   {
    q->FirstVisited=false;
    p=q->right;
   }
   else//如果是第二次访问，则输出
   {
    cout<<q->data<<" ";
    s.pop();
    p=NULL;//给p一条出路
   }

  }
 }
}
int main()
{
 BinTree t;
 t.CreateTree();//创建二叉树
 /////////////三种遍历方式//////////////
 cout<<"先序遍历:";
 t.preOrder(t.root);//先序遍历
 cout<<endl<<"先序遍历非递归实现算法:";
 t.preOrder1(t.root);
 cout<<endl;

 cout<<"中序遍历:";
 t.InOrder(t.root);//中序遍历
 cout<<endl<<"中序遍历非递归算法:";
 t.InOrder1(t.root);
 cout<<endl;

 cout<<"后序遍历:";
 t.PostOrder(t.root);//后序遍历
 cout<<endl<<"后序遍历的非递归算法:";
 t.PostOrder1(t.root);//后序遍历的非递归算法
 cout<<endl;
 return 0;
}

测试结果如下：