大家好，我是讯享网，很高兴认识大家。

讯享网

---

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

---

 目录

一、二叉搜索树的概念

二、二叉搜索树的中序遍历用于排序+去重

三、二叉搜索树的查找

1、查找的非递归写法

2、查找的递归写法

四、二叉搜索树的插入

1、插入的非递归写法

2、插入的递归写法

五、二叉搜索树的删除

1、删除的非递归写法

2、删除的递归写法

六、二叉搜索树的使用场景

1、key搜索模型（节点存key）

2、key搜索模型整体代码

3、key/value搜索模型（节点既存key又存value）

4、key/value搜索模型整体代码

---

一、二叉搜索树的概念

        二叉搜索树又称二叉排序树。

        空树是二叉搜索树，如果一棵树不是空树，需要满足如下情况便可称其为二叉搜索树：

        1、左子树上每一个键值均小于根节点；

        2、右子树上每一个键值均大于根节点；

        3、左右子树均为二叉搜索树。

template <class K> struct BSTreeNode//用于生成二叉搜索树的节点 { BSTreeNode(const K& key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template <class K> struct BSTree//表示整颗二叉搜索树 { typedef BSTreeNode<K> Node; BSTree() :_root(nullptr) {} private: Node* _root; };

讯享网

二、二叉搜索树的中序遍历用于排序+去重

        通过上面那张图不难发现，用二叉搜索树走个中序，就是升序+去重排序，这也是二叉搜索树又被称为二叉排序树的原因。

        使用InOrder调用_InOrder的原因是类外面传参传不了私有的_root，所以采用多套一层的方法。

讯享网//中序遍历 void _InOrder(Node* _root) { if (_root == nullptr) { return; } _InOrder(_root->_left); std::cout << _root->_key << " "; _InOrder(_root->_right); } void InOrder()//因为外部取不到_root,所以这里套了一层调用函数 { _InOrder(_root); std::cout << std::endl; }

三、二叉搜索树的查找

        对于任意一颗二叉搜索树，最坏的查找次数是数的高度次，时间复杂度O(N)。

        如果全国14亿人的身份证号按照完全二叉搜索树进行排列，<14亿<

，也就是说，在14亿人口中，我找到你最坏的情况下仅需要找31次。

        可以看到，二叉搜索树针对满二叉树、完全二叉树这种结构平衡的树时，查找效率为O（logN），但是二叉搜索树如果处理有序或接近有序的数据，可能出现上图单子树的情况，大大降低了查找效率，所以它并不是一个很成熟的数据结构，需要平衡二叉树和红黑树对该缺陷进行弥补。（手撕平衡二叉树和红黑树博客尽量一个月左右补上）

1、查找的非递归写法

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

        根据二叉搜索树的性质，左树均小于根，右树均大于根，进行查找。

2、查找的递归写法

讯享网Node* _FindR(Node* root,const K& key) { if (root == nullptr) return nullptr; if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else return root; } bool FindR(const K& key) { return _FindR(_root, key) == nullptr ? false : true; }

四、二叉搜索树的插入

        二叉搜索树的插入需要考虑插入后，需要维持二叉搜索树的形态。

1、插入的非递归写法

bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key);//BSTreeNode对象中存放key值，构造一个二叉搜索树节点 } else { Node* parent = nullptr; Node* cur = _root; //cur一直走，走到要插入的位置 while (cur) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else//说明数字重复，插入失败 return false; } cur = new Node(key); //判断插入节点放在parent节点的左子树还是右子树 if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } } return true; }

        1、如果根是空，插入的节点就是新的根；

        2、如果根不为空，就先根据二叉搜索树的性质找到该节点要插入的位置，如果路上遇到相同的数，插入失败；

        3、再判断一下，是要插入父亲的左边还是右边即可。

2、插入的递归写法

讯享网bool _InsertR(Node*& root, const K& key)//形参是root的引用 { if (root == nullptr) { root = new Node(key);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系 return true; } if (root->_key < key) return _InsertR(root->_right, key);//看到这个root->_right没，它是下一层root的别名 else if (root->_key > key) return _InsertR(root->_left, key);//看到这个root->_left没，它是下一层root的别名 else//说明相等，插入失败 return false; } bool InsertR(const K& key) { return _InsertR(_root, key); }

        递归写法巧就巧在形参是指针的引用，例如我现在要插入9，下层的root是上一层root->_left的别名， 下层root = new Node(key);即为上一层root->_left=new Node(key);这样插入节点就自动和父节点连接上了。

五、二叉搜索树的删除

        二叉搜索树的节点进行删除后，同样需要维持二叉搜索树的形态。

        二叉搜索树的删除无非是三种情况：

