前言
二叉搜索树（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) // 插入不了重复的值
{
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);
if (key > parent->_key) {
parent->_right = cur;
} else {
parent->_left = cur;
}
return true;
}
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;
}
}
return false;
}
bool Erase(const K& key) {
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 {
// 找到了
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
} else {
if (parent->_right == cur) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
} else if (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* p = cur;
Node* leftMax = cur->_left;
while (leftMax->_right) {
p = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (p->_left == leftMax) {
p->_left = leftMax->_left;
} else {
p->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
void InOrder() {
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root) {
if (root == NULL) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* Copy(Node* root) {
if (root == nullptr) return nullptr;
Node* copyroot = new Node(root->_key);
copyroot->_left = Copy(root->_left);
copyroot->_right = Copy(root->_right);
return copyroot;
}
void Destroy(Node*& root) {
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
private:
Node* _root;
};
引申：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;
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
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 类型的
/**
* 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) : left(left), right(right) {}
* };
*/
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 的路径存在了栈里面，之后根据他们的公共祖先高度应该一样来找
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
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() != q()) {
p();
q();
}
p();
}
};
力扣 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) : left(left), right(right) {}
* };
*/
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 要从最后开始取，然后根构建完之后先构建右树
/**
* 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) : left(left), right(right) {}
* };
*/
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 里就行了
// 中序遍历
/**
* 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) : left(left), right(right) {}
* };
*/
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 来记录上一个存了的结点是啥 改成在一个结点的右子树为空或者上一个访问结点是右子树的根时再访问这个结点 下面是与前面两道题相差比较大的地方
/**
* 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) : left(left), right(right) {}
* };
*/
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 别忘了他是顺序表！
