【初阶与进阶C++详解】第十五篇：二叉树搜索树（操作+实现+应用KVL+性能+习题）

进阶C++详解】第十五篇：二叉树搜索树（操作+实现+应用KVL+性能+习题）"/>

【初阶与进阶C++详解】第十五篇：二叉树搜索树（操作+实现+应用KVL+性能+习题）

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector(vector接口介绍+vector模拟实现+vector迭代器区间构造/拷贝构造/赋值)

【初阶与进阶C++详解】第十篇：list(list接口介绍和使用+list模拟实现+反向迭代器和迭代器适配)

【初阶与进阶C++详解】第十一篇：stack+queue+priority_queue+deque（仿函数）

【初阶与进阶C++详解】第十二篇：模板进阶(函数模板特化+类模板特化+模板分离编译)

【初阶与进阶C++详解】第十三篇：继承(菱形继承+菱形虚拟继承+组合)

【初阶与进阶C++详解】第十四篇：多态（虚函数+重写（覆盖）+抽象类+单继承和多继承）

---

文章目录

• 💙系列文章💙
• 💎一、二叉搜索树概念
• 💎二、二叉搜索树操作实现
• • 🏆1.基本框架
  • 🏆2.插入
  • 🏆3.中序遍历打印
  • 🏆4.查找
  • 🏆5.删除（重点）
• 💎三、二叉搜索树应用
• 💎四、二叉搜索树新能分析
• 💎五、面试题
• • 🏆1.根据二叉树创建字符串
  • 🏆2.二叉树的层序遍历
  • 🏆3.二叉树的层序遍历 II
  • 🏆4.二叉树的最近公共祖先
  • 🏆5.二叉搜索树与双向链表
  • 🏆6.从前序与中序遍历序列构造二叉树
  • 🏆7.从中序与后序遍历序列构造二叉树
  • 🏆8.二叉树的前序遍历
  • img

---

💎一、二叉搜索树概念

二叉搜索树中序遍历是有序的

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

• 若它的右子树不为空，则右子树上所有节点的值都大于于根节点的值

• 它的左右子树都是二叉搜索树

• 这棵树中没有重复的元素

💎二、二叉搜索树操作实现

🏆1.基本框架

构建一个树的节点结构

template<class K>
struct BSTreeNode
{
public:BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(K key):_left(nullptr),_right(nullptr),_key(key){}
};

定义一个根节点，默认值是空

template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
private://成员变量Node* _root=nullptr;
};

🏆2.插入

步骤

1. 首先判断root是否为空，如果为空直接插入数据即可，然后结束

2. 如果root非空则定义==cur（当前节点）和parent（父亲节点）==两个指针遍历，要插入的值比当前节点值小，cur则往左走，要插入的值比当前节点大，cur则往右走，如果等于就返回flase，表示树已经存在这个数据，不用插入，找到正确位置后创建新节点插入即可

