樹的前中序遞歸非遞歸遍歷

                                    樹的前序與中序遍歷遞歸非遞歸遍歷

     1樹的中序遍歷非遞歸算法思想：

         每次都將左子樹入棧，一旦發現左子樹為空，則作出棧處理。打印該節點的值，然后右節點若不為空，則入棧處理。   
     具體偽代碼如下：

   void BT_InOrderNoRec(pTreeT root)
{
    stack<treeT *> s;
    while ((NULL != root) || !s.empty())
    {
        if (NULL != root)
        {
            s.push(root);
            root = root->left;
        }
        else
        {
            root = s.top();
            visit(root);
            s.pop();
            root = root->right;
        }
    }
}




自己實現代碼（比較粗糙）:

  void midStack(const int * a , int n)
  {
     int i = 1 , top = 0;
     int stack[n] ;
     memset(stack , 0 , sizeof(stack)) ;   
     stack[top++] = 1 ; 
     while(top > 0)
     {
       int j = i * 2 ;                                      
       while(j <= n && a[j] != 0)
       {       
         stack[top++] = j ; //左子樹入棧     
         j *= 2 ;   
       }                                                
        i = stack[--top] ;  
        if(i <= n && a[i] !=  0)  
          cout<<a[i]<<" " ; //輸出根 
        
        if(a[2 * i + 1 ] !=0 && 2 * i + 1 <= n)                 
          stack[top++] = 2 * i + 1 ;
        
          i = 2 * i + 1 ; //轉向右子樹 
                                                 
            
     }  
       
       
  }

2 非遞歸前序遍歷

算法思想：

順序訪問每個節點，然后將右節點插入棧中。然后將當前節點變換為左節點。知道當前節點為空，才會作出棧操作。
偽代碼如下：
 void BT_PreOrderNoRec(pTreeT root)
{
    stack<treeT *> s;

    while ((NULL != root) || !s.empty())
    {
        if (NULL != root)
        {
            visit(root);
            s.push(root);
            root = root->left;
        }
        else
        {
            root = s.top();
            s.pop();
            root = root->right;
        }
    }
}

自己實現的代碼：

  void preStack(const int * a , int n)
  {
     int i = 1 , top = 0;  
     int stack[n] ;
     stack[top++] = 1 ; 
      
  while(top > 0)
  {    
     i = stack[--top] ;   
     while( i <= n && a[i] != 0)
     {
       cout<<a[i]<<" " ; //輸出跟節點                                
        i = i * 2 ; //轉到左節點     
        stack[top++] = i + 1 ;           // 將左右子樹入棧                     
     }      
   }
                  
  }

posted on 2011-04-10 10:42 kahn 閱讀(306) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關