二叉搜索树深度解析：从原理实现到算法应用----《Hello C++ Wrold!》(18)--(C/C++)

Ne0inhk

23 Mar 2026 — 14 min read

文章目录

前言
二叉搜索树（二叉排序树或二叉查找树）
作业部分

前言

二叉搜索树（Binary Search Tree，简称 BST）作为一种重要的树形数据结构，在计算机科学领域有着广泛的应用。它凭借其基于键值的有序性，能够高效地支持数据的插入、删除和查找等操作，是许多复杂算法和系统的基础组件。

本文将围绕二叉搜索树展开全面而深入的探讨。首先，我们将从其核心定义和关键性质出发，帮助读者建立对二叉搜索树的基本认知，包括其通过中序遍历可得到升序序列这一重要特性。随后，详细剖析二叉搜索树的各项基本操作，如插入、查找、删除等，并通过 C++ 代码实现进行具体演示，同时对比递归与非递归实现方式的异同。

此外，我们还将对二叉搜索树与有序数组的二分查找进行对比分析，明确各自的优势与局限。最后，结合一系列经典的算法题目，如二叉搜索树与双向链表的转换、根据遍历序列构造二叉树、二叉树的非递归遍历等，展示二叉搜索树在实际问题中的应用，帮助读者巩固所学知识，提升解决复杂问题的能力。无论是数据结构初学者，还是希望深化对二叉搜索树理解的开发者，都能从本文中获得有价值的参考。

二叉搜索树（二叉排序树或二叉查找树）

概念:是一颗空树或者是具有以下性质的二叉树:

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

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

3.它的左右子树也分别为二叉搜索树

引申:a.用中序遍历去遍历二叉搜索树的结果正好是升序

比如:

c.结点左边所有的树都比结点小;结点右边所有的树都比结点大

二叉搜索树的模拟实现

