1 #include <iostream> 2 3 using namespace std; 4 5 template <typename K, typename V> 6 class BST 7 { 8 private: 9 struct node // 类内定义类、结构体 10 { 11 K key; 12 V value; 13 node *left = nullptr; 14 node *right = nullptr; 15 }; 16 node * root = nullptr; 17 node * putB(node *rootp, K key, V value); // 注意不能把这个函数放在公有区,因为node是一个私有变量,如果外部调用putB会出问题,且只有成员函数会调用这个函数,没必要声明为公有的就不要声明为公有 18 public: 19 BST(/* args */); 20 void putA(K key, V value); 21 void putB(K key, V value); 22 /* void putB(node *&rootp, K key, V value); */ //类内定义结构体不用加作用域限定: BST<K, V>::node 23 24 V get(K key); 25 V getR(node *rootp, K key); //对于结构相似且头尾相接的数据结构(如这里的二叉树:每个节点都可以是根节点,每个根节点下都有左右节点),要善于利用递归 26 bool max(K &key, V &value); 27 bool min(K &key, V &value); 28 int rank(K key); 29 bool remove(K key); 30 int howMany(); 31 void show(); 32 void showR(node *p); 33 void free(node *p); 34 ~BST(); 35 }; 36 37 template <typename K, typename V> 38 BST<K, V>::BST(/* args */) 39 { 40 //did nothing 41 } 42 43 template <typename K, typename V> 44 V BST<K, V>::get(K key) 45 { 46 V val = NULL; 47 val = getR(root, key); 48 if(val != NULL) //warning:val == 0 is equal to val == NULL 49 { 50 cout << "key: " << key << "\t val: " << val << endl; 51 return val; 52 } 53 } 54 55 template <typename K, typename V> 56 V BST<K, V>::getR(node *rootp, K key) 57 { 58 if(rootp == nullptr) 59 { 60 cout << "can't find key[" << key << "]." << endl; 61 return NULL; 62 } 63 64 if(rootp->key == key) 65 return rootp->value; 66 else if(rootp->key < key) 67 { 68 return getR(rootp->right, key); 69 } 70 else 71 return getR(rootp->left, key); 72 } 73 74 /* 循环查找 */ 75 template <typename K, typename V> 76 void BST<K, V>::putA(K key, V value) 77 { 78 node **temp = &root; //使用指针的指针,因为下面要给指针分配内存 79 while((*temp) != nullptr) 80 { 81 if((*temp)->key == key) 82 { 83 (*temp)->key = key; 84 (*temp)->value = value; 85 return; 86 } 87 if((*temp)->key > key) 88 temp = &((*temp)->left); 89 else 90 temp = &((*temp)->right); 91 } 92 *temp = (node *)new node; 93 (*temp)->key = key; 94 (*temp)->value = value; 95 } 96 97 template <typename K, typename V> 98 void BST<K, V>::putB(K key, V value) 99 { 100 /* putB(root, key, value); */ 101 root = putB(root, key, value); 102 } 103 104 /* 递归查找 */ 105 /* 106 template <typename K, typename V> 107 void BST<K, V>::putB(node *&rootp, K key, V value) //指针的引用 108 { 109 if(rootp == nullptr) 110 { 111 rootp = new node; 112 rootp->key = key; 113 rootp->value = value; 114 return; 115 } 116 if(rootp->key == key) 117 { 118 rootp->value = value; 119 return; 120 } 121 else if(rootp->key > key) 122 return putB(rootp->left, key, value); 123 else 124 return putB(rootp->right, key, value); 125 126 } 127 */ 128 129 /* 不加typename的话会提示错误: need 'typename' before 'BST<K, V>::node' because 'BST<K, V>' is a dependent scope,原因:c++primer P593 */ 130 template <typename K, typename V> 131 typename BST<K, V>::node * BST<K, V>::putB(node *rootp, K key, V value) 132 { 133 if(rootp == nullptr) 134 { 135 rootp = new node; 136 rootp->key = key; 137 rootp->value = value; 138 return rootp; 139 } 140 if(rootp->key == key) 141 { 142 rootp->value = value; 143 } 144 else if(rootp->key > key) 145 rootp->left = putB(rootp->left, key, value); 146 else 147 rootp->right = putB(rootp->right, key, value); 148 149 return rootp; 150 } 151 152 template <typename K, typename V> 153 void BST<K, V>::show() 154 { 155 showR(root); 156 } 157 158 template <typename K, typename V> 159 void BST<K, V>::showR(node *p) 160 { 161 if(p->left != nullptr) 162 showR(p->left); 163 cout << "key: " << p->key << "\tvalue: " << p->value << endl; 164 if(p->right != nullptr) 165 showR(p->right); 166 } 167 168 template <typename K, typename V> 169 void BST<K, V>::free(node *p) 170 { 171 if(p == nullptr) 172 return; 173 free(p->left); 174 free(p->right); 175 delete p; 176 } 177 178 template <typename K, typename V> 179 BST<K, V>::~BST() 180 { 181 free(root); 182 } 183 184 int main() 185 { 186 BST<char, int> container; 187 cout << "before: " << endl; 188 for(int i=0; i<22; ++i) 189 { 190 char k = 65 + rand() % 20; 191 int v = rand() % 100; 192 cout << "k: " << k << " v: " << v << endl; 193 container.putB(k, v); 194 //or container.putA(k, v); 195 } 196 197 container.show(); 198 199 char token; 200 cout << "enter key you want to find(0 to exit):"; 201 cin >> token; 202 while(token != '0') 203 { 204 container.get(token); 205 cout << "enter key you want to find(0 to exit):"; 206 cin >> token; 207 } 208 209 return 0; 210 }