• <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 閱讀(1267) 評論(2)  編輯 收藏 引用

            評論:
            # re: Binary Search Tree c++ 模板實現(xiàn) 2010-10-24 15:34 | 周潤生
            在VC++里編程出現(xiàn)error的話。去掉main函數(shù)里第二個for循環(huán)的int可以解決。  回復(fù)  更多評論
              
            # re: Binary Search Tree c++ 模板實現(xiàn) 2010-12-17 00:23 | aba
            @周潤生
            這個是早期C++的一個遺留問題,在VC++6.0中可以用
            #define for if(false);else{for解決。  回復(fù)  更多評論
              

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            青青青国产精品国产精品久久久久| MM131亚洲国产美女久久| 97久久精品人人做人人爽| 久久久久国产一区二区三区| 婷婷国产天堂久久综合五月| 少妇久久久久久被弄高潮| 国产99久久久国产精品~~牛| 午夜精品久久影院蜜桃| 久久99精品久久久久子伦| 日韩欧美亚洲综合久久影院Ds| 日韩AV无码久久一区二区| 国产巨作麻豆欧美亚洲综合久久| 久久狠狠爱亚洲综合影院| 精品久久久久久99人妻| 久久精品亚洲精品国产色婷| 久久久久久久亚洲精品| 国产国产成人精品久久| 婷婷五月深深久久精品| 欧美午夜A∨大片久久 | 久久se这里只有精品| 国内高清久久久久久| 久久久久无码精品| 久久精品国产精品青草app| 日韩精品久久无码人妻中文字幕| 精品久久久久一区二区三区| 国产成人精品久久免费动漫| 久久久久久久亚洲Av无码| 亚洲精品99久久久久中文字幕| 久久九九久精品国产免费直播| .精品久久久麻豆国产精品| 久久婷婷五月综合色奶水99啪| 国产精品久久久久久久app | 精品国产热久久久福利| 99久久精品这里只有精品 | 亚洲狠狠久久综合一区77777| 人妻精品久久无码区| 无码人妻久久一区二区三区免费 | 久久久久久狠狠丁香| 国产一区二区三区久久精品| 国内精品久久久人妻中文字幕| 国产A级毛片久久久精品毛片|