编写二叉排序树构造算法

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。以下是二叉排序树构造算法的实现：

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

void insert(TreeNode*& root, int val) {
    if (!root) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insert(root->left, val);
    } else {
        insert(root->right, val);
    }
}

在这个算法中，我们首先判断根节点是否为空，如果为空，则直接将新节点插入到根节点位置。如果不为空，则比较新节点的值和根节点的值的大小关系，如果新节点的值小于根节点的值，则递归地将新节点插入到左子树中；否则，递归地将新节点插入到右子树中。