📰 新闻详情

了解行业动态，掌握建站趋势

首页>资讯中心>新闻详情

C++数据结构之二叉搜索树的实现详解

发布时间：2026/11/5 2:12:48
C++数据结构之二叉搜索树的实现详解

前言


二叉搜索树（binary search tree, BST）是数据结构课上的第一个「会自己排序的树」。它的定义很简单：对任意结点，左子树所有键都小于该结点的键，右子树所有键都大于该结点的键，且左右子树本身也是二叉搜索树。有了这个性质，查找、插入、删除的平均复杂度都是 O(log n)，中序遍历还能直接得到有序序列。


但初学者最常见的误解有三个：第一，以为 BST 的查找一定是 O(log n)——实际上树可能退化成链表，最坏是 O(n)；第二，删除结点时只记得「删掉」，不知道要分叶子、单孩子、双孩子三种情况；第三，用递归析构或者递归插入时不考虑栈深度。本文按「结点定义 → 插入与查找 → 删除的三种情况 → 遍历与析构」的顺序讲清实现，并说明它和标准库std::set/std::map的关系。


代码以 C++17 为基准。为了专注结构本身，这里不使用智能指针，而是手工管理结点，并在最后说明为什么工程代码更应该用std::unique_ptr或直接用标准容器。


一、结点定义与整体约定


一个最小可用的结点只需要键、左孩子指针、右孩子指针：


// 适用于 C++17
struct Node {
int key;
Node* left = nullptr;
Node* right = nullptr;
explicit Node(int k) : key(k) {}
};

这里用explicit是为了避免Node n = 42;这种隐式转换。成员默认初始化= nullptr可以省掉构造函数里手写两行赋值。


本文的实现约定：



  • 不允许重复键。插入时若键已存在，直接返回，不新建结点。

  • 树根由BST类持有，类负责释放所有结点。

  • 所有操作对空树都要能正确工作。


// 适用于 C++17
class BST {
public:
BST() = default;
~BST();
BST(const BST&) = delete;
BST& operator=(const BST&) = delete;

void insert(int key);
bool contains(int key) const;
void erase(int key);
void inorder() const;

private:
Node* root_ = nullptr;

static Node* insert(Node* p, int key);
static bool contains(const Node* p, int key);
static Node* erase(Node* p, int key);
static Node* minNode(Node* p);
static void destroy(Node* p);
static void inorder(const Node* p);
};

拷贝构造和拷贝赋值被删除，是因为默认的浅拷贝会导致两棵树共享结点、析构时重复释放（double free）。如果确实需要可拷贝的树，应当写深拷贝，或者改用std::unique_ptr让编译器阻止浅拷贝。


二、插入与查找


插入是沿着比较路径往下走，遇到空位就挂上新结点。递归写法最直观：


// 适用于 C++17
Node* BST::insert(Node* p, int key) {
if (p == nullptr) return new Node(key);
if (key < p->key) {
p->left = insert(p->left, key);
} else if (p->key < key) {
p->right = insert(p->right, key);
}
// key == p->key 时不做任何事
return p;
}

void BST::insert(int key) {
root_ = insert(root_, key);
}

几个细节值得说明：



  • 比较写成key < p->key和p->key < key两次，而不是key < p->key/key > p->key。对内置的int两者等价，但对只提供<的自定义类型，前一种写法更通用。

  • 返回Node*是为了让「空位挂新结点」这件事能通过返回值传回给父结点。第一次调用时若root_为空，返回的新结点会被赋给root_。

  • 这个递归不是尾递归，深度等于树高。树退化时深度是 O(n)，可能栈溢出。工程上可以改成迭代。


查找同理：


// 适用于 C++17
bool BST::contains(const Node* p, int key) {
while (p != nullptr) {
if (key < p->key) p = p->left;
else if (p->key < key) p = p->right;
else return true;
}
return false;
}

这里用迭代而不是递归，少了函数调用开销，也没有栈深度问题。查找不需要修改结构，所以参数是const Node*。


三、删除：三种情况


