二叉搜索树（BST，Binary Search Tree）,也称二叉排序树或二叉查找树
二叉搜索树：一棵二叉树，可以为空；如果不为空，则满足以下性质：
1. 非空左子树的所有键值小于其根节点的键值；
2. 非空右子树的所有键值大于其根节点的键值；
3. 左、右子树都是二叉搜索树。
左子树比根小，右子树比根大
默认定义，搜索树不允许冗余
1 插入
template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; bool Insert(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 false; //key 已经有了 } } //error 因为 cur是局部变量出了作用域就销毁了，没有形成链接 //cur = new Node(key); //return true; //链接方法 //找到空位置，还需要找到该节点的父亲位置 } private: Node* _root = nullptr; };当找到空位置，还需要找到该节点的父亲位置，就是cur 每次往下寻找的时候，把cur给父节点。（也就是记录cur每次走过的上一个位置）
#pragma once template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; bool Insert(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 { return false; //key 已经有了 } } //error 因为 cur是局部变量出了作用域就销毁了，没有形成链接 //cur = new Node(key); //return true; //链接方法 //找到空位置，还需要找到该节点的父亲位置 cur = new Node(key); if (key > parent->_key) { parent->_right = cur; } else { parent->_key = cur; } } private: Node* _root = nullptr; };插入+中序遍历
#pragma once #include <iostream> using namespace std; 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 { public: typedef BSTreeNode<K> Node; 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) { parent = cur; cur = cur->_right; } else if(cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; //key 已经有了 } } //error 因为 cur是局部变量出了作用域就销毁了，没有形成链接 //cur = new Node(key); //return true; //链接方法 //找到空位置，还需要找到该节点的父亲位置 cur = new Node(key); //判断链接在左边还是在右边 if (key > parent->_key) { parent->_right = cur; } else { parent->_left = cur; } return true; } //中序遍历 //通常使用 友元或者缺省参数或者套一层 //这里使用套一层 void InOrder() { _InOrder(_root); } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr; }; void TestBSTree1() { int a[] = {10,20,22,8}; BSTree<int> t1; for (auto e : a) { t1.Insert(e); } t1.InOrder(); }2 查找
//查找 bool Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_key) { cur = cur->_right; } else if (key < cur->_key) { cur = cur->_left; } else { return true; } } return false; }3 删除
删除分以下几种情况：
a 删除的节点没有孩子
找到该节点后，先记录该节点的父节点，然后再把节点删除，同时把父节点指向删除节点的指针置空
b 删除的节点有1个孩子
直接让删除节点的父节点直接指向删除节点的孩子节点即可
c 删除的节点有2个孩子
替换法：找到一个节点的值替代你，该节点应该是 左子树最大节点或者右子树的最小节点
删除节点流程：
1 先找到删除节点
2 判断删除节点的哪个子树为空
a 删除节点的左子树为空，然后再去判断删除节点是父节点的左边还是右边
i 父节点的左边，让父节点的左边指向删除节点的右子树
ii 父节点的右边，让父节点的右边指向删除节点的右子树
b 删除节点的右子树为空，然后再去判断删除节点是父节点的左边还是右边
b1 父节点的左边，让父节点的左边指向删除节点的左子树
b2 父节点的右边，让父节点的右边指向删除节点的左子树
c 删除节点的左右子树都不为空
c1 找到一个节点的值替代你，该节点应该是 左子树最大节点或者右子树的最小节点
//找到删除节点,当左子树为空 if (cur->_left == nullptr) { //删除节点的左子树为空，需要判断删除节点是父节点的左边还是右边 if (cur == parent->_left) { parent->_left = cur->_right; } else { //如果是父节点的右边 parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) { //删除节点的右子树为空 if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur; }参考代码如下：
else { //左右都不为空，使用替换法进行删除 //找到一个节点的值替代你，该节点应该是 左子树最大节点或者右子树的最小节点 //查找右子树的最左节点 //这里使用右子树的最小节点 Node* rightMinParent = nullptr; Node* rightMin = cur->_right; //删除节点的右子树一直往左边走， while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } //注意这里不能 交换删除节点的值，然后再去删除节点（这样找不到节点） swap(cur->_key,rightMin->_key); rightMinParent->_left = rightMin->_right; delete rightMin; }但是该代码逻辑存在一个bug:
这里的一个解决方法是：
先直接让rightMinParent指向当前cur节点，之后再单独判断处理rightMinParent
搜索二叉树删除的完整实现代码：
//删除 bool Erase(const K& key) { //删除节点需要记录一下父亲节点 Node* parent = nullptr; 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) //避免 parent == nullptr { _root = cur->_right; } else { //删除节点的左子树为空，需要判断删除节点是父节点的左边还是右边 if (cur == parent->_left) { parent->_left = cur->_right; } else { //如果是父节点的右边 parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr) { //if(parent == nullptr) if (cur == _root) { _root = cur->_left; } else { //删除节点的右子树为空 if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else { //删除节点的左右子树都不为空，使用替换法进行删除 //找到一个节点的值替代你，该节点应该是 左子树最大节点或者右子树的最小节点 //查找右子树的最左节点 //这里使用右子树的最小节点 Node* rightMinParent = cur; Node* rightMin = cur->_right; //删除节点的右子树一直往左边走， while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } //注意这里不能 交换删除节点的值，然后再去删除节点（这样找不到节点） swap(cur->_key, rightMin->_key); if (rightMinParent->_left == rightMin) { rightMinParent->_left = rightMin->_right; } else { rightMinParent->_right = rightMin->_right; } //rightMinParent->_left = rightMin->_right; //error 直接使用容易出现野指针问题 delete rightMin; } return true; } } return false; //没有找打要删除的节点 }搜索二叉树的时间复杂度：平均O(logN)
