二叉樹遍歷遞歸與非遞歸實現

說明：本文僅供學習交流，轉載請標明出處，歡迎轉載！

二叉樹遍歷是二叉樹中非常基礎的部分，也是學習二叉樹必須熟練掌握的部分，下面我們先給出二叉樹三種遍歷方式的定義，並通過舉例來說明二叉樹遍歷的過程。

二叉樹的遍歷分為：前序遍歷（也叫先序遍歷）、中序遍歷、後序遍歷。所謂前、中、後都是根據當前子樹根結點相對左右孩子的位置而言，也就是說：

前序遍歷：根結點在前，即：根 ----->左------->右；

中序遍歷：根結點在中間，即：左------>根------>右；

後序遍歷：根結點在最後，即：左------->右------根。

從上面的定義可以看出，這三種遍歷中，左子樹總是比右子樹優先訪問。

下圖是我們給一個例子：

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

代碼如下：

#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;
}

測試結果如下：