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

本网站用的阿里云ECS,推荐大家用。自己搞个学习研究也不错

<

div id=”content”>说明:本文仅供学习交流,转载请标明出处,欢迎转载!

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

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

前序遍历:根结点在前,即:根 —–>左——->右;

中序遍历:根结点在中间,即:左——>根——>右;

后序遍历:根结点在最后,即:左——->右——根。

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

下图是我们给一个例子:

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

二叉树的常见问题及其解决程序 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
#include
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<data<<" ";
  preOrder(r->left);
  preOrder(r->right);
 }
}
void BinTree::preOrder1(Node *root)//先序遍历的非递归实现
{
 if(root!=NULL)
 {
  Node *p=root;
  stacks;
  while(p!=NULL ||!s.empty())
  {
   while(p)
   {
    cout<

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<data<<" ";
  InOrder(r->right);
 }
}

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

void BinTree::PostOrder1(Node *r)//后序遍历的非递归实现
{
 if(r==NULL)
  return ;
 Node *p=r;
 stacks;
 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<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;
}

测试结果如下:

未经允许不得转载:演道网 » 二叉树遍历递归与非递归实现

赞 (0)
分享到:更多 ()

评论 0

评论前必须登录!

登陆 注册