17370845950

插入节点必须用指针引用（Node&）才能修改父节点的left/right字段；find()根据需求返回Node或bool；重复值需显式处理；递归易栈溢出，应考虑迭代实现并注意内存释放。

插入节点时为什么必须用指针的引用（Node*&）？

直接传 Node* 会导致修改形参无法影响实参，新节点只能挂在局部变量上，原树结构不变。用 Node*& 才能真正把新分配的节点地址写回父节点的 left 或 right 字段。

• 错误写法：void insert(Node* root, int val) → 插入后 root 仍是空或旧地址
• 正确写法：void insert(Node*& root, int val) → 可以让 root = new Node(val) 生效
• 递归调用时也需保持引用：比如 insert(root->left, val) 中 root->left 是左指针的引用，才能更新它

find() 返回 Node* 还是 bool？

取决于使用场景。如果只需要判断存在性，返回 bool 更轻量；如果后续要修改或访问该节点数据，必须返回 Node*（或 const Node*）。

• 查找失败时返回 nullptr，不是 NULL（C++11 起推荐用 nullptr）
• 避免在 find() 内部做 cout 或抛异常——职责单一，查就是查，输出/错误处理交给调用方
• 若需迭代器风格支持，可额外封装 begin()/end()，但基础 BST 通常不强制要求

插入重复值怎么处理？BST 标准定义不允许重复，但实际中常有不同策略

标准 BST 定义中，左子树 root，右子树 > root，等于时通常忽略、报错或插入到右子树（视需求而定）。C++ 实现必须显式决定行为，不能默认“随便放”。

• 忽略重复：if (val == root->val) return;
• 允许重复并插入右子树：else if (val >= root->val) insert(root->right, val);
• 若业务需要计数，可扩展节点为 struct Node { int val; int count; Node *left, *right; };，遇到相等只 ++count

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
void insert(Node*& root, int val) {
if (!root) {
root = new Node(val);
return;
}
if (val < root->val)
insert(root->left, val);
else if (val > root->val)
insert(root->right, val);
// 默认忽略重复；如需处理重复，此处加 else 分支
}
Node find(Node root, int val) {
if (!root || root->val == val)
return root;
return val < root->val ? find(root->left, val) : find(root->right, val);
}

递归实现简洁，但深度大时可能栈溢出；生产环境若树高不可控，应改用迭代版 insert 和 find。另外，所有动态分配的 Node* 必须配对 delete，否则内存泄漏——这点容易被初学者完全忽略。