二叉树的遍历(C++非递归实现)

文章真是经典!

其实二叉树的遍历,这么经典的东西,我自己一直都不明白。递归算法那么简洁,让人神魂颠倒;非递归算法就那么不好理解。。。最近使劲想了一想,似乎有一些眉目了,于是记录下来。

【思想】

(1)递归思想。虽然非递归算法没有直接使用函数递归,但是使用了栈,所以实际上仍然是递归的思想。但是它递归的是那么朦胧,让人无法捉摸。可以从以下几个方面思考:首先,三个非递归遍历的算法开始都是向左走到树的最左下方的节点,并把路上遇到的节点入栈,这其实就是递归中的前一半过程。如下图所示:

二叉树的遍历(C++非递归实现)
图中上半部分表示了一个递归函数的层层深入的栈结构,下面则是模拟了将二叉树的节点入栈的过程。以此类推,从最左下的节点向上的过程就是退栈的过程,也就是图上半部分的右边。

(2)算法中cur节点的实际意义。在下面的代码中,可以看到三个算法(前、中、后序)中都有一个cur节点。这个节点表示什么含义呢?就是表示发现了一个继续入栈的机会,也就是从这个节点开始,又可以重复向左下走到底。所以中序遍历和后序遍历的开始都有一句:

while( ! s.empty() || cur != NULL )

那么当cur为空,也就是没有可以继续入栈的机会的时候,那就得靠栈中存着的余货了。

对中序遍历来说,访问完当前节点之后,如果它没有右孩子,那就没有继续入栈的机会了,只能退栈。

对后序遍历来说,检查当前节点时,如果当前节点没有右孩子或者它的右孩子刚刚被访问,那么也别无选择,只能退栈。

这也就是它们的代码中把相应的cur置为NULL的原因。

【代码】

二叉树的遍历(C++非递归实现)
#include <iostream>
#include <stack>
#include <vector>
#include <iomanip>
#include <queue>

using namespace std;

struct Node
{
      Node( const Node *t ) : data( t->data ), lChild( NULL ), rChild( NULL ) {}
      Node( int d ) : data( d ), lChild( NULL ), rChild( NULL ) {}

    struct Node* lChild;
    struct Node* rChild;
    int data;
};

void PreOrder( Node *root, void (*visit)(Node*) )  //ps:二叉树的先序遍历与二叉树的深度优先遍历什么关系呢?
{
if( root == NULL ) return;
stack<Node*> s;
Node *cur;
s.push( root );

while( !s.empty() ) 
{
   cur = s.top();   visit( cur );     s.pop();
  if( cur->rChild != NULL )   s.push( cur->rChild );
  if( cur->lChild != NULL )   s.push( cur->lChild );
}
}

void InOrder( Node *root, void (*visit)(Node*) )
{
stack<Node*> s;
Node *cur = root;

while( ! s.empty() || cur != NULL )    
{
  while( cur != NULL )
   {    s.push( cur ); cur = cur->lChild;    }

   cur = s.top(); visit( cur ); s.pop();

  if( cur->rChild == NULL )
    cur = NULL; // no current node. must pop.
  else
    cur = cur->rChild;  
}
}

void PostOrder( Node *root, void (*visit)(Node*) )
{
stack<Node*> s;
Node *cur = root;
Node *visited = NULL;

while( ! s.empty() || cur != NULL )
{
  while( cur != NULL )
   {     s.push( cur ); cur = cur->lChild; }

   cur = s.top();  // check but no visit.

  if( cur->rChild == visited || cur->rChild == NULL )
   {
    visit( cur ); s.pop();
    visited = cur;
    cur = NULL; // no current node, must pop.
   }
  else
    cur = cur->rChild;
}
}

/***************************************
* 层序遍历:跟先序遍历很像。是二叉树的广度优先搜索。
* 所以要用队列实现。
***************************************/
void LevelOrderTraverse(Node* t, void (*visit)(Node* ) )
{
    if(NULL == t)
        return;
      queue<Node*> q;
      Node* e;
      q.push(t);
    while(!q.empty())
      {
          visit(e = q.front());
          q.pop();
        if(NULL != e->lChild) q.push(e->lChild);
        if(NULL != e->rChild) q.push(e->rChild);
      }
}

//插入节点的函数
void insert(Node *&root, Node *t)
{
    if( root == NULL )
          root = new Node( t );
    else if ( t->data > root->data )
          insert( root->rChild, t );
    else if ( t->data < root->data )
          insert( root->lChild, t );
    else
          ;
}

//使用数组创建二叉树
Node* createTree( vector<int>& a)
{
    if( 0 == a.size() )
        return NULL;

      Node *root = new Node(a[0]);
      vector<int>::const_iterator iter = a.begin();
      iter++;
    for ( ; iter != a.end() ; ++iter )
      {
          Node *t = new Node( *iter );
          insert( root, t );
      }
    return root;
}

void visit(Node *t)
{
      cout<<setw(3)<<t->data<<" ";
}
二叉树的遍历(C++非递归实现)

下面是主函数:

二叉树的遍历(C++非递归实现)
int main()
{
     vector<int> a;
    for (int i = 0 ; i < 10 ; ++i )
     {
        int temp = rand()%31;//随便取了几个随机数
         a.push_back(temp);
     }

     Node* root = createTree( a );

     PreOrderTraverse(root, visit);
     cout<<endl;
     InOrderTraverse(root, visit);
     cout<<endl;
     PostOrderTraverse(root, visit);
     cout<<endl;
}
二叉树的遍历(C++非递归实现)

 

二叉树的遍历(C++非递归实现),布布扣,bubuko.com

二叉树的遍历(C++非递归实现)

原文:http://www.cnblogs.com/theCambrian/p/3624214.html

上一篇:轻量级爬虫+全文检索解决方案项目——NukeLite(2008-11-14 更新r24版 引入新线程机制)


下一篇:Phabricator安装和配置过程记录