jake1036

面试100 12从上向下遍历二叉树

            从上向下遍历二叉树

  问题描述：
      该题要求，从根节点开始向下遍历树，且同层之间从左向右一次遍历。
  分析：
      这一题目实质上，就是树的广度遍历。因为树实质上是一种特殊的图。
  代码如下：
     

#include <iostream>
#include <queue>
 using namespace std ;
  template <class T>
  struct BinaryTree{
     T data ;
     BinaryTree * lc ;
     BinaryTree * rc ;             
  } ;
 
 BinaryTree <int> * root ;
  const int N = 7 ;
  
  template <class T>
  void buildTree(T x) //正规的二叉查找树 
  {
    if(root == 0)
    {
        root = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;
        root->lc = 0 ;
        root->rc = 0 ;
        root->data = x ;
        return ;
    }
    
    BinaryTree <T> * p = root ;
    BinaryTree <T> * q = root ;
    
    while(p)
    {
       q = p ;      
       if(p->data <= x)
           p = p->rc ;
       else
           p = p->lc ;              
    }
    
    p = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;
    p->data = x ;
    p->lc = 0 ;
    p->rc = 0 ;
    
    if(q->data > x)
      q->lc = p ;
    else
      q->rc = p ;     
  }  
 
 template <class T>
  void postOrder(BinaryTree <T> * p)
  {
      if(p)
      {
           cout<<p->data<<" " ;
        postOrder(p->lc) ;   
                     
        postOrder(p->rc) ;
      } 
       
  }
  
  //template <class T>//使用广度优先遍历算法获取 
   void bfs(BinaryTree <int> * p , queue <BinaryTree<int> *> Q)
   {
      while(!Q.empty())  
        {
          BinaryTree <int> * tops = Q.front() ; //取头部 
          cout<<tops->data<<" ";
          Q.pop() ;
          if(tops->lc)              
             Q.push(tops->lc) ;
          if(tops->rc)              
             Q.push(tops->rc) ;
                                                 
        }
        
   }
  
  
 int main()
 {
   int i ;
       int a[] = {8 ,6 ,10 , 5 ,7, 9 , 11}  ;
  
   for(i = 0 ; i < N ; i++)
        buildTree(a[i]) ;
        
    postOrder(root) ;
       cout<<endl ; 
    
    queue<BinaryTree<int>*> que ;
    que.push(root) ;
    bfs(root , que) ;
    system("pause");    
  
  return 0 ;    
 } 
 

 

posted on 2011-05-17 09:09 kahn 阅读(192) 评论(0)  编辑 收藏 引用


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