跳到主要内容 二叉搜索树深度解析:从原理实现到算法应用 | 极客日志
C++ 算法
二叉搜索树深度解析:从原理实现到算法应用 深入讲解二叉搜索树(BST)的概念、性质及模拟实现。涵盖插入、查找、删除操作的递归与非递归写法,对比其与有序数组二分查找的效率差异。此外,通过多个经典算法题目(如 BST 转双向链表、根据遍历序列构造二叉树、非递归遍历等),展示了 BST 在实际场景中的应用技巧与注意事项。
性能调优 发布于 2026/3/30 更新于 2026/4/13 1 浏览前言
二叉搜索树(Binary Search Tree,简称 BST)作为一种重要的树形数据结构,在计算机科学领域有着广泛的应用。它凭借其基于键值的有序性,能够高效地支持数据的插入、删除和查找等操作,是许多复杂算法和系统的基础组件。
本文将围绕二叉搜索树展开全面而深入的探讨。首先,我们将从其核心定义和关键性质出发,帮助读者建立对二叉搜索树的基本认知,包括其通过中序遍历可得到升序序列这一重要特性。随后,详细剖析二叉搜索树的各项基本操作,如插入、查找、删除等,并通过 C++ 代码实现进行具体演示,同时对比递归与非递归实现方式的异同。
此外,我们还将对二叉搜索树与有序数组的二分查找进行对比分析,明确各自的优势与局限。最后,结合一系列经典的算法题目,展示二叉搜索树在实际问题中的应用,帮助读者巩固所学知识,提升解决复杂问题的能力。无论是数据结构初学者,还是希望深化对二叉搜索树理解的开发者,都能从本文中获得有价值的参考。
二叉搜索树(二叉排序树或二叉查找树)
概念:是一颗空树或者是具有以下性质的二叉树:
若左子树不为空,则左子树上所有节点的值都小于根节点的值
若右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
引申:a. 用中序遍历去遍历二叉搜索树的结果正好是升序
c. 结点左边所有的树都比结点小;结点右边所有的树都比结点大
二叉搜索树的模拟实现
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 {
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); }
bool Insert (const K& key)
{
(_root == ) {
_root = (key);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(key > cur->_key) {
parent = cur;
cur = cur->_right;
} (key < cur->_key) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (key);
(key > parent->_key) {
parent->_right = cur;
} {
parent->_left = cur;
}
;
}
{
Node* cur = _root;
(cur) {
(key > cur->_key) {
cur = cur->_right;
} (key < cur->_key) {
cur = cur->_left;
} {
;
}
}
;
}
{
Node* parent = ;
Node* cur = _root;
(cur) {
(key > cur->_key) {
parent = cur;
cur = cur->_right;
} (key < cur->_key) {
parent = cur;
cur = cur->_left;
} {
(cur->_left == ) {
(cur == _root) {
_root = cur->_right;
} {
(parent->_right == cur) {
parent->_right = cur->_right;
} {
parent->_left = cur->_right;
}
}
} (cur->_right == ) {
(cur == _root) {
_root = cur->_left;
} {
(parent->_right == cur) {
parent->_right = cur->_left;
} {
parent->_left = cur->_left;
}
}
} {
Node* p = cur;
Node* leftMax = cur->_left;
(leftMax->_right) {
p = leftMax;
leftMax = leftMax->_right;
}
(cur->_key, leftMax->_key);
(p->_left == leftMax) {
p->_left = leftMax->_left;
} {
p->_right = leftMax->_left;
}
cur = leftMax;
}
cur;
;
}
}
;
}
{
_InOrder(_root);
cout << endl;
}
:
_InOrder(Node* root) {
(root == ) ;
_InOrder(root->_left);
cout << root->_key << ;
_InOrder(root->_right);
}
{
(root == ) ;
Node* copyroot = (root->_key);
copyroot->_left = (root->_left);
copyroot->_right = (root->_right);
copyroot;
}
{
(root == ) ;
(root->_left);
(root->_right);
root;
root = ;
}
:
Node* _root;
};
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown 转 HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
if
nullptr
new
Node
return
true
nullptr
while
if
else
if
else
return
false
new
Node
if
else
return
true
bool Find (const K& key)
while
if
else
if
else
return
true
return
false
bool Erase (const K& key)
nullptr
while
if
else
if
else
if
nullptr
if
else
if
else
else
if
nullptr
if
else
if
else
else
while
swap
if
else
delete
return
true
return
false
void InOrder ()
private
void
if
NULL
return
" "
Node* Copy (Node* root)
if
nullptr
return
nullptr
new
Node
Copy
Copy
return
void Destroy (Node*& root)
if
nullptr
return
Destroy
Destroy
delete
nullptr
private
引申:swap 对于基本类型,交换的是值;对于指针,交换的是指针里面存的值
二叉搜索树和有序数组二分查找的比较
二分查找的话,插入和删除的效率不太行
二叉搜索树的话,查找排序插入删除效率都不错,但是下限太低了
两个搜索模型
key 的搜索模型:快速判断在不在
eg: 门禁系统 小区车辆出入系统
key/value 的搜索模型:通过一个值找另外一个值
eg: 商场的车辆出入系统 高铁实名制车票系统
注意:key 一般是不允许重复的信息!
k-v 模型的话,在上面的二叉搜索树的模拟实现里面,成员变量要加个 value,Insert 和 erase 操作的形参要加 value
习题与实战 下面关于二叉搜索树正确的说法是(C)
A. 待删除节点有左子树和右子树时,只能使用左子树的最大值节点替换待删除节点
B. 给定一棵二叉搜索树的前序和中序遍率历结果,无法确定这棵二叉搜索树
C. 给定一棵二叉搜索树,根据节点值大小排序所需时间复杂度是线性的
D. 给定一棵二叉搜索树,可以在线性时间复杂度内转化为平衡二叉搜索树
引申:使用两个遍历结果确定树的结构,其中有一个遍历结果必须要是中序遍历结果,这样就可以
牛客网 JZ36 二叉搜索树与双向链表
做法:也就是把当前在的地方的 left 改成指向中序遍历上一个结点,把 right 改成指向中序遍历下一个结点 在前序遍历改结点的时候:prev 一定要传引用 注意:最后返回的结点多半不是开头给的那个结点 易忘这一步:if(prev) prev->right = cur;
void Inorder (TreeNode* cur, TreeNode*& prev) {
if (cur == nullptr ) return ;
Inorder (cur->left, prev);
cur->left = prev;
if (prev) prev->right = cur;
prev = cur;
Inorder (cur->right, prev);
}
class Solution {
public :
TreeNode* Convert (TreeNode* pRootOfTree) {
TreeNode* prev = nullptr ;
Inorder (pRootOfTree, prev);
while (pRootOfTree && pRootOfTree->left) pRootOfTree = pRootOfTree->left;
return pRootOfTree;
}
};
力扣 606. 根据二叉树创建字符串
这道题最主要是 () 的处理:
左边为空,右边不为空 -> 左边右边括号都保留
左边不为空,右边为空 -> 左边括号保留
左边右边都为空 -> 左边右边的括号都不保留
注意:root->val 记得转化成 string 类型的
class Solution {
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;
}
};
力扣 236. 二叉树的最近公共祖先
做法 1:时间复杂度为 O(N 平方) 先查找,看 p,q 看该结点的左边还是右边 -> 一个在左一个在右这个结点就是最近公共祖先 在同一边就要递归去那一边再来 注意:p,q 其中一个可能就是最近公共祖先
做法 2:时间复杂度为 O(n) 搞了两个栈,把到 p,q 的路径存在了栈里面,之后根据他们的公共祖先高度应该一样来找
class Solution {
public :
bool Find (TreeNode* root, TreeNode* target, stack<TreeNode*>& path) {
if (root == nullptr ) return false ;
path.push (root);
if (root == target) return true ;
if (Find (root->left, target, path)) return true ;
if (Find (root->right, target, path)) return true ;
path.pop ();
return false ;
}
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 ();
}
};
力扣 105. 从前序与中序遍历序列构造二叉树
做法:用前序去确定根的位置,用中序去分割左右区间(也就是中序去判断完没完)
注意:root 创建空间的写法:TreeNode*root = new TreeNode(preorder[previ]); previ 要带引用,传参时不能传个 0 过去这样!
class Solution {
public :
TreeNode* _build(vector<int >& preorder, vector<int >& inorder, int & previ, int begini, int endi) {
if (begini > endi) return nullptr ;
TreeNode* root = new TreeNode (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. 从中序与后序遍历序列构造二叉树
跟上面做法的区别:previ 要从最后开始取,然后根构建完之后先构建右树
class Solution {
public :
TreeNode* _build(vector<int >& postorder, vector<int >& inorder, int & previ, int begini, int endi) {
if (begini > endi) return nullptr ;
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 里就行了
class Solution {
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;
}
};
class Solution {
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 来记录上一个存了的结点是啥 改成在一个结点的右子树为空或者上一个访问结点是右子树的根时再访问这个结点 下面是与前面两道题相差比较大的地方
class Solution {
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;
}
};
二叉树的后序非递归遍历中,需要的额外空间包括(C)
A. 一个栈
B. 一个队列
C. 一个栈和一个记录标记的顺序表
D. 一个队列和一个记录标记的顺序表
注意:vector 别忘了他是顺序表!