如何用C++实现二叉搜索树？C++数据结构与算法实战【手写代码】

二叉搜索树（BST）的核心性质是左子树所有节点值小于根、右子树所有节点值大于根，且左右子树本身也必须是BST；其节点结构含val、left、right指针，BST类仅持根指针；关键操作中，插入按大小递归插入空位，查找可迭代实现，删除分无子、单子、双子三种情况处理，推荐用右子树最小值替代双子节点；中序遍历结果严格升序，可用于验证正确性。

二叉搜索树的核心性质

二叉搜索树（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) {}
    TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
  };

整个BST类只需持有一个指向根节点的指针，不额外存size或parent等字段——保持轻量，按需扩展。

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

关键操作：插入、查找、删除

插入：从根开始比较，小则进左，大则进右，遇到空位置就新建节点。递归写法最直观：

• 若当前为空，直接返回新节点
• 若val小于当前节点值，递归处理左子树并更新left指针
• 若val大于当前节点值，递归处理右子树并更新right指针
• 相等时不插入（BST通常不允许重复值；如需支持，可加count字段）

查找：同样递归或迭代均可。迭代更省内存，逻辑直白：

标签： node 大数据 栈 c++