删除是 BST 里最容易写错的部分。设要删除的结点为p：



  2. p没有孩子：直接删除，返回nullptr。

  4. p只有一个孩子：用那个孩子顶替p，删除p。

  6. p有两个孩子：找到右子树的最小结点（中序后继），把它的键复制到p，然后递归删除那个后继结点。后继结点最多只有一个右孩子，所以递归会落到情况 1 或 2。


// 适用于 C++17
Node* BST::minNode(Node* p) {
while (p != nullptr && p->left != nullptr) p = p->left;
return p;
}

Node* BST::erase(Node* p, int key) {
if (p == nullptr) return nullptr;

if (key < p->key) {
p->left = erase(p->left, key);
} else if (p->key < key) {
p->right = erase(p->right, key);
} else {
if (p->left == nullptr) {
Node* r = p->right;
delete p;
return r;
}
if (p->right == nullptr) {
Node* l = p->left;
delete p;
return l;
}
Node* s = minNode(p->right); // 中序后继
p->key = s->key;
p->right = erase(p->right, s->key);
}
return p;
}

void BST::erase(int key) {
root_ = erase(root_, key);
}

这里有三个容易忽略的点：



  • 删除只有一个孩子的结点时，必须先保存孩子指针，再delete p，最后返回保存的指针。如果先delete p再读p->right，就是释放后使用（use-after-free），属于 UB。

  • 双孩子的情况选择「右子树最小」作为后继，也可以选「左子树最大」作为前驱，两者都能保持 BST 性质。选后继时，后继一定没有左孩子，所以替换后递归删除它只会走情况 1 或 2。

  • 复制的是键而不是整个结点，这样不需要处理指针的转移。如果结点里还有卫星数据，复制键就意味着卫星数据也要一起复制或交换，需要按业务决定。


必须强调：删除的复杂度是 O(h)，h是树高。对随机插入的树，h期望是 O(log n)；但对有序序列插入，树会退化成一条链，h = n，所有操作都变成 O(n)。这正是标准库不用普通 BST、而用红黑树（red-black tree）的原因。


四、遍历与析构


中序遍历输出有序序列：


// 适用于 C++17
void BST::inorder(const Node* p) {
if (p == nullptr) return;
inorder(p->left);
std::cout << p->key << ' ';
inorder(p->right);
}

void BST::inorder() const {
inorder(root_);
std::cout << '\n';
}

析构必须后序遍历：先释放左右子树，再释放自己。如果先delete自己再访问孩子，就是释放后使用。


// 适用于 C++17
void BST::destroy(Node* p) {
if (p == nullptr) return;
destroy(p->left);
destroy(p->right);
delete p;
}

BST::~BST() {
destroy(root_);
}

递归析构同样受树高影响。对退化树，可以改用显式的栈做迭代后序释放：


// 适用于 C++17
BST::~BST() {
std::vector<Node*> stk;
if (root_ != nullptr) stk.push_back(root_);
while (!stk.empty()) {
Node* p = stk.back();
stk.pop_back();
if (p->left != nullptr) stk.push_back(p->left);
if (p->right != nullptr) stk.push_back(p->right);
delete p;
}
}

这段代码的正确性依赖于「先把孩子压栈，再删除父结点」：孩子指针在父结点被删除前已经读出来放进栈里，之后不再访问父结点。栈里存放的是尚未释放的结点地址，出栈时才释放，所以不存在悬垂访问。


五、完整示例


把上面的片段组装起来，做一个可以独立阅读的示例：


// 适用于 C++17
#include <iostream>
#include <vector>

struct Node {
int key;
Node* left = nullptr;
Node* right = nullptr;
explicit Node(int k) : key(k) {}
};

