首先定义二叉搜索树节点结构，包含值、左子节点和右子节点指针；递归插入时比较值大小，找到空位创建新节点并返回根；迭代法用指针遍历至合适位置后插入，避免栈开销；两种方法均保持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结构。递归写法简洁易懂，迭代更节省栈空间。选择哪种取决于具体需求和偏好。基本上就这些，不复杂但容易忽略边界情况，比如空树处理。
