【初阶与进阶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.基本框架

构建一个树的节点结构

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

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

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

🏆2.插入

步骤

1. 首先判断root是否为空，如果为空直接插入数据即可，然后结束
2. 如果root非空则定义==cur（当前节点）和parent（父亲节点）==两个指针遍历，要插入的值比当前节点值小，cur则往左走，要插入的值比当前节点大，cur则往右走，如果等于就返回flase，表示树已经存在这个数据，不用插入，找到正确位置后创建新节点插入即可
3. 返回值使用bool用来判断是否成功插入boolInsert(const K& key){//根为空，直接创建空间插入if(_root ==nullptr){ _root =newNode(key);returntrue;} Node* parent =nullptr; Node* cur = _root;//找到合适的插入位置while(cur){//比根节点大则查找右子树if(key > cur->_key){ parent = cur; cur = cur->_right;}//比根节点小则查找左子树elseif(key < cur->_key){ parent = cur; cur = cur->_left;}//有相同元素不执行插入else{returnfalse;}}//创建节点进行插入 cur =newNode(key);//判断cur要插入到parent的左子树还是右子树if(key > parent->_key){ parent->_right = cur;}else{ parent->_left = cur;}returntrue;}递归版本：boolInsertR(const K& key)//实际调用的函数{return_InsertR(_root, key);}//使用引用，这时候的root就是上一个节点的左右子树的别名//修改root的同时也会修改上一个子树的左右节点bool_InsertR(Node*& root,const K& key){//空代表走完了，则插入if(root ==nullptr){ Node* newNode =newNode(key); root = newNode;returntrue;}if(key > root->_key){_InsertR(root->_right, key);}elseif(key < root->_key){_InsertR(root->_left, key);}else{returnfalse;//不插入相同值}}

🏆3.中序遍历打印

在类外面无法访问到私有成员

root

，无法直接给该函数传参，可以把这个函数定义为

private

成员

//利用子函数中序遍历   voidInOrder(){_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)boolFind(const K& key){ Node* cur = _root;while(cur){//比根节点大则查找右子树if(key > cur->_key){ cur = cur->_right;}//比根节点小则查找左子树elseif(key < cur->_key){ cur = cur->_left;}//相同则返回else{returntrue;}}//遍历完则说明查找不到，返回falsereturnfalse;}递归版本：boolFindR(const K& key)//实际调用的函数{return_FindR(_root, key);}//递归实现bool_FindR(Node* root,const K& key){if(root ==nullptr){returnfalse;}//如果大于右子树if(key > root->_key){_FindR(root->_right, key);}//如果大于左子树elseif(key < root->_key){_FindR(root->_left, key);}else{returntrue;}}

🏆5.删除（重点）

情况：

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

//删除去找左子树的最大节点，或者右子树的最小节点//与需要删除的树进行交换，交换之后删除叶子节点boolErase(const K& key){// 如果树为空，删除失败if(_root ==nullptr)returnfalse;

        Node* prev =nullptr;
        Node* cur = _root;while(cur){// 小于往左边走if(key > cur->_key){
                prev = cur;
                cur = cur->_right;}elseif(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;}//处理只有左子树时elseif(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;}returntrue;}}returnfalse;}

递归版本：

bool_EraseR(Node*& root,const K& key){//根为空，返回falseif(root ==nullptr){returnfalse;}if(key > root->_key){_EraseR(root->_right, key);}elseif(key < root->_key){_EraseR(root->_left, key);}else{
        Node* del = root;//保存变量用于删除if(root->_left ==nullptr){//传引用的作用//root不仅是当前递归到的节点，同时是上一个节点的左右子树的别名//对该节点的操作会直接改变上一个节点的左右子树
            root = root->_right;}elseif(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;returntrue;}}

💎三、二叉搜索树应用

