BST类需用Node&引用实现就地修改：insert/search用递归辅助函数（传Node&），remove分三类处理（双子用右子树最左后继替换并递归删），析构深释放；search建议迭代避免栈溢出。
怎么写一个能跑通的 BST 类，而不是教科书伪代码
直接给可编译、可调试的完整实现，核心是 Node 结构体 + 三个关键操作封装在 BST 类里。别用裸指针递归到栈溢出，也别把 insert 写成返回新根——C++ 里就地修改更自然。重点是：所有操作都基于 root 指针管理，递归函数用私有辅助成员（比如 insertHelper），对外只暴露干净接口。
常见错误：用 void insert(int val) 但内部递归时忘了传引用或指针地址，导致插入失败；或者 delete 后没置空指针，后续访问 nullptr->left 崩溃。
- 每个节点用
struct Node { int val; Node* left; Node* right; };，不加虚析构（非多态） -
insert和search用递归辅助函数，参数为Node*&（二级指针语义），才能真正修改树结构 -
remove分三类：无子、单子、双子；双子情况用中序后继（右子树最左）替换，再递归删后继 - 析构函数必须深拷贝式释放，否则内存泄漏
insert 函数为什么必须传 Node*& 而不是 Node*
因为你要可能改变某个父节点的 left 或 right 指针本身，比如插入第一个节点时要让 root = new Node(val)。如果只传 Node*，那 root 在函数内被赋值，外部仍为 nullptr —— 这是 C++ 指针入门最常踩的坑。
示例片段：
立即学习“C++免费学习笔记（深入）”；
void insertHelper(Node*& node, int val) {
if (!node) {
node = new Node(val);
return;
}
if (val < node->val) insertHelper(node->left, val);
else if (val > node->val) insertHelper(node->right, val);
// 相等不插入（BST 通常去重）
}注意：这里 node 是引用，node = new Node(...) 真正改了上层调用者的指针变量。
remove 双子节点时，为什么选中序后继而不是前驱
选后继（右子树最小值）或前驱（左子树最大值）都合法，但统一用后继更常见，且实现稍简洁：不用额外找“左子树最右”。关键是——替换后必须递归删除那个后继节点，否则重复值残留。
容易漏的点：
- 找到后继后，不能直接
node->val = successor->val就完事，必须继续调用removeHelper(node->right, successor->val) - 后继节点一定至多一个子树（它是最左，所以无左子），所以它的删除退化为零/单子情况
- 如果用前驱，逻辑对称，但要注意：前驱在左子树，替换后得删左子树，别错删成右子树
查找和遍历要不要用迭代替代递归
查找（search）强烈建议迭代写法：简单、无栈溢出风险、CPU cache 更友好。删除和插入因需回溯改指针，递归更直观；但生产环境若树深度不可控（比如退化成链表），就得用迭代+栈模拟，或直接换平衡树。
迭代查找示例：
Node* search(int val) const {
Node* p = root;
while (p) {
if (val == p->val) return p;
p = (val < p->val) ? p->left : p->right;
}
return nullptr;
}注意：const 成员函数不能改树，所以返回 const Node* 更严谨，但初学可先忽略。
真正难的不是写完这三函数，而是测试边界：插相同值、删根节点、删叶子、删只有一个孩子的中间节点、连续删再插是否复用内存——这些不手动构造测试用例，代码等于没写。
