c++怎么实现一个二叉搜索树_c++二叉搜索树实现方法-C++-PHP中文网

c++怎么实现一个二叉搜索树_c++二叉搜索树实现方法

下次还敢

发布： 2025-10-10 17:02:01

原创

180人浏览过

二叉搜索树通过节点的左小右大性质实现高效查找，C++中可定义TreeNode结构并封装BST类，实现插入、查找和删除操作：插入根据大小关系递归定位，查找沿路径比较目标值，删除分三种情况处理，包括用中序后继替换；示例代码展示创建、插入、搜索和删除流程，验证了核心功能正确性。

c++怎么实现一个二叉搜索树_c++二叉搜索树实现方法

二叉搜索树（Binary Search Tree, 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) {}

登录后复制

};

BST 类设计与核心操作

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

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

1. 插入节点（Insert）

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

void insert(int val) {
    root = insertNode(root, val);
}
<p>TreeNode<em> insertNode(TreeNode</em> 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>

登录后复制

2. 查找节点（Search）

根据大小关系递归查找目标值。

纳米搜索

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

查看详情

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

登录后复制

3. 删除节点（Remove）

分三种情况处理：

叶子节点：直接删除
只有一个子节点：用子节点替代
有两个子节点：用右子树的最小值（中序后继）替换并删除该后继

void remove(int val) {
    root = removeNode(root, val);
}
<p>TreeNode<em> removeNode(TreeNode</em> node, int val) {
if (!node) return nullptr;</p><pre class='brush:php;toolbar:false;'>if (val < node->val) {
    node->left = removeNode(node->left, val);
} else if (val > node->val) {
    node->right = removeNode(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* minRight = findMin(node->right);
    node->val = minRight->val;
    node->right = removeNode(node->right, minRight->val);
}
return node;

登录后复制

}

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

完整使用示例

将上述部分整合进一个类中，并测试基本功能。

#include <iostream>
using namespace std;
<p>class BST {
private:
struct TreeNode {
int val;
TreeNode<em> left;
TreeNode</em> right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>TreeNode* root;

TreeNode* insertNode(TreeNode* node, int val) { ... }
bool searchNode(TreeNode* node, int val) { ... }
TreeNode* removeNode(TreeNode* node, int val) { ... }
TreeNode* findMin(TreeNode* 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 = removeNode(root, val); }

登录后复制

};

// 测试代码 int main() { BST tree; tree.insert(5); tree.insert(3); tree.insert(7); tree.insert(2); tree.insert(4);

cout << (tree.search(3) ? "Found 3\n" : "Not found 3\n");
tree.remove(3);
cout << (tree.search(3) ? "Found 3\n" : "Not found 3\n");

return 0;

登录后复制

}

基本上就这些。这个实现涵盖了二叉搜索树的核心操作，适合学习和基础应用。注意实际项目中要考虑内存释放、平衡性等问题，更复杂场景建议使用 std::set 或 AVL 树、红黑树等自平衡结构。

以上就是c++++怎么实现一个二叉搜索树_c++二叉搜索树实现方法的详细内容，更多请关注php中文网其它相关文章！

大家都在看：

如何配置C++的AI推理框架环境 TensorRT加速库安装使用 C++与AI部署：ONNX Runtime集成全解析 c++中的std::span（C++20）有什么用_轻量级数组视图的设计与应用 c++中C风格字符串和std::string的性能比较_C++两种字符串实现效率对比 c++20中的三路比较运算符（）是什么_太空船操作符的用法与排序实现