1、搜索二叉树

搜索二叉树的特点就是左子树比根小，右子树比根大。它的搜索从根开始，比根大往右走，比根小往左走；最多查找高度次，走到空，还没找到，这个值就不存在；它的左右子树也必须为搜索二叉树。搜索走中序排列会得到一个升序排列。搜索二叉树也叫二叉搜索树，二叉排序树，二叉搜索树等等。搜索二叉树可以为空。

2、实现

1、插入和查找

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){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;}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root = nullptr;
};

2、删除

删除比较复杂，如果是最下面一层的节点，我们可以直接删除；如果是在中间的节点，那么他的子节点交给他的父节点就好，但涉及到根处的节点删除就不简单了，比如删除根和他的一个子节点。当把根删掉后，我们就得再选一个作为根。一个搜索二叉树根的建立本身是可以随便选一个数字作为根，所以删除也可以再人为选一个。不过这个数的选择也有规律，就是选左子树中最大节点或者右子树中最小节点。

现在删除的情况是这样，如果要删除的值比根小，就往左边走；如果比根大，就往右边走；如果等于根，这个就是重点所在：如果这个节点的两个子树都为空，那就直接删；如果有一个为空，那就把这个交给它的父节点，相当于取代它的位置，然后删除它；如果都不为空，那就需要找一个值替换这个节点，这个值就是左子树最大值或者右子树最小值，这里我选择右子树最小值。在节点两子树都有的情况下，代码比较难写，以下写了这段所叙述的情况。

	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)//左为空{else{if (parent->_left == cur){parent->_left = cur->_right;}else{paretn->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//右为空，更新root{else{if (parent->_left == cur){parent->_left = cur->_left;}else{paretn->_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;elsepminRight->_left = minRight->_right;delete minRight;}return true;}}return false;}

上面的代码仍然有错误，加入根的左或右子树整个都为空，就走不动了。这时候应当更新root，如果右边整体为空，那就把_root放到根节点的左子树，因为只有根节点没有父节点parent。

3、递归查找和插入

	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);elsereturn false;}bool InsertR(const K& key){return _InsertR(_root, key);}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);else if (root->_key > key)return _FindR(root->_left, key);}bool FindR(const K& key){return _FindR(_root, key);}

插入这里很巧妙地运用了引用，如果是一个空树，比如插入一个大于根的数值，就会一直往右走，到了空指针处，该插入了，但是新节点如何和上一个节点连接？这里用上引用，引用不能改指向，从上一个栈帧传来的是root->_right，那么接下来直接new一个Node对象，就连接上了。如果整体的数是空，那么也能解决这个问题。

还有递归删除。

	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 _Erase(root->_left, key);}delete del;return true;}}bool EraseR(const K& key){return _EraseR(_root, key);}

4、拷贝等函数

	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);}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;}

5、K和KV模型（应用搜索场景）

Key模型在现实生活有门禁系统这样的例子，主要用来查看有没有的问题。它可以用把很多个信息插入进一个搜索树，然后进行搜索。

Key/Value模型通过一个类型的信息来找另一个类型的信息。KV模型就是添加一个class V，代码和原先的一样，Find稍作修改。

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){cur = cur->_right;}else if (cur->_key > key){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)//右为空，更新root{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;elsepminRight->_left = 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;};
}

中英文互译

	key_value::BSTree<string, string> dict;dict.Insert("sort", "排序");dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("string", "字符串");dict.Insert("insert", "插入");dict.Insert("erase", "删除");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << " : " << ret->_value << endl;}else{cout << "没有这个单词" << endl;}}

这个程序要结束按Ctrl + Z + 空格。

查找水果

	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();

链接: https://gitee.com/kongqizyd/start-some-c-codes-for-learning.c/tree/master/%E6%90%9C%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91

结束。