3. 返回值使用bool用来判断是否成功插入

   bool Insert(const K& key){//根为空，直接创建空间插入if (_root == nullptr){_root = new Node(key);return true;}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{return false;}}//创建节点进行插入cur = new Node(key);//判断cur要插入到parent的左子树还是右子树if (key > parent->_key) {parent->_right = cur;}else {parent->_left = cur;}return true;}
   

   递归版本：

   bool InsertR(const K& key)//实际调用的函数
   {return _InsertR(_root, key);
   }	//使用引用，这时候的root就是上一个节点的左右子树的别名
   //修改root的同时也会修改上一个子树的左右节点
   bool _InsertR(Node*& root, const K& key)
   {//空代表走完了，则插入if (root == nullptr) {Node* newNode = new Node(key);root = newNode;return true;}if (key > root->_key) {_InsertR(root->_right, key);}else if (key < root->_key) {_InsertR(root->_left, key);}else {return false;//不插入相同值}
   }
   

🏆3.中序遍历打印

在类外面无法访问到私有成员root，无法直接给该函数传参，可以把这个函数定义为private成员

//利用子函数中序遍历   
void InOrder(){_InOrder(_root);}void _InOrder(Node* root){ //递归打印if (root == nullptr)return ;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

🏆4.查找

步骤：

1. 如果查找值key比当前节点的值小，就往左子树走

2. 如果查找值key比当前节点的值大，就往右子树走

3. 如果查找值key和当前节点的值相等，就返回当前节点的指针

   	//搜索二叉树一般不直接操作节点，不需要返回节点的指针//Node* Find(const K& key)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;}}//遍历完则说明查找不到，返回falsereturn false;}

   递归版本：

   bool FindR(const K& key)//实际调用的函数
   {return _FindR(_root, key);
   }
   //递归实现
   bool _FindR(Node* root, const K& key)
   {if (root == nullptr) {return false;}//如果大于右子树if (key > root->_key) {_FindR(root->_right, key);}//如果大于左子树else if (key < root->_key) {_FindR(root->_left, key);}else {return true;}
   }
   

🏆5.删除（重点）

情况：

1. 要删除的节点无孩子节点，比如删除节点1时，直接删除
2. 要删除的节点只有左孩子节点，比如节点2，删除节点2的左孩子并且指向左孩子的右边
3. 要删除的节点只有右孩子节点，比如节点7，删除节点7的右孩子并且指向右孩子的做左边
4. 要删除的节点有左孩子和右孩子，比如节点3，在右子树中找到最小/在左子树中找到最大，将它的值填补到被删除的节点中

//删除去找左子树的最大节点，或者右子树的最小节点//与需要删除的树进行交换，交换之后删除叶子节点bool Erase(const K& key){// 如果树为空，删除失败if (_root == nullptr)return false;Node* prev = nullptr;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{// 找到了，开始删除// 1.左右子树都为空 直接删除  可以归类为左为空// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  // 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除//处理只有右子树时if (cur->_left == nullptr){//如果当前节点为根节点，则让右子树成为新的根节点if (cur == _root){_root = _root->_right;}else{//判断当前节点是他父节点的哪一个子树if (prev->_left == cur){prev->_left = cur->_right;}else {prev->_right = cur->_right;}}delete cur;}//处理只有左子树时else if (cur->_right == nullptr){//如果当前节点为根节点，则让左子树成为新的根节点if (cur == _root){_root = _root->_left;}else{if (prev->_left == cur){prev->_left = cur->_left;}else {prev->_right = cur->_left;}}delete cur;}//左右都有孩子else {//将cur和右子树的最小值节点进行交换Node* minParent = cur;//不给空放置要删除的是头节点Node* minRight = cur->_right;//右子树找到最左边的节点while (minRight->_left){minParent = minRight;minRight = minRight->_left;}//替换节点swap(minRight->_key, cur->_key);//如果要删除的是minParent的左子树，则将minParent指向左子树的右边if (minParent->_left == minRight){minParent->_left = minRight->_right;}//如果要删除的是minParent的右子树，则将minParent指向右子树的右边else {minParent->_right = minRight->_right;}delete minRight;}return true;}}return false;}

递归版本：

bool _EraseR(Node*& root, const K& key)
{//根为空，返回falseif (root == nullptr) {return false;}if (key > root->_key) {_EraseR(root->_right, key);}else if (key < root->_key) {_EraseR(root->_left, key);}else {Node* del = root;//保存变量用于删除if (root->_left == nullptr){//传引用的作用//root不仅是当前递归到的节点，同时是上一个节点的左右子树的别名//对该节点的操作会直接改变上一个节点的左右子树root = root->_right;}else if (root->_right == nullptr){root = root->_left;}//左右都有孩子else {//将cur和右子树的最小值节点进行交换Node* minRight = root->_right;while (minRight->_left) //判断的是left，不然会走到空然后交换{minRight = minRight->_left;}swap(minRight->_key, root->_key);//转换到下一个子树中删除return _EraseR(root->_right, key);}delete del;return true;}
}

💎三、二叉搜索树应用

1. K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。

2. KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value，将<key, value>绑定

   • 排序依据key来排序，而不是value

   • key不可以修改，但是value可以修改

   • 在保存键值关系的同时，去重+排序

     下面是修改代码（只用修改查找和插入即可），和具体应用

     template <class K, class V>
     struct BSTNode
     {
     BSTNode<K, V>* _left;
     BSTNode<K, V>* _right;
     K _key;
     V _value;BSTNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key),_value(value)
     {}
     };
     template <class K, class V>
     class BSTree //Binary Search Tree
     {
     typedef BSTNode<K, V> Node;
     public:
     ~BSTree()
     {Node* cur = _root;while (cur){Erase(cur->_key);cur = _root;}
     }//找到了则返回地址
     Node* Find(const K& key)
     {if (_root == nullptr)return nullptr;Node* cur = _root;while (cur){// 小于往左边走if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn cur;}return nullptr;
     }
     bool Insert(const K& key, const V& value)
     {// 没有节点时第一个节点就是根节点if (_root == nullptr){_root = new Node(key, value);return true;}// 用一个父亲节点记录cur的上一个节点Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;// 小于往左边走if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn false;// 已有的节点不插入，此次插入失败}cur = new Node(key, value);// 判断应该插在父节点的左边还是右边if (cur->_key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;
     }
     bool Erase(const K& key)
     {// 如果树为空，删除失败if (_root == nullptr)return false;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{// 找到了，开始删除// 1.左右子树都为空 直接删除  可以归类为左为空// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  // 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除if (cur->_left == nullptr){// 要删除节点为根节点时，直接把右子树的根节点赋值给——root// 根节点的话会导致parent为nullptrif (_root == cur){_root = _root->_right;}else{// 左为空，父亲指向我的右// 判断cur在父亲的左还是右if (parent->_left == cur) // cur->_key < parent->_keyparent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr){if (_root == cur){_root = _root->_left;}else{// 右为空，父亲指向我的左// 判断cur在父亲的左还是右if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}else{// 找右子树中最小的节点Node* rightMinParent = cur;Node* rightMin = cur->_right;// 去右子树找while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//swap(cur->_key, rightMin->_key);// 替代删除cur->_key = rightMin->_key;// 转换成了第一种情况  左为空if (rightMinParent->_left == rightMin)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;rightMin = nullptr;}return true;}}return false;}void InOrder(){// 利用子函数遍历_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};void TestBSTree_KV1(){// 创建一个简易的字典BSTree<string, string> dict;dict.Insert("苹果", "apple");dict.Insert("排序", "sort");dict.Insert("培养", "cultivate");dict.Insert("通过", "pass");dict.Insert("apple", "苹果");dict.Insert("sort", "排序");dict.Insert("cultivate", "培养");dict.Insert("pass", "通过");string str;while (cin >> str){//BSTNode<string, string>* ret = dict.Find(str);aotu ret = dict.Find(str);if (ret){cout << ret->_value << endl;}else{cout << "本字典无此词" << endl;}}void TestBSTree_KV2(){// 统计水果个数BSTree<string, int> countTree;string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };for (auto e : strArr){BSTNode<string, int>* ret = countTree.Find(e);if (ret == nullptr){// 第一次出现则插入countTree.Insert(e, 1);}else{//如果出现过了则增加出现次数即可ret->_value++;}}countTree.InOrder();}
     

💎四、二叉搜索树新能分析

理想情况情况（完全二叉树），二叉搜索树的插入和删除的效率都是O(logN)，极端情况（一条链）会导致效率变成O(N)。

💎五、面试题

🏆1.根据二叉树创建字符串

传送门

输入：root = [1,2,3,4]
输出：“1(2(4))(3)”
解释：初步转化后得到 “1(2(4)())(3()())” ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。

思路：

​ 最后是否加括号有三种情况，左右两边都是空，那么不要加括号，左边是空右边不是空，保留括号，右边是空左边不是空，不要加括号，然后递归循环即可

class Solution {
public://左右两边都是空，那么不用加（）//左边是空右边不是空，要加（）//右边是空左边不是空，不要加（）string tree2str(TreeNode* root) {if(root == nullptr)return "";string str;//to_string 常量转字符串str += to_string(root->val);//如果左边是空，右边不是空，则直接加（）if(root->left){str += '(';str += tree2str(root->left);str += ')';}else if(root->right){str += "()";}//如果右边是空，则直接跳过if(root->right){str += '(';str += tree2str(root->right);str += ')';}return str;}
};

🏆2.二叉树的层序遍历

传送门

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

思路：

​ 利用变量levelsize控制一层变量，然后将每一层变量放到队列q中，如果q为空则表示遍历完了

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;//为空直接返回if(root == nullptr)return vv;queue<TreeNode*> q;int levelsize = 1;q.push(root);while(!q.empty()){vector<int> v;//levelsize计算每一层有多少个数据 while(levelsize--){//将每一层的数据依次放到v中TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}//将v放到vv中vv.push_back(v);levelsize = q.size();}return vv;}
};

🏆3.二叉树的层序遍历 II

传送门

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

思路同第二题，最后逆置即可

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;//为空直接返回if(root == nullptr)return vv;queue<TreeNode*> q;int levelsize = 1;q.push(root);while(!q.empty()){vector<int> v;//levelsize计算每一层有多少个数据 while(levelsize--){//将每一层的数据依次放到v中TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}//将v放到vv中vv.push_back(v);levelsize = q.size();}reverse(vv.begin(), vv.end());return vv;}
};

🏆4.二叉树的最近公共祖先

传送门

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

思路：

​ 当一个节点是祖先的时候，一种情况是，pq两个点都在祖先的左右两边，另一种情况是pq两点中有一个点是祖先，如果pq两点中有一个是祖先的话，那么返回root即可，如果当前root节点不是pq的话，那么就从root的左右子树中找pq，此时我们定义一个子树中寻找节点的函数，用来寻找root子树中是否存在pq，如果pq存在root左右两边的话，那么返回root祖先，如果pq存在root同一边的话，那么将root移动到一边寻找即可

class Solution {
public:bool IsInBinry(TreeNode* root, TreeNode* x){//如果为空，返回空if(root == nullptr)return false;//如果根找到了就返回trueif(root == x)return true;//如果根没有找到就向左右子树中寻找return IsInBinry(root->left, x)||IsInBinry(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr)return root;//如果p或者q是root说明找到了其中一个节点if(p == root || q == root)return root;//如果在当前节点没有找到则左右分开找bool qInleft = IsInBinry(root->left, q);bool qInright = IsInBinry(root->right, q);bool pInleft = IsInBinry(root->left, p);bool pInright = IsInBinry(root->right, p);;//如果当前pq一个在左一个在右，说明当前root是祖先if((qInleft && pInright)||(qInright && pInleft))return root;//如果qp都在左那么就往左边去找else if(qInleft && pInleft)return lowestCommonAncestor(root->left, p, q);else return lowestCommonAncestor(root->right, p, q);}
};

🏆5.二叉搜索树与双向链表

传送门

思路：

​ 通过中序遍历，将节点左子树的右边指向节点，利用一前一后指针将每一个系欸但双向

class Solution {
public://使用引用，这样在不同的递归时，都不会改变void InOrder(Node* cur, Node*& prev){if(cur == nullptr) return;InOrder(cur->left, prev);//每次将root左子树给prevcur->left = prev;//当prev不为空时，将prev右指向curif(prev)prev->right = cur;//将prev移动到curprev = cur;InOrder(cur->right, prev);}Node* treeToDoublyList(Node* root) {if(root == nullptr)return nullptr;Node* prev = nullptr;InOrder(root, prev);Node* head = root;while(head->left){head = head->left;}return head;}
};

🏆6.从前序与中序遍历序列构造二叉树

传送门

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

思路：

​ 首先通过前序遍历找到root然后通过中序遍历确定root位置，那么根据中序遍历root位置可知，在root左边是左树，右边是右树，将中序区间划分为[begini, rooti-1]rooti[rooti+1, endi]，然后将root的左右树分别递归划分

class Solution {
public://prei修改了，防止出作用域销毁TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int begini, int endi){//中间序列不存在说明找到空if(begini>endi){return nullptr;}TreeNode* root = new TreeNode(preorder[prei]);++prei;//划分左右区间int rooti = begini;while(rooti<=endi){if(root->val == inorder[rooti])break;elserooti++;}//[begini, rooti-1]rooti[rooti+1, endi]root->left = _buildTree(preorder, inorder, prei, begini, rooti-1);root->right = _buildTree(preorder, inorder, prei, rooti+1, endi);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int prei = 0, begini = 0, endi = inorder.size()-1;return _buildTree(preorder, inorder, prei, begini, endi);}
};

🏆7.从中序与后序遍历序列构造二叉树

传送门

思路：

思路和前序中序遍历差不多，首先从后序遍历的最后开始，找到根节点，然后从中序遍历中找到[begini, rooti-1]rooti[rooti+1, endi]区间，然后将每个区间递归遍历，注意的是，递归顺序是后序中序遍历时，递归是先右再左

class Solution {
public://prei修改了，防止出作用域销毁TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& nexti, int begini, int endi){//中间序列不存在说明找到空if(begini>endi){return nullptr;}TreeNode* root = new TreeNode(postorder[nexti]);nexti--;//划分左右区间int rooti = begini;while(rooti<endi){if(root->val == inorder[rooti])break;elserooti++;}//[begini, rooti-1]rooti[rooti+1, endi]root->right = _buildTree(inorder, postorder, nexti, rooti+1, endi);root->left = _buildTree(inorder, postorder, nexti, begini, rooti-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int nexti = postorder.size()-1, begini = 0, endi = inorder.size()-1;return _buildTree(inorder, postorder, nexti, begini, endi);}
};

🏆8.二叉树的前序遍历

传送门

输入：root = [1,null,2,3]
输出：[1,2,3]

思路：

​ 前序遍历是根左右，所以我们要优先·访问根节点，然后递归访问左节点和右节点，其他中序遍历和后续遍历差不多

class Solution {
public:void _preorderTraversal(TreeNode* root, vector<int>& v){if(root == nullptr)return ;v.push_back(root->val);_preorderTraversal(root->left, v);_preorderTraversal(root->right, v);}vector<int> preorderTraversal(TreeNode* root) {vector<int> v;_preorderTraversal(root, v);return v;}
};

---