1. 二叉搜索树
a. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树它的中序遍历是得到的结果是升序
b. 二叉搜索树的实现
1. 搜索二叉树的构建
代码
template<class K>struct BinNode{BinNode(K key):_key(key){}K _key;BinNode* left = nullptr;BinNode* right = nullptr;};template<class K>class BinNodeTree{public:typedef BinNode<K> node;private:node* _root = nullptr;};2. 二叉树的插入
循环实现思路
返回类型是 bool ，判断能否插入传入的值（二叉搜索树不存相同的值）
跟节点比较，如果 插入的值 key > 节点的值，则走节点的右子树 ; 如果插入的值 key < 节点的值，则走左子树 ; 如果等于，返回 false ;如果结点为空 ，结束循环 ，new 一个新的结点，需要空节点的父节点去链接新结点，所以我们一定要定义一个父节点
注意：
由于不知道新结点应该是父节点的左子树还是右子树，这里链接就需要判断一下，如果空结点是父结点的左子树，那么就链接左边，反之亦然一开始的根节点为空，所以这里需要特殊处理一下，让根节点成为插入的第一个值构造的新节点代码
bool insert(const K &key){if (_root == nullptr){_root = new node(key);return true;}node* prev = _root;node* cur = _root;while (cur){if (key > cur->_key){prev = cur;cur = cur->right;}else if (key < cur->_key){prev = cur;cur = cur->left;}else{return false;}}cur = new node(key);if (key > prev->_key){prev->right = cur;}else{prev->left = cur;}return true;}
递归实现思路
大体思路和循环的思路差不多，但是略有不同
由于递归函数一定需要结点的地址（可以走左右子树）和 需要插入的值，给这个递归函数传入的结点的地址一定是根节点，但是根节点在类里面不能访问，所以这里我们就弄一层包装，一个函数是传根节点的地址的，另一个函数用来递归实现（都在类里面）这里我们同样需要判断插入的值 key 和 结点的值的关系，但是这里可以不需要父节点，我们在递归函数的形参上面跟之前有所不同，这里的形参用了引用，使得可以直接让空结点存新结点的地址代码
bool Insert(const K& key){return _Insert(_root, key);}bool _Insert(node*& root, const K& key){if (root == nullptr){root = new node(key);return true;}if (key == root->_key){return false;}else if (key > root->_key){_Insert(root->right, key);}else{_Insert(root->left, key);}}
3. 二叉树的查找
循环实现思路
跟节点比较，如果 插入的值 key > 节点的值，则走节点的右子树 ; 如果插入的值 key < 节点的值，则走左子树 ; 如果结点为空 return false；
代码
bool find(const K& key){node* cur = _root;if (cur == nullptr){return false;}while (cur){if (key > cur->_key){cur = cur->right;}else if(key < cur->_key){cur = cur->left;}else{return true;}}return false;}
递归实现思路
和插入的递归思路有一点相同，都要封装一层
剩下的思路和循环是一样的
代码
bool Find(const K& key){return _Find(_root, key);}bool _Find(node* root, const K& key){if (root == nullptr){return false;}if (key == root->_key){return true;}else if (key > root->_key){_Find(root->right, key);}else{_Find(root->left, key);}}
4. 二叉树的删除
循环实现思路
大体上遇到的情况分三种情况：
删除的结点左右子树为空删除的结点左子树或者右子树为空删除的结点左右子树都不为空
第一种情况：
实际上，第一种情况的操作可以归到第二种里面
第二种情况：
如果删除的结点左子树为空，那么我们需要这个结点的 父节点的左子树或者右子树（根据删除结点是父节点的左子树还是右子树进行判断） 是删除结点的右子树
如果删除结点是父节点的左子树，那么父节点左边链接，反之则相反
如图：
如果删除的结点右子树为空，那么我们需要这个结点的 父节点的 左子树或者右子树 （根据删除结点是父节点的左子树还是右子树进行判断）是删除结点的左子树
如果删除结点是父节点的左子树，那么父节点左边链接，反之则相反
如图：
前者我们说了，如果删除节点两边都为空，则也归到第二种，此时只要判断删除节点是父节点的左子树还是右子树就好了，无需管链接删除节点的左子树还是右子树
如图：
第三种情况：
由于两边都不为空，我们不好直接删除，这时候，我们需要把删除节点当根节点（同样构成搜索二叉树），找这个搜索二叉树的某个节点的值，既可以比左边节点的值大（除根节点外），也可以比右边节点的值小，有两个答案：这个搜索二叉树的左子树的最大值和右子树的最小值
如图：
如何找右子树的最小值呢？先得到右子树的地址，再一直往左走，直到节点为空，则它的父节点就是我们要找的，所以我们需要定义一个父节点，让删除节点存父节点的值，由于父节点的左子树为空，那么删除节点要链接父节点的右子树，跟之前第二种情况一样，要知道父节点是上一个父节点的左子树还是右子树（避免删除节点就是根节点的情况导致的错误），再删除父节点
找左子树的最大值相同道理
注意事项：
第二种情况有特例，可能删除的是根节点，并且左子树或者右子树为空如果左子树为空，这个时候我们只需要直接让根节点存右子树的地址，释放原来的节点
反之则相反（如果同样为左右子树都为空，同样适用）
如图：
代码
bool erase(const K &key){node* parent = _root;node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->right;}else if (key < cur->_key){parent = cur;cur = cur->left;}else{if (cur->left == nullptr){if (cur == _root){_root = cur->right;}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;}if (parent->left == cur){parent->left = cur->left;}else{parent->right = cur->left;}delete cur;}else{node* MinRight = cur->right;node* pMinRight = cur;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;}
递归实现思路
和插入的递归思路有些一样，都需要包装，都需要传指针的引用
第一种情况和第二种情况和循环思路很像，由于是引用，这里我们不需要判断是左子树还是右子树，直接赋值即可
第三种情况前面还是一样，找到左子树的最大值或者右子树的最小值
如果找左子树的最大值：
最大值我们可以在通过循环来找，找到之后，可以选择交换删除节点的值和最大值，再次进行递归，删除的值key不变
或者是只让删除节点的值换成最大值，其它不变，递归时，传的根节点就是删除节点的左子树，删除的值key就是最大值
注意：
第三种情况递归时，不可以直接传存最大值的节点（那个最大值节点是局部变量，而引用接收局部变量会出很大问题）
代码
bool Erase(const K& key){return _Erase(_root,key);}bool _Erase(node*& root,const K& key){if (root == nullptr){return false;}if (key > root->_key){_Erase(root->right, key);}else if(key < root->_key){_Erase(root->left, key);}else{node* cur = root;if (root->left == nullptr){root = root->right;delete cur;}else if (root->right == nullptr){root = root->left;delete cur;}else{cur = cur->left;while (cur->right){cur = cur->right;}int k = root->_key = cur->_key;_Erase(root->left, k);}return true;}}
5. 二叉树的销毁
代码
~BinNodeTree(){_BinNodeTree(_root);}void _BinNodeTree(node* root){if (root == nullptr){return;}_BinNodeTree(root->left);_BinNodeTree(root->right);delete root;}
后序遍历即可
6. 二叉树的拷贝构造
代码
BinNodeTree(const BinNodeTree<K>& t){_root = copy(t._root,_root);}node* copy(node* t1, node* t2){if (t1 == nullptr){return nullptr;}t2 = new node(t1->_key);t2->left = copy(t1->left, t2->left);t2->right = copy(t1->right, t2->right);return t2;}
2. 二叉搜索树的应用
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值
如：查找一个单词是否拼写正确
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对，该种方
式在现实生活中非常常见
如：单词中英文查找 ， 统计单词出现次数