• 2008-05-29

    [Code]做树遍历作业的王道 - [Code]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/21870279.html

          估计很多人学数据结构都要写这种东西,用非递归把LDR、LRD和Preorder三种方式遍历,于是你要无聊地写三个函数,多没意思……如果用一个函数就解决了会不会爽一点?至少脑子是在统一模式下工作一气呵成,于是便有以下结果:

    //利用简单自动机模型实现的的堆栈遍历,可以通过选择type值来选择以何种方式遍历,按先左后右顺序
    template<typename T>
    void BinaryTree<T>::StackTraverse( TreeElement<T> *now, int type)
    {
     EasyStack<TreeElement<T>*> nowStack( 50 );
     bool isContinue = true;
     int InitialState = 0, LeftNext=1, RightNext=3, BodyNext=2;
     switch (type)
     {
     case 0: //LDR
      break;
     case 1: //LRD
      InitialState = 0; LeftNext = 2; RightNext = 1; BodyNext = 3;
      break;
     case 2: //Preorder
      InitialState = 1; LeftNext = 2; RightNext = 3; BodyNext = 0;
      break;
     }

     int state = InitialState;

      while ( isContinue )
     {
      switch (state)
      {
      case 0: //判左
       if ( now->left == NULL )
        state = LeftNext;
       else
       { nowStack.Push ( now);  now = now->left ;  state = InitialState;
       }
       break;
      case 1: //输出结点
       cout<<now->body <<"  ";  state = BodyNext;
       break;
      case 2: //判右
       if ( now->right == NULL)
        state = RightNext;
       else
       { now = now->right ; state = InitialState;
       }
       break;
      case 3: //向上
       if ( nowStack.isEmpty == false )
       {
        TreeElement<T>* p = *nowStack.StackTop ;
        if ( now == (*nowStack.StackTop)->left )
         state = LeftNext;
        else
        { nowStack.Pop ( ); state = RightNext; 
        }
        now = p;
       }
       else
        isContinue = false;
       break;
      }
     }
     nowStack.Dispose ();
    }

    分享到:

    历史上的今天: