树的前中序递归非递归遍历

                                    树的前序与中序遍历递归非递归遍历

     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 阅读(301) 评论(0)  编辑 收藏 引用 所属分类: 算法相关