1 #include <iostream>
2 #include <queue>
3 #include <cassert>
4 using namespace std;
5
6 template<typename Key,typename Value>
7 class BST{
8 private:
9 struct Node{
10 Key key;
11 Value value;
12 Node *left;
13 Node *right;
14 Node(Key key,Value value){
15 this->key = key;
16 this->value = value;
17 this->left = this->right = NULL;
18 }
19 Node(Node *node){
20 this->key = node->key;
21 this->value = node->value;
22 this->left = node-> 23 this->right = node->right;
24 25 };
26 Node *root;
27 int count;
28 public 29 BST(){
30 root = 31 count = 0;
32 }
33 ~BST(){
34 destroy(root);
35 36 size(){
37 return 38 39 bool isEmpty(){
40 return count == 41 42 void insert(Key key,1)"> 43 root = insert(root,key,value) ;
44 45 contain(Key key){
46 contain(root,key);
47 }
48 Value* search(Key key){
49 search(root,1)"> 50 51 //前序遍历
52 preOrder(){
53 preOrder(root);
54 55 中序遍历
56 inOrder(){
57 inOrder(root);
58 59 后序遍历
60 postOrder(){
61 postOrder(root);
62 63 层序遍历
64 levelOrder(){
65 queue<Node*> q;
66 q.push(root);
67 while( !q.empty()){
68 Node *node = q.front();
69 q.pop();
70 cout<<node->key<<endl;
71 if(node->left)
72 q.push(node->left);
73 right)
74 q.push(node->right);
75 76 77
78 寻找最小的键值
79 Key minimum(){
80 assert(count != );
81 Node* minNode = minimum(root);
82 return minNode-> 83 84 寻找最大的键值
85 Key maximum(){
86 assert(count != 87 Node* maxNode = maximum(root);
88 return maxNode-> 89 }
90
91 从二叉树中删除最小值所在的节点
92 removeMin(){
93 if (root)
94 root = removeMin( root );
95 96 从二叉树中删除最大值所在的节点
97 removeMax(){
98 99 root = removeMax( root );
100 101 从二叉树中删除键值为key 的节点
102 remove(Key key){
103 root = remove(root,1)">104 105
106 107 向以node为根的二叉搜索树中，插入节点（key,value）
108 返回插入新节点的二叉搜索树的根
109 Node* insert(Node *node,Key key,Value value){
110 if(node == NULL){
111 count ++112 return new Node(key,value);
113 }
114 if(key==node->key)
115 node->value =116 else if (key < node->117 node->left = insert(node->left,1)">118 else
119 node->right = insert(node->right,1)">120 node;
121 122 查看以node为根的二叉搜索树中是否包含键值为key的节点
123 bool contain(Node* node,Key key){
124 125 true126 if(key<node->key)
127 return contain(node->128 else
129 130 }
131 Value* search(Node*132 NULL)
133 134 if(key == node->135 return &(node->value);
136 if(key < node->value)
137 return search(node->138 139 140 141 对以node为根的二叉搜索树进行前序遍历
142 void preOrder(Node* node){
143 if(node != NULL)
144 cout<<node->key<<145 preOrder(node->146 preOrder(node->147 148 对以node为根的二叉搜索树进行中序遍历
149 void inOrder(Node*150 151 inOrder(node->152 cout<<node->key<<153 inOrder(node->154 155 156 对以node为根的二叉搜索树进行后序遍历
157 void postOrder(Node*158 159 postOrder(node->160 postOrder(node->161 cout<<node->key<<162 163 164 释放内存
165 void destroy(Node*166 167 destroy(node->168 destroy(node->169 delete170 count --171 172 173 在以node为根的二叉搜索树中，返回最小键值的节点
174 Node* minimum(Node*175 if(node->left ==176 177 return minimum(node->left);
178 179
180 在以node为根的二叉搜索树中，返回最大键值的节点
181 Node* maximum(Node*182 if(node->right ==183 184 return maximum(node->right);
185 186 删除掉以node为根的二分搜索树中的最小节点
187 返回删除节点后的二分搜索树
188 Node* removeMin(Node*189 if(node->left ==190 Node* rightNode = node->191 192 rightNode;
193 }
194 node->left = removeMin(node->195 196 197 删除掉以node为根的二分搜索树中的最大节点
198 199 Node* removeMax(Node*200 if(node->right ==201 Node* leftNode = node->202 203 leftNode;
204 205 node->right = removeMax(node->206 207 208 删除掉以node为根的二分搜索树中键值为key的节点
209 210 Node* remove(Node*211 212 213 key){
214 node->left = remove(node->215 216 217 if (key > node->218 node->right = remove(node->219 220 221 else{ key = node->key
222 NULL){
223 Node *rightNode = node->224 225 count --226 227 }
228
229 230 Node *leftNode = node->231 232 count --233 234 235
236 :node的左右孩子都不为空
237 Node *successor = new Node(minimum(node->right));
238 count ++239 successor->right = removeMin(node->240 successor->left = node->241 242 count --243 successor;
244 245 246 };
247 int main(int argc,char** argv) {
248 return 249 }
