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


	


            
	    
    




            






            

				

            



    
    







            
	   
	



久久精品人人做人人爽电影|
亚洲欧洲精品成人久久奇米网|
久久精品无码一区二区无码|
久久人妻少妇嫩草AV无码专区|
亚洲国产精品久久66|
蜜桃麻豆WWW久久囤产精品|
人妻精品久久无码区|
久久久无码精品午夜|
蜜臀久久99精品久久久久久小说|
国产精品99久久久久久猫咪
|
久久精品成人免费国产片小草|
久久久久久久久久久久久久
|
日日狠狠久久偷偷色综合96蜜桃|
99蜜桃臀久久久欧美精品网站|
国产精品久久国产精品99盘
|
久久中文娱乐网|
久久久久亚洲AV无码观看|
久久久久国产一级毛片高清版|
精品久久亚洲中文无码|
久久精品中文字幕有码|
久久夜色精品国产亚洲|
久久久久国产精品熟女影院|
亚洲精品视频久久久|
国产精品久久久久乳精品爆|
久久天天躁狠狠躁夜夜96流白浆
|
亚洲午夜久久久久久噜噜噜|
欧洲国产伦久久久久久久|
99久久99久久|
久久久久国产精品|
久久99国产精品久久|
久久Av无码精品人妻系列|
一本色道久久综合狠狠躁|
亚洲精品第一综合99久久|
欧美亚洲日本久久精品|
思思久久99热只有频精品66|
久久综合久久鬼色|
日韩欧美亚洲综合久久影院Ds|
久久精品国产WWW456C0M|
久久精品国产亚洲7777|
国产精品久久新婚兰兰|
99久久精品国产一区二区|