• <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解決。  回復  更多評論
              
            久久毛片一区二区| 2021精品国产综合久久| 久久综合丝袜日本网| 久久天天躁夜夜躁狠狠躁2022 | 四虎影视久久久免费| 人人狠狠综合久久亚洲婷婷| 久久人人爽人人爽人人av东京热| 99久久国产主播综合精品 | 少妇久久久久久被弄到高潮| 99久久伊人精品综合观看| 一级做a爱片久久毛片| 久久综合丁香激情久久| 99久久伊人精品综合观看| 久久福利片| 偷偷做久久久久网站| 色欲久久久天天天综合网| 久久青青草原精品国产| 久久99国产精品久久99| 国内精品伊人久久久久影院对白 | 精品久久久久久中文字幕人妻最新| 青青草原精品99久久精品66| 久久精品国产亚洲AV大全| 国产婷婷成人久久Av免费高清| 国内精品久久国产大陆| 国产福利电影一区二区三区,免费久久久久久久精 | 久久99久久99小草精品免视看 | 国产精品久久久久天天影视| 精品久久久久久亚洲| 国内精品免费久久影院| 久久久久人妻一区二区三区 | 2021最新久久久视精品爱| 久久w5ww成w人免费| 久久er国产精品免费观看8| 亚洲午夜久久久久妓女影院| 99麻豆久久久国产精品免费 | 久久天天躁狠狠躁夜夜avapp | 综合久久一区二区三区 | 国产精品99久久精品| 久久本道综合久久伊人| 久久精品久久久久观看99水蜜桃| 91精品国产高清91久久久久久|