c++怎么实现一个二叉搜索树_c++二叉搜索树BST的定义与实现

新闻中心 NEWS CENTER

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

c++怎么实现一个二叉搜索树_c++二叉搜索树BST的定义与实现

2025-11-16

浏览次数：次

返回列表

二叉搜索树通过递归实现插入、查找、删除和中序遍历操作，核心是保持左小右大的有序性。1. 插入时根据大小关系选择左右子树递归插入；2. 查找利用有序性快速定位目标值；3. 删除分三种情况处理，尤其需用中序后继替换双孩子节点；4. 中序遍历验证升序输出。完整示例展示构建、删除与遍历过程，重点在于正确维护树结构与边界处理。

c++怎么实现一个二叉搜索树_c++二叉搜索树bst的定义与实现

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

};

基本操作实现

常见的操作包括插入、查找、删除和遍历。下面逐一实现。

1. 插入节点

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

TreeNode* insert(TreeNode* root, int val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    // 相同值不插入（保持唯一性）
    return root;
}

2. 查找节点

利用 BST 的有序性进行递归或迭代查找。

Zyro AI Background Remover

Zyro推出的AI图片背景移除工具

145 查看详情 Zyro AI Background Remover

TreeNode* search(TreeNode* root, int target) {
    if (!root || root->val == target) {
        return root;
    }
    if (target < root->val) {
        return search(root->left, target);
    } else {
        return search(root->right, target);
    }
}

3. 删除节点

删除操作较复杂，分三种情况处理：

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

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

    // 有两个孩子
    TreeNode* successor = findMin(root->right);
    root->val = successor->val;
    root->right = remove(root->right, successor->val);
}
return root;

}

4. 中序遍历（验证BST）

中序遍历输出应为升序，可用于验证树的结构是否正确。

void inorder(TreeNode* root) {
    if (root) {
        inorder(root->left);
        std::cout << root->val << " ";
        inorder(root->right);
    }
}

完整使用示例

把上面的函数组合起来，可以这样使用：

#include <iostream>
int main() {
    TreeNode* root = nullptr;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 2);
    root = insert(root, 4);
<pre class='brush:php;toolbar:false;'>std::cout << "Inorder: ";
inorder(root); // 输出: 2 3 4 5 7
std::cout << std::endl;

root = remove(root, 3);
std::cout << "After removing 3: ";
inorder(root); // 输出: 2 4 5 7
std::cout << std::endl;

return 0;

}

基本上就这些。实现一个基础的二叉搜索树时，重点是维护其有序性，特别是在删除操作中选择合适的替代节点。虽然这里用的是递归实现，也可以改写为迭代版本以节省栈空间。不复杂但容易忽略边界条件，比如重复值处理和空指针检查。

以上就是c++++怎么实现一个二叉搜索树_c++二叉搜索树BST的定义与实现的详细内容，更多请关注其它相关文章！

# 如何处理 # 茂名个人网站推广哪家好 # 广安做推广的网站便宜的 # 淮安短视频seo # 静海seo公司 # 茂名前端seo优化 # 做seo需要懂什么 # 歌舞团营销推广方式 # 象州网站定制建设 # 关键词营销网站排名系统 # 丹阳互联网推广营销 # 迭代 # 的是 # 正确处理 # c++ # 三种 # 升序 # 数据结构 # 遍历 # 递归 # 子树 # stream # ios # ai # 栈 # node # 二叉搜索树