二叉树的小结

真言

最近正在总结学习过的算法，看到二叉树这一块，就总结总结一下吧。

内容 插入 在二叉树中插入一个关键字，查找出要插入的位置新建节点，并插入

// function:insert key into tree
template
   
    
void tree
    
     ::_insert(btnode
     
       * *bt,T d) { if((*bt) == NULL) { (*bt) = new btnode
      
       ; (*bt) -> key = d; } else { btnode
       
         * p = *bt ; if(d < p->key) { this->_insert(&(p->Lchild),d); } else if(d>p->key) { this->_insert(&(p->Rchild),d); } else { cout<
        
         
 
         
 三种遍历方法 先序遍历，中序遍历，后序遍历先序遍历
         
// fucntion:preorder visit tree
template
          
           
void tree
           
            ::_preOrderTraver(btnode
            
              * p) { if(p != NULL ) { this->_visit(p); this->_preOrderTraver(p->Lchild); this->_preOrderTraver(p->Rchild); } };
            
           
          
         
 中序遍历
         
// fucntion:inorder visit tree
template
          
           
void tree
           
            ::_inOrderTraver(btnode
            
              * p) { if(p != NULL ) { this->_inOrderTraver(p->Lchild); this->_visit(p); this->_inOrderTraver(p->Rchild); } };
            
           
          
         
 后序遍历
         
// fucntion:postorder visit tree
template
          
           
void tree
           
            ::_postOrderTraver(btnode
            
              * p) { if(p != NULL ) { this->_postOrderTraver(p->Lchild); this->_postOrderTraver(p->Rchild); this->_visit(p); } };
            
           
          
         
 
         
 判断是否是平衡树 
         
// function:whether is balanced binary tree
template
          
           
std::pair
           
             binarytree
            
             ::_IsBalancedBinaryTree(btnode
             
               *p) { if( p == NULL ) return std::make_pair(0,true); else { std::pair
              
                r = this -> _IsBalancedBinaryTree(p->Rchild); std::pair
               
                 l = this -> _IsBalancedBinaryTree(p->Lchild); int h = (int)(r.first) - (int)(l.first); h = abs(h); if(h>1) return std::make_pair(max(r.first,l.first)+1,false); else return std::make_pair(max(r.first,l.first)+1,r.second && l.second); } };
               
              
             
            
           
          
         





 
         
 实验 
        
       
      
     
    
   

代码

b-tree.h

#include 
     
      
#include 
      
        #include 
       
         #include 
        
          using namespace std; template
         
           class btnode { public: T key; btnode * Lchild; btnode * Rchild; // function:make function btnode( ); }; template
          
            btnode
           
            ::btnode() { key = -1; Lchild = NULL; Rchild = NULL; }; template
            
              class tree { public: // var:R id the root of the tree btnode
             
               * R; // function:make function tree(); // function:make tree void _maketree(T * data,size_t s); // function:insert key into tree void tree
              
               ::_insert(btnode
               
                 * *bt,T d); // function:visit node p void _visit(btnode
                
                  * p); // fucntion:preorder visit tree void _preOrderTraver(btnode
                 
                   * p); // fucntion:inorder visit tree void _inOrderTraver(btnode
                  
                    * p); // fucntion:postorder visit tree void tree
                   
                    ::_postOrderTraver(btnode
                    
                      * p); // function:whether is balanced binary tree std::pair
                     
                       _IsBalancedBinaryTree(btnode
                      
                        *p); }; // function:make function template
                       
                         tree
                        
                         ::tree() { this->R = NULL; }; // function:make tree // input:an array of data and its length // output: a binary tree template
                         
                           void tree
                          
                           ::_maketree(T * data,size_t s) { for(size_t i= 0;i
                           
                            _insert(&(this->R),data[i]); } }; // function:insert key into tree template
                            
                              void tree
                             
                              ::_insert(btnode
                              
                                * *bt,T d) { if((*bt) == NULL) { (*bt) = new btnode
                               
                                ; (*bt) -> key = d; } else { btnode
                                
                                  * p = *bt ; if(d < p->key) { this->_insert(&(p->Lchild),d); } else if(d>p->key) { this->_insert(&(p->Rchild),d); } else { cout<
                                 
                                   void tree
                                  
                                   ::_visit(btnode
                                   
                                     * p) { if(p != NULL) { cout<<"key="<
                                    
                                     key<
                                     
                                       void tree
                                      
                                       ::_preOrderTraver(btnode
                                       
                                         * p) { if(p != NULL ) { this->_visit(p); this->_preOrderTraver(p->Lchild); this->_preOrderTraver(p->Rchild); } }; // fucntion:inorder visit tree template
                                        
                                          void tree
                                         
                                          ::_inOrderTraver(btnode
                                          
                                            * p) { if(p != NULL ) { this->_inOrderTraver(p->Lchild); this->_visit(p); this->_inOrderTraver(p->Rchild); } }; // fucntion:postorder visit tree template
                                           
                                             void tree
                                            
                                             ::_postOrderTraver(btnode
                                             
                                               * p) { if(p != NULL ) { this->_postOrderTraver(p->Lchild); this->_postOrderTraver(p->Rchild); this->_visit(p); } }; // function:whether is balanced binary tree template
                                              
                                                std::pair
                                               
                                                 tree
                                                
                                                 ::_IsBalancedBinaryTree(btnode
                                                 
                                                   *p) { if( p == NULL ) return std::make_pair(0,true); else { std::pair
                                                  
                                                    r = this -> _IsBalancedBinaryTree(p->Rchild); std::pair
                                                   
                                                     l = this -> _IsBalancedBinaryTree(p->Lchild); int h = (int)(r.first) - (int)(l.first); h = abs(h); if(h>1) return std::make_pair(max(r.first,l.first)+1,false); else return std::make_pair(max(r.first,l.first)+1,r.second && l.second); } };
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

test.cpp

#include 
     
      
#include "b-tree.h"
using namespace std;

// function:input data
std::pair
      
        Inputdata(); int main() { // tree has the root : tree::R tree
       
         * T = new tree
        
         ; //int size = 10; //int * data = new int[size]; //for(int i=0;i
         
           d = Inputdata(); T->_maketree(d.first,d.second); cout<<"preorder traversal"<
          
           _preOrderTraver(T->R); cout<<"inorder traversal"<
           
            _inOrderTraver(T->R); cout<<"postorder traversal"<
            
             _postOrderTraver(T->R); std::pair
             
               r=T->_IsBalancedBinaryTree(T->R); cout<<"whether it is balanced binary tree,result is "<
              
                Inputdata() { size_t s = 0; cout<<"please input the number(>=0) of data,size = "<
               
                >s; std::pair
                
                  r; int * p = NULL; if(s == 0) { r = std::make_pair(p,0); return r; } else { p = new int[s]; cout<<"please input data"<
                 
                  >p[i]; } cout<<"ok,data input over"<