• <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>
            

    
            

            




            







												


        

            
	

            liyuxia713
            

            蹣跚前行者
            

            


            
	
		

            常用鏈接
            

		

            統計
            
	
		
		
		
            Algorithms
            
		
				
			
	
		
            C++
            
		
				
			
	

		

            最新評論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			二叉排序樹
		
            
		
             1//BTreeNode.h 二叉樹結點抽象類型
             2
             3#ifndef BTREENODE_H
             4#define BTREENODE_H
             5
             6#include <cstdlib>
             7//template<class T> class BTree;
             8template<class T> class SortBTree;
             9
            10template<class T> class BTreeNode
            11{
            12    //friend class BTree<T>;
            13    friend class SortBTree<T>;
            14public:
            15    BTreeNode():lchild(NULL),rchild(NULL){    };
            16    BTreeNode(const T&dt, BTreeNode<T> *lch =NULL , BTreeNode<T> *rch = NULL)
            17        :data(dt),lchild(lch),rchild(rch){};
            18
            19    T get_data()const {return data;    };    
            20    BTreeNode<T>* get_lchild()const {return lchild;    };
            21    BTreeNode<T>* get_rchild()const {return rchild;    };
            22    void set_data(const T& d) { data = d;};    
            23protected:
            24private:
            25    T data;
            26    BTreeNode<T> *lchild, *rchild;
            27}            ;
            28
            29#endif
            

              1/************************************************************************
              2* SortBTree.h
              3* 根據給定的字符串構造一個排序二叉樹
              4* 從排序二叉樹中尋找最大值，最小值，不存在時拋出invalid_argument異常
              5* 從排序二叉樹中刪除某一元素，不存在時拋出invalid_argument 異常
              6* 往排序二叉樹中添加一個新元素                                                                     
              7************************************************************************/
              8
              9#ifndef SORTBTREE_H
             10#define SORTBTREE_H
             11
             12#include "BTreeNode.h"
             13#include <cstdlib>
             14#include <stdexcept>
             15
             16template<class T>
             17class SortBTree
             18{
             19public:
             20    SortBTree(T* p , int n);
             21    
             22    const T& max()const; // return the maximum
             23    const T& min()const; // return the minimum
             24    
             25    BTreeNode<T>* find_data(const T& data)const; //return the node of data, if data is not exist, throw error
             26    void delete_data(const T& data) { delete_data(root,data); }; //delete the node of data, if data is not exist, throw error
             27    void insert_data(const T& data) { insert_data(root,data); };
             28
             29    BTreeNode<T>* get_root()const {return root; }; // return the root of tree
             30    void display()const    { display(root,visit); cout << endl;};    // print the data of tree
             31    
             32protected:
             33    static void insert_data(BTreeNode<T> * &root, const T& ndata); //這里必須是對指針的引用,切記，切記    
             34    static BTreeNode<T>* find_data(BTreeNode<T>* r,const T& data);
             35    static void delete_node(BTreeNode<T> * &p);
             36    static void delete_data(BTreeNode<T>* &r, const T& data);
             37    static void display(BTreeNode<T>*p, void visit(BTreeNode<T>* p));    
             38private:
             39    BTreeNode<T> *root;    
             40}            ;
             41
             42//construction function
             43template<class T>
             44SortBTree<T>::SortBTree(T* p, int n)
             45{
             46    root = new BTreeNode<T>;
             47    root = NULL; //注意這行很必要，BTreeNode沒有默認設置為NULL的構造函數
             48    for(int i = 0; i != n; ++i)
             49    {        
             50        insert_data(root,p[i]);
             51    }
             52}
             53
             54// insert a new data 
             55template<class T>
             56void SortBTree<T>::insert_data(BTreeNode<T> *&rt,const T& ndata)
             57{
             58    if(rt == NULL) 
             59    {
             60        rt = new BTreeNode<T>(ndata,NULL,NULL);
             61        //rt->data = ndata; //這三條語句不等于上面那條
             62        //rt->lchild = NULL; //用這三條語句是錯的
             63        //rt->rchild = NULL;
             64    }
             65    else if(rt->data == ndata) return;
             66    else if(rt->data > ndata) insert_data(rt->lchild, ndata);
             67    else insert_data(rt->rchild, ndata);
             68}
             69
             70// delete a node from tree(improved)
             71// 如果p沒有左子樹，則讓p的右子樹的根代替p即可。
             72// 如果p有左子樹，找出左子樹中結點值最大的節點temp(最右下角的結點，也是中序遍歷最后一個結點，他沒有右子樹)
             73// 用temp的結點值替換下p的結點值
             74// 刪除temp(因為temp的右子樹為空，從而直接用其左子樹根代替本身就可達到刪除結點的目的)
             75// 注： 一般的方法用temp替換p，但是這樣可能導致樹很不平衡。
             76template<class T>
             77void SortBTree<T>::delete_node(BTreeNode<T> * &p)
             78{
             79    if(p == NULL) cout << "There is not this node." <<endl;
             80    else if(p->lchild == NULL) p = p->rchild;
             81    else
             82    {
             83        BTreeNode<T>* temp = p;
             84        //記錄左子樹中序遍歷的最后一個結點（值最大的點）
             85        while(temp->rchild != NULL)
             86            temp = temp->rchild;    
             87        //刪除這個結點，等價于用這個結點的做子樹代替這個結點（因為這個結點沒有右子樹）
             88        BTreeNode<T>* parent;
             89        parent = temp;
             90        while(parent->rchild != NULL)
             91        {
             92            parent = temp;
             93            temp = temp->rchild;
             94        }
             95        parent = temp->lchild;
             96        p->set_data(temp->data);        
             97    }
             98}
             99
            100//delete a data
            101template<class T>
            102void SortBTree<T>::delete_data(BTreeNode<T>* &root, const T& data)
            103{
            104    if(root == NULL)
            105        throw std::invalid_argument("This data is not exsit.");
            106    else if(root->data == data) delete_node(root);
            107    else if(root->data > data) delete_data(root->lchild,data);
            108    else delete_data(root->rchild,data);
            109}
            110
            111// find a specific data
            112template<class T>
            113BTreeNode<T>*  SortBTree<T>::find_data(BTreeNode<T>* r,const T& data)
            114{
            115    if(r == NULL) return r;
            116    else if(r->data == data) return r; //注意這兩行是不能合并在一起的，不然可能會出現NULL->data呢
            117    else if(r->data > data) return find_data(r->lchild,data);
            118    else return find_data(r->rchild,data);
            119}
            120// find a specific data in tree
            121template<class T>
            122BTreeNode<T>* SortBTree<T>::find_data(const T& data)const
            123{
            124    if(find_data(root,data) == NULL)
            125        throw std::invalid_argument("This data is not exist.");
            126    else 
            127        return find_data(root,data);
            128}
            129
            130// return the maximum value 
            131template<class T>
            132const T& SortBTree<T>::max()const
            133{
            134    if(root == NULL)
            135        throw std::invalid_argument("This is an empty Tree.");
            136    else
            137    {
            138        BTreeNode<T> *q = root;
            139        while(q->rchild != NULL)
            140            q = q->rchild;
            141        return q->data;
            142    }
            143}
            144
            145//return the minimum value
            146template<class T>
            147const T& SortBTree<T>::min()const
            148{
            149    if(root == NULL)
            150        throw std::invalid_argument("This is an empty Tree.");
            151    else
            152    {
            153        BTreeNode<T> *q = root;
            154        while(q->lchild != NULL)
            155            q = q->lchild;
            156        return q->data;
            157    }
            158}
            159
            160//print the sort tree
            161template <class T>
            162void SortBTree<T>::display(BTreeNode<T>*p, void visit(BTreeNode<T>* p))
            163{
            164    if(p != NULL)
            165    {
            166        display(p->lchild,visit);
            167        visit(p);
            168        display(p->rchild,visit);
            169    }                
            170}
            171#endif
            

            

             1//SortBTree_Test.cpp
             2
             3#include "SortBTree.h"
             4#include <iostream>
             5#include "string"
             6
             7using std::cout;
             8using std::endl;
             9using std::invalid_argument;
            10//謂詞函數predicate
            11void visit(BTreeNode<char> *p) { std::cout << p->get_data() << " ";};
            12
            13int main()
            14{
            15    char *str = "19382";
            16    SortBTree<char> sbtr(str,5);
            17    SortBTree<char> empty_tree(str,0);
            18    cout << "The original sort binary tree is: ";
            19    sbtr.display();
            20    try
            21    {
            22        sbtr.find_data('5');
            23    }
            24    catch (invalid_argument& err)
            25    {
            26        cout << err.what() <<endl;
            27    }
            28
            29    try
            30    {
            31        cout << "max = " << sbtr.max() <<endl;
            32        cout << "min = " << sbtr.min() <<endl;
            33        cout << "max of empty tree = " << empty_tree.max() <<endl;
            34    }
            35    catch(invalid_argument& err)
            36    {
            37        cout << err.what() <<endl;
            38    }
            39
            40    try
            41    {        
            42        sbtr.insert_data('6');
            43        sbtr.delete_data('8');
            44        sbtr.display();
            45        sbtr.delete_data('5');
            46        sbtr.display();        
            47    }
            48    catch (invalid_argument& err)
            49    {
            50        cout << err.what() <<endl;
            51    }
            52    
            53    return 0;
            54}
            

		
            
			posted on 2009-04-27 20:57 幸運草 閱讀(1755) 評論(0)  編輯 收藏 引用  所屬分類: Data Structure 
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