class BST {
public:
BST() = default;
~BST() { destroy(root_); }
BST(const BST&) = delete;
BST& operator=(const BST&) = delete;

void insert(int key) { root_ = insert(root_, key); }
bool contains(int key) const { return contains(root_, key); }
void erase(int key) { root_ = erase(root_, key); }
void inorder() const { inorder(root_); std::cout << '\n'; }

private:
Node* root_ = nullptr;

static Node* insert(Node* p, int key) {
if (p == nullptr) return new Node(key);
if (key < p->key) p->left = insert(p->left, key);
else if (p->key < key) p->right = insert(p->right, key);
return p;
}

static bool contains(const Node* p, int key) {
while (p != nullptr) {
if (key < p->key) p = p->left;
else if (p->key < key) p = p->right;
else return true;
}
return false;
}

static Node* minNode(Node* p) {
while (p != nullptr && p->left != nullptr) p = p->left;
return p;
}

static Node* erase(Node* p, int key) {
if (p == nullptr) return nullptr;
if (key < p->key) {
p->left = erase(p->left, key);
} else if (p->key < key) {
p->right = erase(p->right, key);
} else {
if (p->left == nullptr) {
Node* r = p->right;
delete p;
return r;
}
if (p->right == nullptr) {
Node* l = p->left;
delete p;
return l;
}
Node* s = minNode(p->right);
p->key = s->key;
p->right = erase(p->right, s->key);
}
return p;
}

static void destroy(Node* p) {
if (p == nullptr) return;
destroy(p->left);
destroy(p->right);
delete p;
}

static void inorder(const Node* p) {
if (p == nullptr) return;
inorder(p->left);
std::cout << p->key << ' ';
inorder(p->right);
}
};

int main() {
BST t;
for (int k : {50, 30, 70, 20, 40, 60, 80}) t.insert(k);
t.inorder(); // 按标准语义应为 20 30 40 50 60 70 80

t.erase(20); // 叶子
t.erase(30); // 一个孩子
t.erase(50); // 两个孩子
t.inorder(); // 按标准语义应为 40 60 70 80

std::cout << std::boolalpha << t.contains(60) << '\n';
return 0;
}

手工推演一遍删除50的过程：50的右子树是70，右子树最小结点是60；把60写到根，再在右子树里删60，60是叶子，直接摘掉。最终中序是40 60 70 80。


常见坑点


1. 析构时先删父结点再访问孩子


❌delete p; destroy(p->left);——delete p之后p->left是释放后读取。


✅ 先递归释放孩子，再delete p；或者像本文的迭代版本那样先把孩子指针存进栈。


2. 删除单孩子结点时先 delete 再取孩子


❌delete p; return p->right;


✅Node* r = p->right; delete p; return r;


3. 用默认拷贝构造复制树


❌ 直接BST b = a;，编译器生成的拷贝构造只复制根指针，两棵树析构时重复释放。


✅ 删除拷贝操作，或实现深拷贝（递归克隆每个结点）。


4. 认为 BST 查找一定是 O(log n)


❌ 在文档里写「查找复杂度 O(log n)」而不加前提。


✅ 写成「平均 O(log n)，最坏 O(n)，取决于树高」；需要严格对数界就用std::set/std::map（红黑树）或平衡树。


5. 允许重复键却不定义语义


❌ 插入key == p->key时随手往右走，结果重复键散落在多处，删除时只删一个。


✅ 明确约定：拒绝重复、计数、或允许重复并说明删除哪一个。标准库用std::multiset表达允许重复。


6. 递归深度不设防


❌ 对可能有序的输入直接用递归插入/析构。


✅ 改成迭代，或先打乱输入、使用平衡树；至少要在文档里提示栈深度风险。


7. 结点里的指针没有默认初始化


❌struct Node { int key; Node* left; Node* right; };然后new Node{1}，两个指针是 indeterminate 值。


✅ 成员写= nullptr，或构造函数里显式置空。


总结




操作平均复杂度最坏复杂度关键点



查找O(log n)O(n)沿比较路径下降

插入O(log n)O(n)空位挂新结点，拒绝或处理重复键

删除O(log n)O(n)叶子/单孩子/双孩子三种情况

中序遍历O(n)O(n)输出有序序列

析构O(n)O(n)必须后序释放



二叉搜索树的代码不长，但正确性全在边界上：空指针、单孩子、双孩子、重复键、析构顺序。把这些情况逐一写清楚，树的行为才是可预期的。工程代码里，如果只需要有序集合，优先用std::set/std::map；如果是要学结构或做面试题，再手写 BST，并且记住它的 O(log n) 是有前提的。




相关新闻

最新新闻

日新闻

周新闻

月新闻