1、删除的非递归写法

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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了 { _root = _root->_right; } else { if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤” parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空 { if (cur == _root) { _root = _root->_left; } else { if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; } else//被删除节点左右孩子均不为空 { //左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根（对被删除节点进行替换） Node* rightMin = cur->_right;//这里选用右树的最小值进行更换 Node* rightMinParent = cur; while (rightMin->_left!=nullptr)//因为找最小值，不停找左树即可 { rightMinParent = rightMin; rightMin = rightMin->_left; } //std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢 cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载 //rightMin的左节点必为空，判断父节点的链接方式即可 if (rightMinParent->_left == rightMin)//两种情况，第一种如上方图删除8，实际干掉9位置，需要将10的左连至9的右 rightMinParent->_left = rightMin->_right; else if (rightMinParent->_right == rightMin)//第二种如上方图删除10，实际干掉14，需要将10的右连至14的右 rightMinParent->_right = rightMin->_right; delete rightMin; } return true; } } return false; }

        1、先通过二叉搜索树的性质找到要删除的节点；

        2、找到需要删除的节点后，分三种情况进行讨论：

        一、被删除节点的左孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的右孩子。（如图删除9和14）

        二、被删除节点的左孩子存在但右孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的左孩子。（如图删除9）

        三、被删除的节点均不为空，可以选用左树最大节点或者右树最小节点对被删除节点进行值替换，问题转化为第一种或第二种情况。（详见代码注释）

2、删除的递归写法

讯享网bool _EarseR(Node*& root, const K& key)//形参给了引用，意义同插入的递归写法 { if (root == nullptr) { return false; } if (root->_key < key) return _EarseR(root->_right, key); else if (root->_key > key) return _EarseR(root->_left, key); else//说明找到了要删除的节点,无需考虑root的父亲为空 { Node* del = root; if (root->_left == nullptr)//被删除节点的左为空 root = root->_right;//让root连接root的右树，因为是引用，所以父节点和root是连接的 else if (root->_right == nullptr)//被删除节点左不为空但右为空 root = root->_left; else//root左右子树均不为空 { Node* rightMin = root->_right; while (rightMin->_left!=nullptr)//找到被删除节点的右树最小节点 { rightMin = rightMin->_left; } root->_key = rightMin->_key;//找到了交换key //对子树进行递归删除 return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归 } delete del; return true; } } bool EraseR(const K& key) { return _EarseR(_root, key); }

        找到节点后，同样需要分三种情况讨论。

        1、被删除节点左树为空；

        2、被删除节点左树不为空但右树为空；

        3、被删除节点左右子树均不为空。

六、二叉搜索树的使用场景

1、key搜索模型（节点存key）

        key搜索模型只用key作关键码，结构中只需存key，key即为需要搜索到的值。

        例如对英语单词拼写的检查，可以将词库中的所有单词存入二叉搜索树，通过二叉搜索树中检索单词是否存在，达到拼写报错目的。

2、key搜索模型整体代码

template <class K> struct BSTreeNode { BSTreeNode(const K& key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template <class K> struct BSTree { typedef BSTreeNode<K> Node; BSTree() :_root(nullptr) {} //插入节点 bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key);//BSTreeNode对象中存放key值 } else { Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else//说明数字重复 return false; } cur = new Node(key); //判断插入节点放在parent节点的左子树还是右子树 if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } } return true; } bool InsertR(const K& key) { return _InsertR(_root, key); } //中序遍历 void InOrder()//因为外部取不到_root,所以这里套了一层调用函数 { _InOrder(_root); std::cout << std::endl; } //查找 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 FindR(const K& key) { return _FindR(_root, key) == nullptr ? false : true; } 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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了 { _root = _root->_right; } else { if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤” parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空 { if (cur == _root) { _root = _root->_left; } else { if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; } else//被删除节点左右孩子均不为空 { //左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根 Node* rightMin = cur->_right;//这里选用右树的最小值进行更换 Node* rightMinParent = cur; while (rightMin->_left!=nullptr) { rightMinParent = rightMin; rightMin = rightMin->_left; } //std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢 cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载 if (rightMinParent->_left == rightMin)//两种情况，第一种如图删除8，实际干掉9位置，需要将10的左连至9的右 rightMinParent->_left = rightMin->_right; else if (rightMinParent->_right == rightMin)//第二种如图删除10，实际干掉14，需要将10的右连至14的右 rightMinParent->_right = rightMin->_right; delete rightMin; } return true; } } return false; } bool EraseR(const K& key) { return _EarseR(_root, key); } private: Node* _root; void _InOrder(Node* _root) { if (_root == nullptr) { return; } _InOrder(_root->_left); std::cout << _root->_key << " "; _InOrder(_root->_right); } Node* _FindR(Node* root,const K& key) { if (root == nullptr) return nullptr; if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else return root; } bool _InsertR(Node*& root, const K& key)//形参是root的引用 { if (root == nullptr) { root = new Node(key);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系 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 _EarseR(Node*& root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) return _EarseR(root->_right, key); else if (root->_key > key) return _EarseR(root->_left, key); else//说明找到了要删除的节点,无需考虑root的父亲为空 { Node* del = root; if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else//root左右子树均不为空 { Node* rightMin = root->_right; while (rightMin->_left!=nullptr)//找到右树最小节点 { rightMin = rightMin->_left; } root->_key = rightMin->_key; return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归 } delete del; return true; } } };

3、key/value搜索模型（节点既存key又存value）

        key/value搜索模型指每一个key值，都有与之对应的value值，例如英汉互译，一个英文单词可以对应一个翻译字符串。该模型还可以用于统计相同内容出现次数。（举例代码见下方测试函数。）

4、key/value搜索模型整体代码

讯享网namespace KV { template <class K,class V> struct BSTreeNode { BSTreeNode(const K& key,const V& value) :_left(nullptr) , _right(nullptr) , _key(key) ,_value(value) {} BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _right; K _key; V _value; }; template <class K,class V> struct BSTree { typedef BSTreeNode<K,V> Node; BSTree() :_root(nullptr) {} //插入节点 bool Insert(const K& key,const V& value) { if (_root == nullptr) { _root = new Node(key,value);//BSTreeNode对象中存放key值 } else { Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else//说明数字重复 return false; } cur = new Node(key, value); //判断插入节点放在parent节点的左子树还是右子树 if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } } return true; } bool InsertR(const K& key,const V& value) { return _InsertR(_root, key, value); } //中序遍历 void InOrder()//因为外部取不到_root,所以这里套了一层调用函数 { _InOrder(_root); std::cout << std::endl; } //查找 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; } Node* FindR(const K& key) { return _FindR(_root, key); } 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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了 { _root = _root->_right; } else { if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤” parent->_left = cur->_right; else parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空 { if (cur == _root) { _root = _root->_left; } else { if (parent->_left == cur) parent->_left = cur->_left; else parent->_right = cur->_left; } delete cur; } else//被删除节点左右孩子均不为空 { //左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根 Node* rightMin = cur->_right;//这里选用右树的最小值进行更换 Node* rightMinParent = cur; while (rightMin->_left != nullptr) { rightMinParent = rightMin; rightMin = rightMin->_left; } //std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢 cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载 cur->_value = rightMin->_value; if (rightMinParent->_left == rightMin)//两种情况，第一种如图删除8，实际干掉9位置，需要将10的左连至9的右 rightMinParent->_left = rightMin->_right; else if (rightMinParent->_right == rightMin)//第二种如图删除10，实际干掉14，需要将10的右连至14的右 rightMinParent->_right = rightMin->_right; delete rightMin; } return true; } } return false; } bool EraseR(const K& key) { return _EarseR(_root, key); } private: Node* _root; void _InOrder(Node* _root) { if (_root == nullptr) { return; } _InOrder(_root->_left); std::cout << _root->_key << " "<<_root->_value; _InOrder(_root->_right); } Node* _FindR(Node* root, const K& key) { if (root == nullptr) return nullptr; if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else return root; } bool _InsertR(Node*& root, const K& key, const V& value)//形参是root的引用 { if (root == nullptr) { root = new Node(key,value);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系 return true; } if (root->_key < key) return _InsertR(root->_right, key，value); else if (root->_key > key) return _InsertR(root->_left, key，value); else return false; } bool _EarseR(Node*& root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) return _EarseR(root->_right, key); else if (root->_key > key) return _EarseR(root->_left, key); else//说明找到了要删除的节点,无需考虑root的父亲为空 { Node* del = root; if (root->_left == nullptr) root = root->_right; else if (root->_right == nullptr) root = root->_left; else//root左右子树均不为空 { Node* rightMin = root->_right; while (rightMin->_left != nullptr)//找到右树最小节点 { rightMin = rightMin->_left; } root->_key = rightMin->_key; root->_value = rightMin->_value; return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归 } delete del; return true; } } }; } void testKV1()//中英互译 { KV::BSTree<std::string, std::string> dic; dic.Insert("data", "数据"); dic.Insert("algorithm", "算法"); dic.Insert("map", "地图、映射"); dic.Insert("Linux", "一款开源免费的操作系统"); std::string str; while (std::cin >> str) { KV::BSTreeNode<std::string, std::string>* ret = dic.Find(str); if (ret != nullptr) { std::cout << "中文翻译：" << ret->_value << std::endl; } else std::cout << "查找失败！" << std::endl; } } void testKV2()//用于统计次数 { std::string arr[] = { "数学", "语文", "数学", "语文", "数学", "数学", "英语","数学", "英语", "数学", "英语" }; KV::BSTree<std::string, int> count; for (auto& e : arr) { KV::BSTreeNode<std::string, int>* ret = count.Find(e); if (ret != nullptr) { ret->_value++; } else { count.Insert(e,1); } } count.InOrder(); }