BSTree.h

#pragma oncenamespace key {template<class K>//这里习惯用K而不是T，keystruct BSTreeNode {BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree {//这里简写了，一般应该写全称：BinarySearchTreetypedef BSTreeNode<K> Node;//在类域内部重命名以防冲突public:BSTree() = default; // 制定强制生成默认构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);//_root = nullptr;}//插入bool Insert(const K& key) {//可能插入失败，BSTree默认不允许冗余，若试图插入已存在的元素便会失败//树的形状只取决于插入的先后顺序，最先插入的元素便是根if (_root == nullptr) {_root = new Node(key);return true;}//找到可插入的位置Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else {//相等的情况插入失败return false;}}cur = new Node(key);//链接if (parent->_key < key) {parent->_right = cur;}else {parent->_left = cur;}return true;}//查找bool Find(const K& key) {Node* cur = _root;while (cur) {if (cur->_key < key) {cur = cur->_right;}else if (cur->_key > key) {cur = cur->_left;}else {return true;}}return false;}//删除(难点)bool Erase(const K& key) {Node* parent = nullptr;Node* cur = _root;while (cur) {//找到要删的值if (cur->_key < key) {parent = cur;cur = cur->_right;}else if (cur->_key > key) {parent = cur;cur = cur->_left;}else {//找到目标，开始删除if (cur->_left == nullptr) {//1.左为空if (cur == _root) {//处理删根的情况_root = cur->_right;}else {if (parent->_left == cur) {parent->_left = cur->_right;//托孤右子节点}else {parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr) {//2.右为空if (cur == _root) {//处理删根的情况_root = cur->_left;}else {if (parent->_left == cur) {parent->_left = cur->_left;//托孤左子节点}else {parent->_right = cur->_right;}}delete cur;}else {//3.左右都不为空，不能托孤两个，改找保姆：左树的最大节点(左树最右节点)或右树的最小节点(右树最左节点)//这里找右树的最小节点Node* pminRight = cur;//不能是nullptr，若根就是最左节点会进不了循环Node* minRight = cur->_right;while (minRight->_left) {pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight) {pminRight->_left = minRight->_right;}else {pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;//未找到目标数值，故未进行删除操作}//递归插入bool InsertR(const K& key) {return _InsertR(_root, key);}//递归查找bool FindR(const K& key){return _FindR(_root, key);}//递归删除bool EraseR(const K& key){return _EraseR(_root, key);}//中序递归遍历void InOrder() {//为便于调用，套一层无参的壳让子函数带参递归_InOrder(_root);cout << endl;}protected:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destroy(Node*& root){if (root == nullptr) {return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key)return _FindR(root->_right, key);elsereturn _FindR(root->_left, key);}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 开始准备删除if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else{Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}}void _InOrder(Node* root) {//↑不能缺省传Node* root = _root ，因为://1.缺省参数必须是常量或全局变量或静态变量2.访问成员变量需要的this指针只能在函数内部使用。if (root == nullptr) {return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};}namespace key_value{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}protected:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
}

test.cpp

#include <iostream>
#include <string>
using namespace std;#include "BSTree.h"void TestBSTree1(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };key::BSTree<int> t1;for (auto e : a){t1.Insert(e);}t1.InOrder();//t1.Erase(4);//t1.InOrder();//t1.Erase(14);//t1.InOrder();//t1.Erase(3);//t1.InOrder();t1.Erase(8);t1.InOrder();for (auto e : a){t1.Erase(e);t1.InOrder();}t1.InOrder();
}void TestBSTree2(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };key::BSTree<int> t1;for (auto e : a){t1.InsertR(e);}t1.InOrder();t1.EraseR(10);t1.EraseR(14);t1.EraseR(13);t1.InOrder();for (auto e : a){t1.EraseR(e);t1.InOrder();}t1.InOrder();
}void TestBSTree3(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };key::BSTree<int> t1;for (auto e : a){t1.InsertR(e);}t1.InOrder();key::BSTree<int> t2(t1);t2.InOrder();cout << endl;
}void TestBSTree4(){key_value::BSTree<string, string> dict;dict.Insert("sort", "排序");dict.Insert("left", "左");dict.Insert("right", "右");dict.Insert("string", "字符串");dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("菠萝", "面包");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << ":" << ret->_value << endl;}else{cout << "无此单词" << endl;}}
}void TestBSTree5(){string arr[] = { "门", "大桥", "鸭", "鸭", "大桥", "大桥", "大桥", "门", "门", "门", "二四六", "七八" };key_value::BSTree<string, int> countTree;for (auto str : arr){//key_value::BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == nullptr){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}int main(){TestBSTree1();TestBSTree2();TestBSTree3();TestBSTree5();TestBSTree4();return 0;
}

运行结果：