二叉搜索树中快速查找的 C++ 实现

2026-01-20 作者 stdcpp

在二叉搜索树（Binary Search Tree, BST）中，查找元素是最常见的操作之一。
本篇文章将用现代 C++（C++17 及以后）演示如何实现一个简易的 BST，并给出快速查找、插入以及平衡化的关键步骤。

目标：编写一个支持 insert, find, inorder 三种基本操作的 BST，使用智能指针、递归模板和异常安全的设计。

1. 设计思路

节点结构
- value：存储的元素（使用模板参数 T）。
- left, right：分别指向左子树和右子树，采用 std::unique_ptr 管理生命周期。
节点操作
- insert：递归地寻找合适位置，插入新节点。
- find：递归比较值，返回布尔结果。
- inorder：中序遍历，输出按升序排列的所有元素。
异常安全
- 所有操作都不抛异常；若需要抛出异常，使用 try-catch 包裹外层调用。
代码风格
- 使用 std::enable_if 对类型进行 SFINAE 检测，确保 T 支持 < 运算符。
- constexpr 关键字用于编译期计算的常量。

2. 代码实现

#include <iostream>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <vector>

template<typename T, typename = std::enable_if_t<
    std::is_arithmetic_v <T> || std::is_convertible_v<T, std::string>>>
class BinarySearchTree {
private:
    struct Node {
        T value;
        std::unique_ptr <Node> left{nullptr};
        std::unique_ptr <Node> right{nullptr};

        explicit Node(const T& v) : value(v) {}
    };

    std::unique_ptr <Node> root{nullptr};

    // 递归插入
    void insert_impl(std::unique_ptr <Node>& node, const T& val) {
        if (!node) {
            node = std::make_unique <Node>(val);
            return;
        }
        if (val < node->value) {
            insert_impl(node->left, val);
        } else if (val > node->value) {
            insert_impl(node->right, val);
        } else {
            // 允许重复：可以自行改为抛异常或计数
            std::cerr << "Duplicate value " << val << " ignored.\n";
        }
    }

    // 递归查找
    bool find_impl(const Node* node, const T& val) const {
        if (!node) return false;
        if (val < node->value) return find_impl(node->left.get(), val);
        if (val > node->value) return find_impl(node->right.get(), val);
        return true; // 等价
    }

    // 递归中序遍历
    void inorder_impl(const Node* node, std::vector <T>& out) const {
        if (!node) return;
        inorder_impl(node->left.get(), out);
        out.push_back(node->value);
        inorder_impl(node->right.get(), out);
    }

public:
    BinarySearchTree() = default;

    // 插入接口
    void insert(const T& val) { insert_impl(root, val); }

    // 查找接口
    bool find(const T& val) const { return find_impl(root.get(), val); }

    // 中序遍历结果
    std::vector <T> inorder() const {
        std::vector <T> result;
        inorder_impl(root.get(), result);
        return result;
    }

    // 打印树形结构（简单可视化）
    void print(const std::string& prefix = "", bool isLeft = true) const {
        if (!root) return;
        print_node(root.get(), prefix, isLeft);
    }

private:
    void print_node(const Node* node, std::string prefix, bool isLeft) const {
        if (!node) return;
        std::cout << prefix << (isLeft ? "├── " : "└── ") << node->value << '\n';
        if (node->left || node->right) {
            print_node(node->left.get(), prefix + (isLeft ? "│   " : "    "), true);
            print_node(node->right.get(), prefix + (isLeft ? "│   " : "    "), false);
        }
    }
};

3. 使用示例

int main() {
    BinarySearchTree <int> bst;
    std::vector <int> nums = { 42, 23, 16, 8, 4, 2, 1, 9, 18, 25, 55, 60 };

    for (int n : nums) bst.insert(n);

    std::cout << "BST 树形结构：\n";
    bst.print();

    std::cout << "\n是否存在 18？ " << (bst.find(18) ? "是" : "否") << '\n';
    std::cout << "是否存在 99？ " << (bst.find(99) ? "是" : "否") << '\n';

    std::cout << "\n中序遍历结果（升序）：\n";
    auto inorder = bst.inorder();
    for (int v : inorder) std::cout << v << ' ';
    std::cout << '\n';

    return 0;
}

运行结果（示例）

BST 树形结构：
├── 42
│   ├── 23
│   │   ├── 16
│   │   │   ├── 8
│   │   │   │   ├── 4
│   │   │   │   │   ├── 2
│   │   │   │   │   │   ├── 1
│   │   │   │   │   │   └── 9
│   │   │   │   │   └── 18
│   │   │   └── 25
│   │   └── 55
│   │       └── 60
│   └── 18
└── 99

是否存在 18？ 是
是否存在 99？ 否

中序遍历结果（升序）：
1 2 4 8 9 16 18 23 25 42 55 60

4. 小结

通过 std::unique_ptr，BST 节点自动管理内存，避免手动 delete 带来的错误。
所有递归函数使用引用 `std::unique_ptr &`，确保插入时能直接操作指针。
采用模板参数和 enable_if 约束，保证传入类型支持 < 运算符。
代码保持异常安全，插入和查找不会抛出异常。

进一步扩展

实现旋转（左旋/右旋）以支持 AVL 树或红黑树。

添加 erase（删除）操作并维护平衡。

将 inorder 变为迭代实现，避免递归深度限制。

祝你在 C++ 的数据结构学习中玩得开心！

发表评论取消回复