C++怎么实现一个二叉搜索树_C++数据结构与BST的插入、删除、查找

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++怎么实现一个二叉搜索树_C++数据结构与BST的插入、删除、查找

2025-11-23

浏览次数：次

返回列表

二叉搜索树通过类和指针实现，包含插入、删除、查找和中序遍历操作，其中插入和查找基于值的比较递归进行，删除需处理三种情况，中序遍历验证有序性，整体平均时间复杂度为O(log n)，但性能依赖树的平衡性。

c++怎么实现一个二叉搜索树_c++数据结构与bst的插入、删除、查找

二叉搜索树（Binary Search Tree，简称 BST）是一种重要的数据结构，它能高效地实现插入、删除和查找操作，平均时间复杂度为 O(log n)。在 C++ 中，我们可以用类和指针来构建一个完整的 BST。下面详细介绍其实现方式。

BST 的基本结构

每个节点包含一个值、指向左子树和右子树的指针。我们定义一个 TreeNode 结构体来表示节点：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
<pre class='brush:php;toolbar:false;'>TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

接着定义一个 BST 类，管理整棵树：

class BST {
private:
    TreeNode* root;
<pre class='brush:php;toolbar:false;'>// 辅助函数
TreeNode* insertNode(TreeNode* node, int val);
TreeNode* deleteNode(TreeNode* node, int val);
TreeNode* findMin(TreeNode* node);
TreeNode* searchNode(TreeNode* node, int val);

public: BST() : root(nullptr) {} void insert(int val); void remove(int val); bool search(int val); void inorder(); // 中序遍历用于验证 BST 性质 };

插入操作

插入时从根开始比较，小于当前节点值则进入左子树，大于则进入右子树，直到找到空位置。

递归实现：

PictoGraphic

AI驱动的矢量插图库和插图生成平台

133 查看详情 PictoGraphic

TreeNode* BST::insertNode(TreeNode* node, int val) {
    if (!node) {
        return new TreeNode(val);
    }
    if (val < node->val) {
        node->left = insertNode(node->left, val);
    } else if (val > node->val) {
        node->right = insertNode(node->right, val);
    }
    // 相等时不插入重复值
    return node;
}
<p>void BST::insert(int val) {
root = insertNode(root, val);
}</p>

查找操作

查找过程类似插入，根据大小关系决定向左或向右查找。

TreeNode* BST::searchNode(TreeNode* node, int val) {
    if (!node || node->val == val) {
        return node;
    }
    if (val < node->val) {
        return searchNode(node->left, val);
    }
    return searchNode(node->right, val);
}
<p>bool BST::search(int val) {
return searchNode(root, val) != nullptr;
}</p>

删除操作（关键难点）

删除节点有三种情况：

叶子节点：直接删除。
只有一个子节点：让父节点指向其子节点。
有两个子节点：用右子树中的最小值（中序后继）替换该节点，然后删除那个最小节点。

TreeNode* BST::findMin(TreeNode* node) {
    while (node && node->left) {
        node = node->left;
    }
    return node;
}
<p>TreeNode<em> BST::deleteNode(TreeNode</em> node, int val) {
if (!node) return nullptr;</p><pre class='brush:php;toolbar:false;'>if (val < node->val) {
    node->left = deleteNode(node->left, val);
} else if (val > node->val) {
    node->right = deleteNode(node->right, val);
} else {
    // 找到要删除的节点
    if (!node->left) {
        TreeNode* temp = node->right;
        delete node;
        return temp;
    } else if (!node->right) {
        TreeNode* temp = node->left;
        delete node;
        return temp;
    }

    // 有两个子节点
    TreeNode* successor = findMin(node->right);
    node->val = successor->val;
    node->right = deleteNode(node->right, successor->val);
}
return node;

}

void BST::remove(int val) { root = deleteNode(root, val); }

中序遍历验证结构

中序遍历 BST 应输出有序序列，可用于调试。

void inorderHelper(TreeNode* node) {
    if (node) {
        inorderHelper(node->left);
        std::cout << node->val << " ";
        inorderHelper(node->right);
    }
}
<p>void BST::inorder() {
inorderHelper(root);
std::cout << std::endl;
}</p>

基本上就这些。这个实现涵盖了 BST 的核心操作，适合学习和实际应用。注意内存管理，在更高级的版本中可使用智能指针避免泄漏。BST 的性能依赖于树的平衡性，极端情况下会退化为链表，后续可学习 *L 树或红黑树来解决这个问题。

以上就是C++怎么实现一个二叉搜索树_C++数据结构与BST的插入、删除、查找的详细内容，更多请关注其它相关文章！