国产精品久久永久免费|
亚洲精品乱码久久久久久久久久久久|
国产精品久久久久国产A级|
韩国免费A级毛片久久|
99国产欧美精品久久久蜜芽
|
国产精品对白刺激久久久|
久久99国产精品久久|
色综合久久夜色精品国产|
久久久久久久久久久精品尤物|
久久综合综合久久综合|
久久久久久国产精品免费免费|
免费精品久久天干天干|
亚洲国产精品久久|
无码日韩人妻精品久久蜜桃|
久久国产精品偷99|
国产Av激情久久无码天堂|
亚洲国产成人精品女人久久久|
久久久久久久久久久久中文字幕|
亚洲精品tv久久久久久久久久|
婷婷久久综合九色综合98|
久久久久久国产精品无码超碰|
香蕉aa三级久久毛片|
精品久久久久久国产牛牛app|
日产精品久久久一区二区|
久久亚洲国产精品成人AV秋霞|
国产午夜精品久久久久九九|
曰曰摸天天摸人人看久久久|
久久精品黄AA片一区二区三区|
无码八A片人妻少妇久久|
久久91精品国产91久|
久久综合色之久久综合|
久久久青草青青国产亚洲免观|
7国产欧美日韩综合天堂中文久久久久|
久久99国内精品自在现线|
久久A级毛片免费观看|
久久午夜羞羞影院免费观看|
久久人爽人人爽人人片AV|
久久婷婷成人综合色综合|
97久久天天综合色天天综合色hd
|
久久精品国产久精国产一老狼|
亚洲精品无码专区久久同性男|