C++二叉搜索树插入节点详解

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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;
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;
}

int main() {
    TreeNode* root = nullptr;
    root = insertIntoBST(root, 5);
    root = insertIntoBST(root, 3);
    root = insertIntoBST(root, 7);
    root = insertIntoBST(root, 2);
    root = insertIntoBST(root, 4);
    return 0;
}