template<classK>structBSTreeNode{ BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}};template<classK>classBSTree{typedef BSTreeNode<K> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){ _root =Copy(t._root);} BSTree<K>&operator=(BSTree<K> t){swap(_root, t._root);//理解!return*this;}~BSTree(){Destroy(_root);}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;//cur只是里面存的值变成了他的}else{returnfalse;}} cur =newNode(key);//把开辟好的地址存在了cur里面if(key > parent->_key){ parent->_right = cur;//本来里面是nullptr;}else{ parent->_left = cur;}returntrue;}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;}}returnfalse;}boolErase(const K& key){ 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// 找到了{// 左为空if(cur->_left ==nullptr){if(cur == _root){ _root = cur->_right;}else{if(parent->_right == cur){ parent->_right = cur->_right;}else{ parent->_left = cur->_right;}}}// 右为空elseif(cur->_right ==nullptr){if(cur == _root){ _root = cur->_left;}else{if(parent->_right == cur){ parent->_right = cur->_left;}else{ parent->_left = cur->_left;}}}// 左右都不为空 else{// 找替代节点 Node* parent = cur;//这里不能是nullptr,不然要删的地方是根节点就惨了 Node* leftMax = cur->_left;while(leftMax->_right){ parent = leftMax; leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if(parent->_left == leftMax){ parent->_left = leftMax->_left;}else{ parent->_right = leftMax->_left;//这个就是左子树存在右子树的情况}//这里要注意!!! cur = leftMax;}delete cur;returntrue;}}returnfalse;}voidInOrder(){_InOrder(_root); cout << endl;}/*bool FindR(const K& key) { return _FindR(_root, key); } bool InsertR(const K& key) { return _InsertR(_root, key); } bool EraseR(const K& key) { return _EraseR(_root, key); }*/用递归实现这些函数 private:/* bool _EraseR(Node*& root, const K& key)这种树形递归的话一般都要传这个root { if (root == nullptr) return false; if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; // 1、左为空 // 2、右为空 // 3、左右都不为空 if (root->_left == nullptr) { root = root->_right; } else if (root->_right == nullptr) { root = root->_left; } else { Node* leftMax = root->_left;这里可不是传的引用 while (leftMax->_right) { leftMax = leftMax->_right; } swap(root->_key, leftMax->_key); return _EraseR(root->_left, key);这里不能是(leftMax,key)!!! 倒不是它是局部变量的关系 } delete del; return true; } } bool _InsertR(Node*& root, const K& key)这里用&就非常好 { if (root == nullptr) { root = new Node(key); 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 _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) { return _FindR(root->_right, key); } else if (root->_key > key) { return _FindR(root->_left, key); } else { return true; } } */这是用递归实现的函数 void_InOrder(Node* root){if(root ==NULL){return;}_InOrder(root->_left); cout << root->_key <<" ";_InOrder(root->_right);} Node*Copy(Node* root){if(root ==nullptr)returnnullptr; Node* copyroot =newNode(root->_key); copyroot->_left =Copy(root->_left); copyroot->_right =Copy(root->_right);return copyroot;}//这里用的是前序遍历,用中序可不行voidDestroy(Node*& root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root; root =nullptr;}private: Node* _root;};

引申:1.swap对于基本类型，交换的是值;对于指针，交换的是指针里面存的值

二叉搜索树和有序数组二分查找的比较

二分查找的话，插入和删除的效率不太行

二叉搜索树的话，查找排序插入删除效率都不错，但是下限太低了,如图:

两个搜索模型

1.key的搜索模型:快速判断在不在

eg:门禁系统小区车辆出入系统

2.key/value的搜索模型:通过一个值找另外一个值

eg:商场的车辆出入系统高铁实名制车票系统

注意:key一般是不允许重复的信息!

k-v模型的话，在上面的二叉搜索树的模拟实现里面,成员变量要加个value,Insert和erase操作的形参要加value

作业部分

下面关于二叉搜索树正确的说法是（C） A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点 B.给定一棵二叉搜索树的前序和中序遍率历结果，无法确定这棵二叉搜索树 C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的 D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树 引申:使用两个遍历结果确定树的结构， 其中有一个遍历结果必须要是中序遍历结果,这样就可以

牛客网 JZ36 二叉搜索树与双向链表

牛客网 JZ36 二叉搜索树与双向链表 做法:也就是把当前在的地方的left改成指向中序遍历上一个结点，把right改成指向中序遍历下一个结点 在前序遍历改结点的时候:prev一定要传引用 注意:最后返回的结点多半不是开头给的那个结点 易忘这一步:if(prev) prev->right = cur;

代码展示:/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/voidInorder(TreeNode*cur,TreeNode*&prev)//这个要注意{if(cur ==nullptr)return;Inorder(cur->left,prev);//第二个传cur会出事 cur->left = prev;if(prev) prev->right = cur;//这个不能省，叶子结点需要这个 prev = cur;Inorder(cur->right, prev);}classSolution{public: TreeNode*Convert(TreeNode* pRootOfTree){ TreeNode* prev =nullptr;Inorder(pRootOfTree, prev);while(pRootOfTree&&pRootOfTree->left) pRootOfTree = pRootOfTree->left;return pRootOfTree;}};

引申:while和if自己老是容易写混

力扣 606. 根据二叉树创建字符串

力扣 606. 根据二叉树创建字符串 这道题最主要是()的处理: 1.左边为空，右边不为空->左边右边括号都保留 2.左边不为空，右边为空->左边括号保留 3.左边右边都为空->左边右边的括号都不保留 注意:root->val记得转化成string类型的

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: string tree2str(TreeNode* root){ string s1;if(root ==nullptr)return"";else s1+=to_string(root->val);if(root->left||root->right){ s1+="(";s1+=tree2str(root->left); s1+=")";}if(root->right)//{ s1+="(";s1+=tree2str(root->right); s1+=")";}return s1;}};

注意理解这里局部变量s1的用法

力扣 236. 二叉树的最近公共祖先

力扣 236. 二叉树的最近公共祖先 做法1:时间复杂度为O(N平方) 先查找,看p,q看该结点的左边还是右边->一个在左一个在右这个结点就是最近公共祖先 在同一边就要递归去那一边再来 注意:p,q其中一个可能就是最近公共祖先 做法2:时间复杂度为O(n) 搞了两个栈,把到p,q的路径存在了栈里面，之后根据他们的公共祖先高度应该一样来找

代码展示:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:boolFind(TreeNode*root,TreeNode*target,stack<TreeNode*>&path)//{if(root ==nullptr)returnfalse; path.push(root);if(root == target)returntrue;if(Find(root->left,target,path))returntrue;if(Find(root->right,target,path))returntrue; path.pop();returnfalse;} TreeNode*lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){ stack<TreeNode*> p1,q1;Find(root,p,p1);Find(root,q,q1);while(p1.size()>q1.size()) p1.pop();while(p1.size()<q1.size()) q1.pop();while(p1.top()!=q1.top()){ p1.pop(); q1.pop();}return p1.top();}};

上面是做法2的Find的写法

力扣 105. 从前序与中序遍历序列构造二叉树

力扣 105. 从前序与中序遍历序列构造二叉树 做法: 用前序去确定根的位置，用中序去分割左右区间（也就是中序去判断完没完） 注意:root创建空间的写法: TreeNode*root = new TreeNode(preorder[previ]); previ要带引用,传参时不能传个0过去这样!

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: TreeNode*_build(vector<int>& preorder, vector<int>& inorder ,int&previ,int begini,int endi){if(begini>endi)returnnullptr; TreeNode*root =newTreeNode(preorder[previ]);int rooti = begini;while(rooti<=endi){if(preorder[previ]== inorder[rooti])break; rooti++;}++previ; root->left =_build(preorder,inorder,previ,begini,rooti-1); root->right =_build(preorder,inorder,previ,rooti+1,endi);return root;} TreeNode*buildTree(vector<int>& preorder, vector<int>& inorder){int n =(int)preorder.size()-1;int p =0;return_build(preorder,inorder,p,0,n);}};

自己实现的函数:

力扣 106. 从中序与后序遍历序列构造二叉树
 力扣 144. 二叉树的前序遍历(自己要求自己用非递归的形式完成)
力扣 94. 二叉树的中序遍历(自己要求自己用非递归的形式完成)
力扣 145. 二叉树的后序遍历(自己要求自己用非递归的形式完成)

力扣 106. 从中序与后序遍历序列构造二叉树 跟上面做法的区别:previ要从最后开始取,然后根构建完之后先构建右树 代码展示:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: TreeNode*_build(vector<int>& postorder, vector<int>& inorder ,int&previ,int begini,int endi){if(begini>endi)returnnullptr;// TreeNode*root =newTreeNode(postorder[previ]);int rooti = begini;while(rooti<=endi){if(postorder[previ]== inorder[rooti])break; rooti++;}--previ; root->right =_build(postorder,inorder,previ,rooti+1,endi); root->left =_build(postorder,inorder,previ,begini,rooti-1);return root;} TreeNode*buildTree(vector<int>& inorder, vector<int>& postorder){int p = postorder.size()-1;return_build(postorder,inorder,p,0,postorder.size()-1);}};

力扣 144. 二叉树的前序遍历(自己要求自己用非递归的形式完成) 做法:访问左路结点(此时就把结点的值搞到vector里面),左路结点全入栈，后续依次访问左路结点的右子树 力扣 94. 二叉树的中序遍历(自己要求自己用非递归的形式完成) 做法:改成在出栈的时候再把结点存vector里就行了

代码展示: 中序遍历:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: vector<int>inorderTraversal(TreeNode* root){ vector<int>v; stack<TreeNode*> st; TreeNode* cur = root;while(cur||!st.empty()){while(cur){ st.push(cur); cur = cur->left;} TreeNode*top = st.top();st.pop(); v.push_back(top->val); cur = top->right;}return v;}}; 前序遍历:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: vector<int>preorderTraversal(TreeNode* root){ vector<int>v; stack<TreeNode*> st; TreeNode* cur = root;while(cur||!st.empty()){while(cur){ v.push_back(cur->val); st.push(cur); cur = cur->left;} TreeNode*top = st.top();st.pop(); cur = top->right;}return v;}};

力扣 145. 二叉树的后序遍历(自己要求自己用非递归的形式完成) 做法:加一个prev来记录上一个存了的结点是啥 改成在一个结点的右子树为空或者上一个访问结点是右子树的根时再访问这个结点 下面是与前面两道题相差比较大的地方

代码展示:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: vector<int>postorderTraversal(TreeNode* root){ vector<int>v; stack<TreeNode*> st; TreeNode* cur = root; TreeNode*prev =nullptr;while(cur||!st.empty()){while(cur){ st.push(cur); cur = cur->left;} TreeNode*top = st.top();if(top->right==nullptr||top->right == prev){ v.push_back(top->val); prev = top; st.pop();}else cur = top->right;}return v;}};