c++中如何实现一个二叉搜索树_BST数据结构实现与操作-C++-PHP中文网

c++中如何实现一个二叉搜索树_BST数据结构实现与操作

尼克

发布： 2025-09-23 17:13:01

原创

225人浏览过

二叉搜索树通过类与指针实现，支持插入、查找、删除操作；插入与查找利用递归比较节点值，删除需处理三种情况，平均时间复杂度为O(log n)，最坏O(n)。

c++中如何实现一个二叉搜索树_bst数据结构实现与操作

二叉搜索树（Binary Search Tree，简称 BST）是一种重要的数据结构，它具有左子树节点值小于根节点、右子树节点值大于根节点的特性。C++ 中可以通过类和指针来实现 BST，支持插入、查找、删除等基本操作。

BST 的基本结构定义

每个节点包含一个值、指向左子树和右子树的指针。使用 C++ 类封装整个树结构。

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

登录后复制

};

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

定义一个管理树操作的类：

立即学习“C++免费学习笔记（深入）”；

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

登录后复制

public: BST() : root(nullptr) {}

void insert(int val);
bool search(int val);
void remove(int val);

登录后复制

};

插入操作

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

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>

登录后复制

查找操作

根据 BST 性质递归查找目标值。

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 实现的关键是利用递归保持结构有序，插入、查找、删除平均时间复杂度为 O(log n)，最坏情况下退化为 O(n)。可以在此基础上扩展中序遍历、求高度、验证是否为 BST 等功能。不复杂但容易忽略边界条件，比如重复值处理（当前实现忽略重复插入）和内存释放。

以上就是c++++中如何实现一个二叉搜索树_BST数据结构实现与操作的详细内容，更多请关注php中文网其它相关文章！