c++ BSTree二叉搜索树（附原码）

一、概念

二、基本操作

1、插入

2、中序遍历

3、删除

4、查找

5、总结删除

三、应用场景

四、原码

一、概念

左子树比根小，右子树比根大
意义：最多查找高度次数
不需要排序，就达到了二分查找的效率
同时还弥补了单纯数组的插入删除效率低的问题
其中序遍历，是一个升序，所以也叫做二叉排序树

默认定义，搜索树不允许冗余，搜索树也不允许修改
k模型的搜索树不可以修改，因为修改，那就破坏了搜索树的基本结构
k-v模型的搜索树可以修改，修改val部分，搜索树以key为参考构成搜索树

二、基本操作

1、插入

小的插入左边，大的插入右边

注意，先后插入的顺序不同，会导致树的结构不同

2、中序遍历

中序遍历，需要根节点，但是根节点为私有，怎么办？

1）友元（不推荐）
2）缺省参数、
3）再套一层
什么意思？
将函数设置为私有
再在public部分写一个函数2调用函数1

		//4、中序void Inorder(){_Inorder(_root);cout << endl;}private:void _Inorder( Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << ":" << root->_val << endl;_Inorder(root->_right);}

3、删除

替换法（此处的代码逻辑是右子树的最小节点）
左子树的最大节点：保证比所有左子树都大
右子树的最小节点：保证比所有右子树都小
交换，删除
但是左子树的最大节点或者右子树的最小节点并不一定是叶子节点
有可能带有节点，所以，需要特殊判断处理

删一个叶子、带一个孩子、带两个孩子，画图依次判断情况

1、带有一个孩子节点的情况：（顺带没有孩子的也解决了，因为链接的是空）
如果我只有一个右孩子，那就要看我是父节点的左孩子还右孩子，需要判断
父节点链接我的右孩子
如果我只有一个左孩子，同样的道理，父节点链接我的左孩子

2、带有两个孩子的节点的删除
替换法：
左子树的最大节点（最右节点），右子树的最小节点（最左节点）
交换，删除
但是要注意个特殊情况：即左子树没有最大节点，右子树没有最小节点，就要单独判断

还有一个坑：
如果根节点的左子树为空，此删除根节点就会出错，因为根据代码逻辑，此时的根节点已经没有了parent
需要单独判断

4、查找

这个简单

5、总结删除

有两种情况：

1、删除叶子节点

2、删除非叶子节点

1）删除带有一个孩子的节点（左/右）
可以把删除叶子节点一同处理，即叶子节点不需要特殊处理
为什么？删除带有一个孩子的节点
其父节点都要链接上该节点的左孩子/右孩子
如果是叶子节点，那么左孩子/右孩子是空，就直接连接上了

除了以上的正常情况
还需要考虑删除的是根节点
也就是单支树的情况
此时也要特殊处理

2）删除带两个孩子的节点
找右子树的最左边节点
又分两种情况：
a、没有最左节点
b、有最左节点

总之，画图！画图！画图！自己分析。不懂，拿我原码去看，推逻辑，自己手撕一遍，从头到尾。如此，抽丝剥茧，一砖一瓦，焉有不会之理？

三、应用场景

1、k模型
构建一个搜索树
查找一个key在不在搜索树内
例如查找文本错误单词

2、k-v模型（key-val）
通过key查找value
可以统计某个关键词次数

搜索二叉树有一个致命点：
当key为有序，就会构成仅有左子树/右子树（单支）的结构，即退化
因此，又有了AVL树和红黑树，解决左右子树高度平衡的问题，即所谓平衡树

四、原码

#pragma once
#include<iostream>
using namespace std;namespace myspace
{template<class K, class V >struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _val ;BSTreeNode(const K& key, const V& val ):_key(key),_val(val),_left(nullptr),_right(nullptr){}};template<class K, class V>class BSTree{typedef BSTreeNode<K,V> Node;public://1、插入bool insert(const K& key, const V& val = 0){//已经存在节点，返回false，不存在，插入（不冗余）if(_root == nullptr){_root = new Node(key,val);return true;}Node* cur = _root;Node* parent = _root;//根节点不为空while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if(key > cur->_key){parent = cur;cur = cur->_right;}else{return false;}}//找到空节点if (key < parent->_key){parent->_left = new Node(key,val);}else{parent->_right = new Node(key,val);}return true;}//2、删除bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if(key > cur->_key){parent = cur;cur = cur->_right;}else//找到节点{if (cur->_left == nullptr)//左孩子为空{if (cur == _root)//右单支树{_root = cur->_right;}else{if (parent->_left->_key == cur->_key){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->_key == cur->_key){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else//两个孩子均不为空{//从cur开始，找右子树的最小，即右子树的最左Node* rightMinparent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinparent = rightMin;rightMin = rightMin->_left;}//到这里，说明找到了rightMinswap(cur->_key,rightMin->_key);if (rightMinparent->_left == rightMin)//正常情况下，存在rightMin{rightMinparent->_left = rightMin->_right;}else//不存在rightMin{rightMinparent->_right = rightMin->_right;}delete rightMin;}return true;}}//走到这里，说明找到空了也没有找到return false;}//3、查找Node* find(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key == key){return cur;}if (key < cur->_key){parent = cur;cur = cur->_left;}else{parent = cur;cur = cur->_right;}}//走到这里，说明找到空了也没有找到return nullptr;}//4、中序void Inorder(){_Inorder(_root);cout << endl;}private:void _Inorder( Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << ":" << root->_val << endl;_Inorder(root->_right);}private:Node* _root = nullptr;};void BSTreetest1(){BSTree<int, int> bs;bs.insert(1,1);bs.insert(2,2);bs.insert(3,3);bs.insert(3,3);bs.insert(3,3);bs.insert(3,3);bs.insert(3,3);bs.insert(3,3);bs.insert(3,3);bs.insert(4,4);bs.insert(5,99);bs.insert(6,100);bs.Inorder();if (bs.find(100))cout << "存在" << endl;elsecout << "不存在" << endl;}void BSTreetest2()//右子树没有最左节点{BSTree<int, int> bs;bs.insert(10);bs.insert(3);bs.insert(18);bs.insert(2);bs.insert(8);bs.insert(9);bs.insert(12);bs.insert(16);bs.Inorder();bs.erase(3);bs.Inorder();}void BSTreetest3()//右子树有最左节点{BSTree<int, int> bs;bs.insert(10);bs.insert(3);bs.insert(18);bs.insert(2);bs.insert(8);bs.insert(9);bs.insert(12);bs.insert(16);bs.insert(5);bs.insert(6);bs.Inorder();bs.erase(3);bs.Inorder();}void BSTreetest4()//右单支树，{BSTree<int, int> bs;bs.insert(1);bs.insert(2);bs.insert(3);bs.insert(4);bs.Inorder();bs.erase(1);bs.Inorder();}void BSTreetest5()//左单支树，{BSTree<int, int> bs;bs.insert(4);bs.insert(3);bs.insert(2);bs.insert(1);bs.Inorder();bs.erase(1);bs.Inorder();}}