1. K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。
2. KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value，将<key, value>绑定- 排序依据key来排序，而不是value- key不可以修改，但是value可以修改- 在保存键值关系的同时，去重+排序下面是修改代码（只用修改查找和插入即可），和具体应用template<classK,classV>structBSTNode{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<classK,classV>classBSTree//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)returnnullptr; Node* cur = _root;while(cur){// 小于往左边走if(key < cur->_key) cur = cur->_left;elseif(key > cur->_key) cur = cur->_right;elsereturn cur;}returnnullptr;}boolInsert(const K& key,const V& value){// 没有节点时第一个节点就是根节点if(_root ==nullptr){ _root =newNode(key, value);returntrue;}// 用一个父亲节点记录cur的上一个节点 Node* parent =nullptr; Node* cur = _root;while(cur){ parent = cur;// 小于往左边走if(key < cur->_key) cur = cur->_left;elseif(key > cur->_key) cur = cur->_right;elsereturnfalse;// 已有的节点不插入，此次插入失败} cur =newNode(key, value);// 判断应该插在父节点的左边还是右边if(cur->_key < parent->_key){ parent->_left = cur;}else{ parent->_right = cur;}returntrue;}boolErase(const K& key){// 如果树为空，删除失败if(_root ==nullptr)returnfalse; Node* parent =nullptr; Node* cur = _root;while(cur){// 小于往左边走if(key < cur->_key){ parent = cur; cur = cur->_left;}elseif(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->_key parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur; cur =nullptr;}elseif(cur->_right ==nullptr){if(_root == cur){ _root = _root->_left;}else{// 右为空，父亲指向我的左// 判断cur在父亲的左还是右if(parent->_left == cur) parent->_left = cur->_left;else parent->_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;else rightMinParent->_right = rightMin->_right;delete rightMin; rightMin =nullptr;}returntrue;}}returnfalse;}voidInOrder(){// 利用子函数遍历_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;};voidTestBSTree_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;}}voidTestBSTree_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)" 。

思路：

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

classSolution{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 +=')';}elseif(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为空则表示遍历完了

classSolution{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]]

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

classSolution{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移动到一边寻找即可

classSolution{public:boolIsInBinry(TreeNode* root, TreeNode* x){//如果为空，返回空if(root ==nullptr)returnfalse;//如果根找到了就返回trueif(root == x)returntrue;//如果根没有找到就向左右子树中寻找returnIsInBinry(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都在左那么就往左边去找elseif(qInleft && pInleft)returnlowestCommonAncestor(root->left, p, q);elsereturnlowestCommonAncestor(root->right, p, q);}};

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

传送门

思路：

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

classSolution{public://使用引用，这样在不同的递归时，都不会改变voidInOrder(Node* cur, Node*& prev){if(cur ==nullptr)return;InOrder(cur->left, prev);//每次将root左子树给prev
        cur->left = prev;//当prev不为空时，将prev右指向curif(prev)
            prev->right = cur;//将prev移动到cur
        prev = cur;InOrder(cur->right, prev);}
    Node*treeToDoublyList(Node* root){if(root ==nullptr)returnnullptr;
        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的左右树分别递归划分

classSolution{public://prei修改了，防止出作用域销毁
    TreeNode*_buildTree(vector<int>& preorder, vector<int>& inorder,int& prei,int begini,int endi){//中间序列不存在说明找到空if(begini>endi){returnnullptr;}
        TreeNode* root =newTreeNode(preorder[prei]);++prei;//划分左右区间int rooti = begini;while(rooti<=endi){if(root->val == inorder[rooti])break;else
                rooti++;}//[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]区间，然后将每个区间递归遍历，注意的是，递归顺序是后序中序遍历时，递归是先右再左

classSolution{public://prei修改了，防止出作用域销毁
    TreeNode*_buildTree(vector<int>& inorder, vector<int>& postorder,int& nexti,int begini,int endi){//中间序列不存在说明找到空if(begini>endi){returnnullptr;}
        TreeNode* root =newTreeNode(postorder[nexti]);
        nexti--;//划分左右区间int rooti = begini;while(rooti<endi){if(root->val == inorder[rooti])break;else
                rooti++;}//[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]

思路：

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

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