jake1036

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

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

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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理