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

            蹣跚前行者
            

            


            
	
		

            常用鏈接
            

		

            統(tǒng)計(jì)
            
	
		
		
		
            Algorithms
            
		
				
			
	
		
            C++
            
		
				
			
	

		

            最新評(píng)論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			二叉排序樹
		
            
		
             1//BTreeNode.h 二叉樹結(jié)點(diǎn)抽象類型
             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* 根據(jù)給定的字符串構(gòu)造一個(gè)排序二叉樹
              4* 從排序二叉樹中尋找最大值，最小值，不存在時(shí)拋出invalid_argument異常
              5* 從排序二叉樹中刪除某一元素，不存在時(shí)拋出invalid_argument 異常
              6* 往排序二叉樹中添加一個(gè)新元素                                                                     
              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); //這里必須是對(duì)指針的引用,切記，切記    
             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沒有默認(rèn)設(shè)置為NULL的構(gòu)造函數(shù)
             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; //用這三條語句是錯(cuò)的
             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有左子樹，找出左子樹中結(jié)點(diǎn)值最大的節(jié)點(diǎn)temp(最右下角的結(jié)點(diǎn)，也是中序遍歷最后一個(gè)結(jié)點(diǎn)，他沒有右子樹)
             73// 用temp的結(jié)點(diǎn)值替換下p的結(jié)點(diǎn)值
             74// 刪除temp(因?yàn)閠emp的右子樹為空，從而直接用其左子樹根代替本身就可達(dá)到刪除結(jié)點(diǎn)的目的)
             75// 注： 一般的方法用temp替換p，但是這樣可能導(dǎo)致樹很不平衡。
             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        //記錄左子樹中序遍歷的最后一個(gè)結(jié)點(diǎn)（值最大的點(diǎn)）
             85        while(temp->rchild != NULL)
             86            temp = temp->rchild;    
             87        //刪除這個(gè)結(jié)點(diǎn)，等價(jià)于用這個(gè)結(jié)點(diǎn)的做子樹代替這個(gè)結(jié)點(diǎn)（因?yàn)檫@個(gè)結(jié)點(diǎn)沒有右子樹）
             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; //注意這兩行是不能合并在一起的，不然可能會(huì)出現(xiàn)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//謂詞函數(shù)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 幸運(yùn)草 閱讀(1742) 評(píng)論(0)  編輯 收藏 引用  所屬分類: Data Structure 
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲欧美国产精品专区久久|
久久一本综合|
777午夜精品久久av蜜臀|
精品久久久久久无码中文字幕|
久久精品视频一|
久久精品无码av|
久久亚洲2019中文字幕|
日本加勒比久久精品|
香蕉99久久国产综合精品宅男自
|
欧美黑人又粗又大久久久|
亚洲人成网站999久久久综合|
伊人久久成人成综合网222|
久久婷婷色香五月综合激情
|
精品一久久香蕉国产线看播放|
久久精品国产91久久麻豆自制|
狠狠色丁香婷婷久久综合不卡|
99热成人精品免费久久|
久久精品国产99久久久香蕉|
中文成人无码精品久久久不卡|
久久综合久久美利坚合众国|
久久婷婷五月综合97色一本一本
|
伊人久久综合精品无码AV专区|
色欲综合久久中文字幕网|
狠狠色丁香婷婷综合久久来|
久久精品国产精品亚洲下载
|
要久久爱在线免费观看|
久久婷婷五月综合97色|
国产成人综合久久精品尤物|
久久久久久久久66精品片|
潮喷大喷水系列无码久久精品
|
久久久久人妻一区二区三区vr|
久久这里只精品国产99热|
久久综合伊人77777|
久久久久久午夜成人影院
|
伊人色综合久久|
久久伊人五月丁香狠狠色|
亚洲成人精品久久|
无码人妻久久一区二区三区免费|
久久久久18|
久久99中文字幕久久|
亚洲精品无码久久久久|