c++如何实现一个二叉搜索树_c++ BST数据结构实现方法

新闻中心 NEWS CENTER

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

c++如何实现一个二叉搜索树_c++ BST数据结构实现方法

2025-11-18

浏览次数：次

返回列表

二叉搜索树通过类封装实现插入、查找、删除操作，节点结构含值与左右指针，插入按大小规则递归构建，查找依二分逻辑遍历，删除时无子节点直接删、单子节点替换、双子节点找中序后继替代并递归删，示例验证功能正确性。

c++如何实现一个二叉搜索树_c++ bst数据结构实现方法

二叉搜索树（Binary Search Tree, BST）是一种重要的数据结构，它能高效地实现查找、插入和删除操作。在C++中，可以通过类和指针来构建一个完整的BST。下面是一个简洁、实用的C++ BST实现方法。

定义BST节点结构

每个节点包含一个值、指向左子树和右子树的指针。

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

};

Whimsical

Whimsical推出的AI思维导图工具

182 查看详情 Whimsical

BST类的基本设计

我们创建一个BST类，封装插入、查找、删除等核心操作。

class BST {
private:
    TreeNode* root;
<pre class='brush:php;toolbar:false;'>TreeNode* 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;
}

bool searchNode(TreeNode* node, int val) {
    if (!node) return false;
    if (node->val == val) return true;
    if (val < node->val) {
        return searchNode(node->left, val);
    } else {
        return searchNode(node->right, val);
    }
}

TreeNode* deleteNode(TreeNode* node, int val) {
    if (!node) return nullptr;

    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;
}

TreeNode* findMin(TreeNode* node) {
    while (node && node->left) {
        node = node->left;
    }
    return node;
}

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

void insert(int val) {
    root = insertNode(root, val);
}

bool search(int val) {
    return searchNode(root, val);
}

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

};

使用示例

下面是一个简单的测试用法：

#include <iostream>
using namespace std;
<p>int main() {
BST tree;
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);</p><pre class='brush:php;toolbar:false;'>cout << "Search 4: " << (tree.search(4) ? "Found" : "Not found") << endl;
cout << "Search 6: " << (tree.search(6) ? "Found" : "Not found") << endl;

tree.remove(3);
cout << "After deleting 3, search 3: " 
     << (tree.search(3) ? "Found" : "Not found") << endl;

return 0;

}

基本上就这些。这个实现覆盖了BST的核心功能：插入保持有序，查找利用二分逻辑，删除处理三种情况。注意递归写法清晰易懂，适合学习和实际使用。

以上就是c++++如何实现一个二叉搜索树_c++ BST数据结构实现方法的详细内容，更多请关注其它相关文章！

# 是一种 # 电商平台推广营销模式 # 优化关键词的排名方法是 # 长春营销推广哪家强 # 山东网站推广行业 # 崇州集团网站建设 # 网站制作网站建设单位 # 搜狗seo最新算法 # 铜山区seo多少钱 # 舟山产品seo推广 # 网站建设推荐超速云建站 # 相关文章 # 遍历 # node # 与其他 # 如何使用 # 如何实现 # 是一个 # 子树 # 数据结构 # 递归 # stream # ios # c++ # ai