如何用c++实现一个二叉搜索树 节点的插入、查找和删除【数据结构】

BST的插入、查找、删除操作均基于左小右大性质：插入递归至空位新增叶子；查找递归或迭代单路径比对；删除分三类——无子直接删、单子顶替、双子用中序前驱/后继替换并递归删。

节点定义与基本结构

二叉搜索树（BST）每个节点满足：左子树所有节点值

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

插入操作：递归实现，保持BST性质

从根开始比较，小于当前节点往左走，大于往右走；遇到空位置就新建节点插入。

TreeNode* insertIntoBST(TreeNode* root, int val) {
  if (!root) return new TreeNode(val);
  if (val val) {
    root->left = insertIntoBST(root->left, val);
  } else {
    root->right = insertIntoBST(root->right, val);
  }
  return root;
}

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

• 插入不改变原有结构，只新增叶子节点
• 重复值可按需求处理（如忽略、或允许重复并插入右子树）
• 非递归版本可用 while 循环 + 指针追踪父节点实现

查找操作：简单递归或迭代

利用BST有序性，每次比较后只进一个子树，时间复杂度平均 O(log n)。

图酷AI

下载即用！可以免费使用的AI图像处理工具，致力于为用户提供最先进的AI图像处理技术，让图像编辑变得简单高效。

106

查看详情

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

• 返回匹配节点指针，未找到返回 nullptr
• 迭代写法更省内存：用 while 遍历，更新 root = root->left 或 root->right

删除操作：分三种情况处理

删除是 BST 最复杂的操作，需保证删除后仍为 BST。关键在“替代节点”的选择：

• 无子节点（叶子）：直接删，返回 nullptr
• 只有一个子节点：用该子节点顶替被删节点
• 有两个子节点：找左子树最大值（或右子树最小值）替换，再递归删除该替代值

TreeNode* deleteNode(TreeNode* root, int key) {
  if (!root) return nullptr;
  if (key val) {
    root->left = deleteNode(root->left, key);
  } else if (key > root->val) {
    root->right = deleteNode(root->right, key);
  } else {
    // 找到要删除的节点
    if (!root->left) return root->right;
    if (!root->right) return root->left;
    // 两个孩子：找左子树最大值（中序前驱）
    TreeNode* predecessor = root->left;
    while (predecessor->right) predecessor = predecessor->right;
    root->val = predecessor->val;
    root->left = deleteNode(root->left, predecessor->val);
  }
  return root;
}

注意：用右子树最小值（中序后继）同样可行，逻辑对称。选哪个取决于风格偏好，不影响正确性。

以上就是如何用c++++实现一个二叉搜索树 节点的插入、查找和删除【数据结构】的详细内容，更多请关注php中文网其它相关文章！