如何用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)。

标签： node c++ red