說明：本文僅供學習交流，轉載請標明出處，歡迎轉載！
二叉樹遍歷是二叉樹中非常基礎的部分，也是學習二叉樹必須熟練掌握的部分，下面我們先給出二叉樹三種遍歷方式的定義，並通過舉例來說明二叉樹遍歷的過程。
二叉樹的遍歷分為：前序遍歷（也叫先序遍歷）、中序遍歷、後序遍歷。所謂前、中、後都是根據當前子樹根結點相對左右孩子的位置而言，也就是說：
前序遍歷：根結點在前，即：根 ----->左------->右；
中序遍歷：根結點在中間，即：左------>根------>右；
後序遍歷：根結點在最後，即：左------->右------根。
從上面的定義可以看出，這三種遍歷中，左子樹總是比右子樹優先訪問。
下圖是我們給一個例子：
二叉樹的常見問題及其解決程序 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;
}
測試結果如下：
