liyuxia713

蹣跚前行者

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 50
文章 - 0
評論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數據結構中的一些經典算法
第四維空間
數據結構算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學習筆記

二叉排序樹

1

//BTreeNode.h 二叉樹結點抽象類型
2

3

#ifndef BTREENODE_H
4

#define BTREENODE_H
5

6

#include <cstdlib>
7

//template<class T> class BTree;
8

template<class T> class SortBTree;
9

10

template<class T> class BTreeNode
11

{
12

//friend class BTree<T>;
13

friend class SortBTree<T>;
14

public:
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;};
23

protected:
24

private:
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

16

template<class T>
17

class SortBTree
18

{
19

public:
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

32

protected:
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));
38

private:
39

BTreeNode<T> *root;
40

};
41

42

//construction function
43

template<class T>
44

SortBTree<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
55

template<class T>
56

void 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，但是這樣可能導致樹很不平衡。
76

template<class T>
77

void 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
101

template<class T>
102

void 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
112

template<class T>
113

BTreeNode<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
121

template<class T>
122

BTreeNode<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
131

template<class T>
132

const 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
146

template<class T>
147

const 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
161

template <class T>
162

void 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

7

using std::cout;
8

using std::endl;
9

using std::invalid_argument;
10

//謂詞函數predicate
11

void visit(BTreeNode<char> *p) { std::cout << p->get_data() << " ";};
12

13

int 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