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

说明：本文仅供学习交流，转载请标明出处，欢迎转载！二叉树遍历是二叉树中非常基础的部分，也是学习二叉树必须熟练掌握的部分，下面我们先给出二叉树三种遍历方式的定义，并通过举例来说明二叉树遍历的过程。二叉树的遍历分为：前序遍历（也叫先序遍历）、中序遍历、后序遍历。所谓前、中、后都是根据当前子树根结点相对左右孩子的位置而言，也就是说：前序遍历：根结点在前，即：根 ----->左------->右；中序遍历：根结点在中间，即：左------>根------>右；后序遍历：根结点在最后，即：左------->右------根。从上面的定义可以看出，这三种遍历中，左子树总是比右子树优先访问。下图是我们给一个例子：二叉树的常见问题及其解决程序 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;
}测试结果如下：本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-08/104980.htm