• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

             

            #include <iostream>

            using namespace std; 

            template
            <typename Type> 
            struct BTNode{
                Type elem;
                BTNode
            <Type>* lchild, *rchild;
                BTNode(){}
                BTNode( BTNode
            <Type>* l, BTNode<Type>* r, Type k ):
                    lchild(l), rchild(r), elem(k) {}
            };

            template
            <typename Type>
            class BSTree{
                
            private:
                    BTNode
            <Type>* root;    
                    BTNode
            <Type>* get_min( BTNode<Type>* );
                    BTNode
            <Type>* get_max( BTNode<Type>* );
                    BTNode
            <Type>* insert ( BTNode<Type>*, Type key );
                    BTNode
            <Type>* erase  ( BTNode<Type>*, Type key );
                    
            void          travel ( BTNode<Type>* root );
                    
            void          clear  ( BTNode<Type>* root );
                    
            bool          search ( BTNode<Type>*, Type key );
                
                
            public:
                    BSTree();
                    
            ~BSTree();
                    BTNode
            <Type>* get_min();
                    BTNode
            <Type>* get_max();
                    
            void          insert( Type key );
                    
            void          travel();
                    
            bool          is_empty();
                    
            void          clear();
                    
            void          erase( Type key );
                    
            bool          search( Type key );
            };

            template
            <typename Type>
            bool BSTree<Type>::search( BTNode<Type>* root, Type key ){
                
            if!root ) return false;
                
            if( root->elem== key ) return true;
                
                
            if( key< root->elem ) return search( root->lchild, key );
                
            else                  return search( root->rchild, key );
            }

            template
            <typename Type>
            bool BSTree<Type>::search( Type key ){
                
            return search( root, key ); }

            template
            <typename Type>
            BTNode
            <Type>* BSTree<Type>::erase( BTNode<Type>* root, Type key ){
                
            if( root->elem== key ){
                    
            if!root->lchild && !root->rchild ){
                        delete root;
                        
            return NULL; }
                    
            else if( root->lchild && !root->rchild ){
                        BTNode
            <Type>* tmp= root->lchild;
                        delete root; 
            return tmp; }
                    
            else {
                        BTNode
            <Type>* tmp= get_min( root->rchild );
                        root
            ->elem= tmp->elem;
                        root
            ->rchild= erase( root->rchild, tmp->elem );
                        
            return root; }
                }
                
            if( key< root->elem ) root->lchild= erase( root->lchild, key );
                
            else                  root->rchild= erase( root->rchild, key );
                
            return root;
            }

            template
            <typename Type>
            void BSTree<Type>::erase( Type key ){
                
            if!search( key ) ) return;
                root
            = erase( root, key );
            }

            template
            <typename Type>
            void BSTree<Type>::clear( BTNode<Type>* root ){
                
            if( root ){
                    clear( root
            ->lchild );
                    clear( root
            ->rchild );
                    delete root; }
            }

            template
            <typename Type>
            void BSTree<Type>::clear(){
                clear( root ); }

            template
            <typename Type>
            bool BSTree<Type>::is_empty(){
                
            return root== NULL; }

            template
            <typename Type>
            BSTree
            <Type>::BSTree(){ root= NULL; }

            template
            <typename Type>
            BSTree
            <Type>::~BSTree(){
                clear(); }

            template
            <typename Type>
            void BSTree<Type>::travel( BTNode<Type>* root ){
                
            if( root ){
                    travel( root
            ->lchild );
                    cout 
            << root->elem << endl;
                    travel( root
            ->rchild ); }
            }

            template
            <typename Type>
            void BSTree<Type>::travel(){
                BTNode
            <Type>* r= root;
                travel( r ); }

            template
            <typename Type>
            BTNode
            <Type>* BSTree<Type>::insert(BTNode<Type>* root,Type key){
                
            if( root== NULL )
                    
            return new BTNode<Type>( NULL, NULL, key );
                
            if( root->lchild== NULL && key< root->elem ){
                    root
            ->lchild= new BTNode<Type>( NULL, NULL, key );
                    
            return root; }
                
            else if( root->rchild== NULL && key> root->elem ){
                    root
            ->rchild= new BTNode<Type>( NULL, NULL, key );
                    
            return root; }
                
            if( root->elem> key ) root->lchild= insert( root->lchild, key );
                
            else                  root->rchild= insert( root->rchild, key );
                
            return root;
            }

            template
            <typename Type>
            void BSTree<Type>::insert( Type key ){
                root
            = insert( root, key ); }

            template
            <typename Type>
            BTNode
            <Type>* BSTree<Type>::get_min( BTNode<Type>* root ){
                
            if( root== NULL ) return NULL;
                
            while( root->lchild ) root= root->lchild;
                
            return root;}

            template
            <typename Type>
            BTNode
            <Type>* BSTree<Type>::get_min(){
                BTNode
            <Type>* r= root;
                
            return get_min( r );}

            template
            <typename Type>
            BTNode
            <Type>* BSTree<Type>::get_max( BTNode<Type>* root ){
                
            if( root== NULL ) return NULL;
                
            while( root->rchild ) root= root->rchild;
                
            return root;}

            template
            <typename Type>
            BTNode
            <Type>* BSTree<Type>::get_max(){
                BTNode
            <Type>* r= root;
                
            return get_max( r );}
                
            int main()
            {
                freopen( 
            "test.txt""w", stdout );
                BSTree
            <int>  test;
                
                
            forint i= 0; i< 100000++i )
                test.insert( rand() );
                
            forint i= 0; i< 100000++i )
                test.erase( rand() );
                
                test.travel();
                
                
            return 0;
            }
            posted on 2009-04-11 19:29 Darren 閱讀(1268) 評論(2)  編輯 收藏 引用

            評論:
            # re: Binary Search Tree c++ 模板實現 2010-10-24 15:34 | 周潤生
            在VC++里編程出現error的話。去掉main函數里第二個for循環的int可以解決。  回復  更多評論
              
            # re: Binary Search Tree c++ 模板實現 2010-12-17 00:23 | aba
            @周潤生
            這個是早期C++的一個遺留問題,在VC++6.0中可以用
            #define for if(false);else{for解決。  回復  更多評論
              
            日韩人妻无码精品久久免费一| 狠狠狠色丁香婷婷综合久久五月| 99久久精品免费| 久久精品国产精品亚洲下载| 欧美成a人片免费看久久| 久久婷婷五月综合97色| 国产精品成人精品久久久| 中文字幕无码精品亚洲资源网久久| 91视频国产91久久久| 四虎影视久久久免费| 久久精品国产只有精品2020| 人人妻久久人人澡人人爽人人精品| 国产精品久久久久影院色| 一本一本久久aa综合精品 | 久久久久女人精品毛片| 99久久精品国产毛片| 性高湖久久久久久久久| 久久成人18免费网站| 色综合久久88色综合天天| 久久精品人人做人人爽电影| 久久久久亚洲精品男人的天堂| 久久婷婷国产综合精品| 一级女性全黄久久生活片免费| 人人狠狠综合久久亚洲婷婷| 久久无码人妻一区二区三区午夜| 国产精品视频久久久| 国产一区二区精品久久岳| 久久WWW免费人成一看片| 亚洲精品无码久久毛片 | 中文字幕精品久久久久人妻| 99久久无码一区人妻| 久久综合伊人77777麻豆| 亚洲?V乱码久久精品蜜桃 | 久久噜噜电影你懂的| 久久综合久久综合久久综合| 亚洲精品乱码久久久久久蜜桃 | 久久伊人亚洲AV无码网站| 亚洲人成无码网站久久99热国产| 久久精品中文字幕有码| 国产亚洲精品自在久久| 国产69精品久久久久99尤物|