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

前言二叉搜索树binary search tree, BST是数据结构课上的第一个「会自己排序的树」。它的定义很简单对任意结点左子树所有键都小于该结点的键右子树所有键都大于该结点的键且左右子树本身也是二叉搜索树。有了这个性质查找、插入、删除的平均复杂度都是 O(log n)中序遍历还能直接得到有序序列。但初学者最常见的误解有三个第一以为 BST 的查找一定是 O(log n)——实际上树可能退化成链表最坏是 O(n)第二删除结点时只记得「删掉」不知道要分叶子、单孩子、双孩子三种情况第三用递归析构或者递归插入时不考虑栈深度。本文按「结点定义 → 插入与查找 → 删除的三种情况 → 遍历与析构」的顺序讲清实现并说明它和标准库std::set/std::map的关系。代码以 C17 为基准。为了专注结构本身这里不使用智能指针而是手工管理结点并在最后说明为什么工程代码更应该用std::unique_ptr或直接用标准容器。一、结点定义与整体约定一个最小可用的结点只需要键、左孩子指针、右孩子指针// 适用于 C17struct Node {int key;Node* left nullptr;Node* right nullptr;explicit Node(int k) : key(k) {}};这里用explicit是为了避免Node n 42;这种隐式转换。成员默认初始化 nullptr可以省掉构造函数里手写两行赋值。本文的实现约定不允许重复键。插入时若键已存在直接返回不新建结点。树根由BST类持有类负责释放所有结点。所有操作对空树都要能正确工作。// 适用于 C17class 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让编译器阻止浅拷贝。二、插入与查找插入是沿着比较路径往下走遇到空位就挂上新结点。递归写法最直观// 适用于 C17Node* 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)可能栈溢出。工程上可以改成迭代。查找同理// 适用于 C17bool 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 里最容易写错的部分。设要删除的结点为pp没有孩子直接删除返回nullptr。p只有一个孩子用那个孩子顶替p删除p。p有两个孩子找到右子树的最小结点中序后继把它的键复制到p然后递归删除那个后继结点。后继结点最多只有一个右孩子所以递归会落到情况 1 或 2。// 适用于 C17Node* 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的原因。四、遍历与析构中序遍历输出有序序列// 适用于 C17void 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自己再访问孩子就是释放后使用。// 适用于 C17void BST::destroy(Node* p) {if (p nullptr) return;destroy(p-left);destroy(p-right);delete p;}BST::~BST() {destroy(root_);}递归析构同样受树高影响。对退化树可以改用显式的栈做迭代后序释放// 适用于 C17BST::~BST() {std::vectorNode* 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;}}这段代码的正确性依赖于「先把孩子压栈再删除父结点」孩子指针在父结点被删除前已经读出来放进栈里之后不再访问父结点。栈里存放的是尚未释放的结点地址出栈时才释放所以不存在悬垂访问。五、完整示例把上面的片段组装起来做一个可以独立阅读的示例// 适用于 C17#include iostream#include vectorstruct 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 80t.erase(20); // 叶子t.erase(30); // 一个孩子t.erase(50); // 两个孩子t.inorder(); // 按标准语义应为 40 60 70 80std::cout std::boolalpha t.contains(60) \n;return 0;}手工推演一遍删除50的过程50的右子树是70右子树最小结点是60把60写到根再在右子树里删6060是叶子直接摘掉。最终中序是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) 是有前提的。