二叉排序树创建和插入

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下性质：

1. 左子树上所有节点的值均小于它的根节点的值；
2. 右子树上所有节点的值均大于它的根节点的值；
3. 左右子树也分别为二叉排序树。

基于这些性质，我们可以利用二叉排序树来快速地进行查找、插入、删除等操作。

二叉排序树的创建和插入操作如下：

创建二叉排序树：

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

// 创建二叉排序树
TreeNode* createBST(vector<int>& nums) {
    if (nums.empty()) return NULL;
    TreeNode* root = new TreeNode(nums[0]);
    for (int i = 1; i < nums.size(); i++) {
        insertBST(root, nums[i]);
    }
    return root;
}

插入节点到二叉排序树：

// 插入节点到二叉排序树
void insertBST(TreeNode* &root, int val) {
    if (!root) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insertBST(root->left, val);
    } else {
        insertBST(root->right, val);
    }
}

其中，createBST 函数接收一个整数数组 nums，表示二叉排序树的节点值。我们先以 nums 的第一个元素作为根节点，然后依次将剩余的元素插入到树中。

insertBST 函数则是插入一个节点到二叉排序树中。如果根节点为空，直接创建一个新的节点作为根节点。否则，根据节点值的大小，递归地插入到左子树或右子树中。

需要注意的是，为了能够在 insertBST 函数中修改树结构，我们使用了指向指针的引用，即 TreeNode* &root。