二叉搜索樹的基本實現。
1 /*
2 Date: 2014-04-29
3 purpose: An implementation of MAP using binary search tree.
4 */
5
6 #ifndef CUSTOMIZED_MAP_H
7 #define CUSTOMIZED_MAP_H
8
9 #ifndef NULL
10 #define NULL 0
11 #endif
12
13 class NODE{
14 public:
15 NODE(int _key, char * _data):key(_key),data(_data),left(NULL),right(NULL){}
16
17 public:
18 int key;
19 char * data;
20 NODE * left;
21 NODE * right;
22 };
23
24 class CUST_MAP{
25 public:
26 CUST_MAP():root(NULL){}; // how about construction failed?
27 ~CUST_MAP();
28 void destructorImp(NODE * root);
29 bool appendItem(int key, char * data);
30 bool removeItem(int key);
31 bool traverse();
32 bool traverseImp(NODE * root);
33
34 public:
35 NODE * root;
36 };
37
38 #endif
實現文件
1 #include <iostream>
2 #include <vector>
3 #include "Customized_MAP.h"
4
5 using std::cout;
6 using std::endl;
7 using std::string;
8
9 bool CUST_MAP::appendItem(int key, char * data){
10 enum Direction{LEFT, RIGHT}; //append which direction of the pended item
11 Direction direction = LEFT;
12
13 //routine check.
14 NODE * root = this->root;
15 if (root == NULL){
16 this->root = new NODE(key, data);
17 if (this->root)
18 return true;
19 else return false;
20 }
21
22 NODE * image = root;//record the history of root
23
24 // find inserting point
25 while (root){
26 image = root;
27 if (root->key > key){
28 root = root->left;
29 direction = LEFT;
30 }
31 else if (root->key < key){
32 root = root->right;
33 direction = RIGHT;
34 }
35 else return false; // duplicated key==> abort appending operation
36 }
37
38 // append the fresh node
39 NODE * newNode = new NODE(key, data);
40 if (direction == LEFT){
41 image->left = newNode;
42 }else if (direction == RIGHT){
43 image->right = newNode;
44 }
45
46 return true;
47 }
48
49 bool CUST_MAP::removeItem(int key){
50 enum Direction{LEFT, RIGHT}; //append which direction of the new item
51 Direction direction = LEFT;
52
53 NODE * root = this->root;
54 if (root == NULL) // no node deleted. return false
55 return false;
56
57 NODE * parent = NULL;
58
59 while(root){
60 if (root->key > key){
61 parent = root;
62 root = root->left;
63 direction = LEFT;
64 }
65 else if (root->key < key){
66 parent = root;
67 root = root->right;
68 direction = RIGHT;
69 }
70 else if (root->key == key){
71 if (root->left && root->right){//要刪除的節點有兩個孩子節點
72 if (root->right->left == NULL){
73 //要刪除節點的右孩子結點沒有左孩子節點
74 //1：copy data, root->right ===> root.
75 //2: record pointer
76 //3: delete root->right
77 //4: finish pointer association
78 //how to delete root->data;
79 root->data = root->right->data;
80 root->key = root->right->key;
81 NODE * right = root->right->right;
82
83 delete root->right;
84
85 root->right = right;
86 }else{
87 //要刪除節點的右孩子結點有左孩子節點
88 //root: 要刪除的節點
89 //找到root右孩子的 最左方沒左孩子的節點： tParent
90 NODE * t = root->right;
91 NODE * tParent = NULL;
92 while (t->left){
93 tParent = t;
94 t = t->left;
95 }
96 root->key = t->key;
97 root->data = t->data;
98 NODE * right = t->right;
99
100 delete t;
101 t = NULL;
102
103 tParent->left = right;
104 }
105
106 }else if (root->left){//要刪除的節點只有左孩子節點
107 if (direction == LEFT)
108 parent->left = root->left;
109 else if(direction == RIGHT)
110 parent->right = root->left;
111
112 delete root;
113 root = NULL;
114 }else if(root->right){//要刪除的節點只有右孩子節點
115 if (direction == LEFT)
116 parent->left = root->right;
117 else if(direction == RIGHT)
118 parent->right = root->right;
119
120 delete root;
121 root = NULL;
122 }else if (root->left==NULL && root->right==NULL){//要刪除的節點沒有孩子節點
123 if (direction == LEFT)
124 parent->left = NULL;
125 else if(direction == RIGHT)
126 parent->right = NULL;
127
128 delete root;
129 root = NULL;
130 }
131
132 return true;
133 }
134 }
135
136 return false;
137 }
138
139 void CUST_MAP::destructorImp(NODE * root){
140 if (root){
141 destructorImp(root->left);
142 destructorImp(root->right);
143
144 delete root;
145 root = NULL;
146 }
147 }
148
149 CUST_MAP::~CUST_MAP(){
150 destructorImp(root);
151 }
152
153 bool CUST_MAP::traverseImp(NODE * root){
154 if (root){
155 traverseImp(root->left);
156 cout<<root->data<<endl;
157 traverseImp(root->right);
158 }
159
160 return true;
161 }
162
163 bool CUST_MAP::traverse(){
164 traverseImp(root);
165
166 return true;
167 }
168
169 int main(){
170 CUST_MAP mapTest;
171 mapTest.appendItem(1, "1 one");
172 mapTest.appendItem(28, "28 twenty-eight");
173 mapTest.appendItem(16, "16 sixteen");
174 mapTest.appendItem(12, "12 twelf");
175 mapTest.appendItem(24, "24 twety-four");
176 mapTest.appendItem(56, "56 fifty-six");
177 mapTest.appendItem(36, "36 thirty-six");
178 mapTest.appendItem(66, "66 sixty-six");
179 mapTest.appendItem(46, "46 fourty-six");
180
181 cout<<"New:"<<endl;
182 mapTest.traverse();
183 cout<<endl<<endl;
184
185 mapTest.removeItem(36);
186 cout<<"New:"<<endl;
187 mapTest.traverse();
188
189 cout<<"over"<<endl;
190
191 return 0;
192 }
來幅圖片
done.
