青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

liyuxia713

蹣跚前行者

常用鏈接

統(tǒng)計

Algorithms

C++

最新評論

二叉排序樹

 1//BTreeNode.h 二叉樹結(jié)點抽象類型
 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)造一個排序二叉樹
  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沒有默認設(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; //用這三條語句是錯的
 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é)點值最大的節(jié)點temp(最右下角的結(jié)點,也是中序遍歷最后一個結(jié)點,他沒有右子樹)
 73// 用temp的結(jié)點值替換下p的結(jié)點值
 74// 刪除temp(因為temp的右子樹為空,從而直接用其左子樹根代替本身就可達到刪除結(jié)點的目的)
 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        //記錄左子樹中序遍歷的最后一個結(jié)點(值最大的點)
 85        while(temp->rchild != NULL)
 86            temp = temp->rchild;    
 87        //刪除這個結(jié)點,等價于用這個結(jié)點的做子樹代替這個結(jié)點(因為這個結(jié)點沒有右子樹)
 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; //注意這兩行是不能合并在一起的,不然可能會出現(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> *= 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> *= 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 幸運草 閱讀(1759) 評論(0)  編輯 收藏 引用 所屬分類: Data Structure

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久综合五月| 欧美色道久久88综合亚洲精品| 欧美人妖另类| 久久免费99精品久久久久久| 麻豆亚洲精品| 老司机精品久久| 久久久精品视频成人| 欧美自拍偷拍| 久久在线免费观看| 欧美福利在线| 国产精品区一区| 国产一区二区三区在线免费观看| 国产专区欧美精品| 亚洲精品韩国| 午夜欧美理论片| 免费高清在线视频一区·| 91久久国产综合久久| 亚洲精品国产精品国自产观看| 91久久精品国产91性色| 欧美va亚洲va国产综合| 亚洲四色影视在线观看| 亚洲视频在线免费观看| 久久久国产一区二区| 欧美激情成人在线| 国产精品综合色区在线观看| 亚洲国产成人av| 亚洲午夜一区二区三区| 久久中文字幕一区| 99热精品在线| 老巨人导航500精品| 国产精品乱码| 亚洲精品综合精品自拍| 久久成人这里只有精品| 亚洲日本中文字幕| 久久女同精品一区二区| 国产精品美女诱惑| 99视频有精品| 毛片基地黄久久久久久天堂| 亚洲已满18点击进入久久| 欧美不卡视频一区发布| 国产一区视频在线看| 亚洲欧美国产精品专区久久| 欧美黄色影院| 久久人人97超碰精品888| 国产欧美亚洲日本| 亚洲欧美日韩区| 99成人在线| 欧美精品在线一区| 最新国产成人av网站网址麻豆| 久久精品系列| 性欧美激情精品| 国产日韩欧美一区在线| 亚洲一区国产| 亚洲视频一区二区| 欧美日韩亚洲一区| 99精品视频免费全部在线| 欧美激情成人在线| 欧美国产另类| av成人黄色| 99精品99久久久久久宅男| 欧美精品成人91久久久久久久| 亚洲国产精品美女| 亚洲福利视频在线| 欧美精品在线播放| 亚洲性av在线| 午夜精品美女久久久久av福利| 国产乱肥老妇国产一区二| 欧美一区二区| 久久精品观看| 亚洲国产精品视频一区| 亚洲高清一二三区| 欧美日韩国产在线播放| 亚洲一区二区在| 午夜亚洲激情| 亚洲国产另类精品专区| 亚洲精品久久久久| 国产精品无码永久免费888| 久久九九全国免费精品观看| 久久久久国色av免费观看性色| 国产欧美一区二区精品仙草咪 | 浪潮色综合久久天堂| 在线成人黄色| 欧美电影免费观看大全| 亚洲一区二区久久| 亚洲图片在线观看| 国户精品久久久久久久久久久不卡| 久久久久久久97| 欧美成人综合在线| 亚洲影院在线观看| 久久久精品欧美丰满| 99精品欧美一区二区三区| 亚洲综合日韩中文字幕v在线| 国产一区二区三区四区在线观看| 老司机凹凸av亚洲导航| 欧美激情精品久久久久久蜜臀| 亚洲综合不卡| 免费黄网站欧美| 亚洲欧美第一页| 欧美aⅴ99久久黑人专区| 亚洲自拍偷拍一区| 卡一卡二国产精品| 性欧美暴力猛交69hd| 欧美高清在线一区| 欧美一区永久视频免费观看| 免费久久精品视频| 久久激情网站| 欧美视频中文字幕| 欧美大片免费观看| 国产亚洲在线观看| 亚洲黄色大片| 黄色成人片子| 9国产精品视频| 亚洲精品在线观| 久久久久国产一区二区| 午夜精品美女自拍福到在线| 久久久久久日产精品| 亚洲永久网站| 欧美日韩精品一本二本三本| 老司机午夜精品视频| 国产精品久久中文| 亚洲片在线资源| 午夜在线a亚洲v天堂网2018| 亚洲视频一区| 免费看成人av| 亚洲大胆av| 亚洲激情影视| 欧美成人午夜影院| 欧美xx视频| 尤物在线观看一区| 久久精品国产精品亚洲| 久久蜜桃精品| 韩国av一区二区| 欧美在线一区二区三区| 久久精品动漫| 一区二区三区在线免费观看| 亚洲一区二区免费看| 亚洲一级片在线看| 欧美午夜一区二区三区免费大片 | 亚洲欧美偷拍卡通变态| 亚洲女同精品视频| 国产精品国色综合久久| 亚洲欧美欧美一区二区三区| 国产精品久久福利| 一本色道久久综合| 小嫩嫩精品导航| 国产嫩草一区二区三区在线观看 | 午夜精品久久久久久久久久久久久| 亚洲免费中文| 国产麻豆精品视频| 久久国产精品99国产| 久久亚洲免费| 亚洲国产精品电影| 欧美激情综合| 亚洲午夜精品福利| 久久婷婷av| 亚洲精品在线看| 国产精品久久久久久av福利软件| 亚洲嫩草精品久久| 免费一级欧美片在线观看| 日韩亚洲精品在线| 国产模特精品视频久久久久| 久久嫩草精品久久久精品| 亚洲精品乱码| 久久九九国产精品| 亚洲免费高清| 国产精品中文在线| 免费亚洲一区二区| 亚洲视频1区| 蜜臀91精品一区二区三区| 亚洲美女av在线播放| 午夜精品视频在线观看| 欧美精品色综合| 久久综合中文色婷婷| 亚洲麻豆av| 国产亚洲福利社区一区| 欧美激情bt| 欧美在线播放一区| 日韩香蕉视频| 噜噜爱69成人精品| 亚洲欧美激情视频| 最新国产乱人伦偷精品免费网站 | 黄色成人av网站| 欧美日韩亚洲一区二区三区| 久久精品99久久香蕉国产色戒| 亚洲免费不卡| 欧美刺激午夜性久久久久久久| 亚洲影院免费观看| 亚洲精品综合在线| 国内久久精品视频| 国产精品三区www17con| 欧美日本国产视频| 久久久亚洲高清| 午夜亚洲性色福利视频| 中文精品一区二区三区| 亚洲日本成人在线观看| 欧美成人精品在线观看| 久久久噜噜噜久久中文字免| 亚洲在线播放| 亚洲视频中文字幕| 亚洲一区久久|