jake1036

面试100 -11二叉树镜像

       求二叉树的镜像

1 该问题实质上是将二叉树的左右两子树，进行交换。
    求查找树的映像
   即是将原来标准的二叉树，翻转180度 。
   实现方法：
  方法(1)
   首先前序遍历，标准二茶树，然后将每一个节点，按照逆查找树，插入到镜像中
  方法(2)
   前序遍历，交换左右子树,递归遍历
  方法(3) 
   使用非递归的方法，遍历左右子树

2 代码如下：
  
#include <iostream>
#include <stack>

  using namespace std ;
  
  template <class T>
  struct BinaryTree{
     T data ;
     BinaryTree * lc ;
     BinaryTree * rc ;             
  } ;
 
 BinaryTree <int> * root ;
 BinaryTree <int> * image ;
 
  
 const int N = 7 ;
 

 
 
  template <class T>
  void  switchs( BinaryTree <T> * p ,stack <BinaryTree<T>*> st)
    {
       while(!st.empty()) //当st不为空的时候 
       {
          BinaryTree <T> * top = st.top() ;
          st.pop() ;
          while(top) //前序遍历，右节点依次插入堆栈，左节点依次进行操作
          {          //此处也可以，左节点和右节点都入栈 
            BinaryTree <T> * temp = top->lc ; //交换        
            top->lc = top->rc ;         
            top->rc = temp ;        
                     
            if(top->rc)  //右节点依次压栈 
              st.push(top->rc) ;          
                     
                    
            top = top->lc ;
          }
                            
       }          
    }
 
  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 buildImageTree(T x) //正规的二叉查找树 
  {
    if(image == 0)
    {
        image = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;
        image->lc = 0 ;
        image->rc = 0 ;
        image->data = x ;
        return ;
    }
    
    BinaryTree <T> * p = image ;
    BinaryTree <T> * q = image ;
    
    while(p)
    {
       q = p ;      
       if(p->data <= x)
           p = p->lc ;
       else
           p = p->rc ;              
    }
    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)
      {
        postOrder(p->lc) ;   
        cout<<p->data<<" " ;             
        postOrder(p->rc) ;
      } 
       
  }
  
   template <class T>
  void preOrder(BinaryTree <T> * p )
  {
      if(p)
      {
        buildImageTree(p->data) ;   
        preOrder(p->lc) ;                        
        preOrder(p->rc) ;
      } 
       
  }
  
   template <class T> //可以看做交换左右两个节点 
    void switcLR(BinaryTree <T> * p)
    {
       if(p)
      {
            
        BinaryTree <T> * temp = p->lc ;  
        p->lc = p->rc ;
        p->rc = temp ;     
        switcLR(p->lc) ;                        
        switcLR(p->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 ;
       
       stack <BinaryTree <int> *>  st ;
       st.push(root) ; //首先把根传进去 
       switchs(root , st) ;
       postOrder(root) ;
       
       system("pause");
     return 0 ;    
   }

posted on 2011-05-17 09:02 kahn 阅读(804) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


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