首先定义二叉搜索树节点结构，包含值、左子节点和右子节点指针；递归插入时比较值大小，找到空位创建新节点并返回根；迭代法用指针遍历至合适位置后插入，避免栈开销；两种方法均保持BST性质，递归简洁，迭代节省空间，需注意空树处理。
在C++中向二叉搜索树（Binary Search Tree, BST）插入节点，需要遵循BST的性质：对于任意节点，其左子树所有节点值小于该节点值，右子树所有节点值大于该节点值。插入操作的目标是保持这一性质。
定义二叉搜索树节点结构
首先定义一个基本的树节点结构，包含数据、左子节点和右子节点指针：
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
递归方式插入节点
递归方法思路清晰：从根节点开始，比较插入值与当前节点值的大小，决定进入左子树或右子树，直到找到空位置插入新节点。
函数返回类型为 TreeNode*，便于更新子树连接：
立即学习“C++免费学习笔记（深入）”；
TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) { return new TreeNode(val); // 空位置，创建并返回新节点 } if (val < root->val) { root->left = insertIntoBST(root->left, val); // 插入左子树 } else { root->right = insertIntoBST(root->right, val); // 插入右子树 } return root; // 返回当前根节点 }
迭代方式插入节点
迭代方法使用指针遍历树，避免递归调用开销，适合深度较大的树。
步骤如下：
- 若树为空，直接创建新节点作为根。
- 否则，从根开始比较，移动指针直到找到合适的空位置。
- 创建新节点并连接到父节点的左或右指针。
TreeNode* insertIntoBST(TreeNode* root, int val) { TreeNode* newNode = new TreeNode(val); if (!root) return newNode; <pre class='brush:php;toolbar:false;'>TreeNode* current = root; while (true) { if (val < current->val) { if (!current->left) { current->left = newNode; break; } current = current->left; } else { if (!current->right) { current->right = newNode; break; } current = current->right; } } return root;
}
两种方法都能正确插入节点并维持BST结构。递归写法简洁易懂，迭代更节省栈空间。选择哪种取决于具体需求和偏好。基本上就这些，不复杂但容易忽略边界情况，比如空树处理。