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

c++怎么实现一个二叉搜索树_c++二叉搜索树实现步骤

冰火之心

发布： 2025-10-23 08:18:02

原创

308人浏览过

答案：实现二叉搜索树需定义节点结构和BST类，包含插入、查找、删除及中序遍历方法。1. 节点含值、左右子指针；2. BST类通过递归实现插入、查找、删除操作；3. 删除时处理三种情况：无子、一子、两子（用右子树最小值替换）；4. 中序遍历验证有序性；5. 示例演示插入、查找、删除流程，体现BST性质。

c++怎么实现一个二叉搜索树_c++二叉搜索树实现步骤

实现一个二叉搜索树（Binary Search Tree, BST）在 C++ 中是一个常见的数据结构练习。它支持高效的查找、插入和删除操作，前提是树保持相对平衡。下面介绍如何从零开始实现一个基础的二叉搜索树。

1. 定义二叉搜索树的节点结构

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

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搜索引擎

查看详情

2. 定义二叉搜索树类

创建一个 BST 类，管理根节点，并提供插入、查找、删除等方法。

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

class BST {
private:
    TreeNode* root;
<pre class='brush:php;toolbar:false;'>// 辅助函数：递归插入
TreeNode* insert(TreeNode* node, int val) {
    if (!node) {
        return new TreeNode(val);
    }
    if (val < node->val) {
        node->left = insert(node->left, val);
    } else if (val > node->val) {
        node->right = insert(node->right, val);
    }
    // 相等时不插入重复值
    return node;
}

// 辅助函数：递归查找
bool search(TreeNode* node, int val) {
    if (!node) return false;
    if (val == node->val) return true;
    if (val < node->val) {
        return search(node->left, val);
    } else {
        return search(node->right, val);
    }
}

// 辅助函数：查找最小值节点（用于删除）
TreeNode* findMin(TreeNode* node) {
    while (node && node->left) {
        node = node->left;
    }
    return node;
}

// 辅助函数：递归删除
TreeNode* remove(TreeNode* node, int val) {
    if (!node) return nullptr;

    if (val < node->val) {
        node->left = remove(node->left, val);
    } else if (val > node->val) {
        node->right = remove(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 = remove(node->right, minRight->val);
    }
    return node;
}

// 中序遍历（用于测试）
void inorder(TreeNode* node) {
    if (node) {
        inorder(node->left);
        std::cout << node->val << " ";
        inorder(node->right);
    }
}

登录后复制

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

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

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

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

void inorder() {
    inorder(root);
    std::cout << std::endl;
}

登录后复制

};

3. 使用示例

创建一个 BST 对象并进行基本操作。

#include <iostream>
using namespace std;
<p>int main() {
BST tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);</p><pre class='brush:php;toolbar:false;'>cout << "中序遍历: ";
tree.inorder();  // 输出：20 30 40 50 60 70 80

cout << "查找 40: " << (tree.search(40) ? "存在" : "不存在") << endl;

tree.remove(30);
cout << "删除 30 后中序遍历: ";
tree.inorder();  // 20 40 50 60 70 80

return 0;

登录后复制

}