C++用递归生成一个二叉排序树

二叉排序树（Binary Search Tree）是一种特殊的二叉树，它的左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值。因此，对于任意一个节点，其左子树和右子树都是二叉排序树。

递归生成二叉排序树的思路如下：

1. 如果当前节点为空，则将新节点插入到该位置并返回。
2. 如果新节点的值小于当前节点的值，则递归调用函数，将新节点插入到左子树中。
3. 如果新节点的值大于当前节点的值，则递归调用函数，将新节点插入到右子树中。

下面是用 C 语言实现递归生成二叉排序树的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉排序树节点结构体
typedef struct bst_node {
    int data;
    struct bst_node *left;
    struct bst_node *right;
} BSTNode;

// 插入节点
BSTNode *insert(BSTNode *root, int data) {
    // 如果当前节点为空，则将新节点插入到该位置并返回
    if (root == NULL) {
        BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    // 如果新节点的值小于当前节点的值，则递归调用函数，将新节点插入到左子树中
    if (data < root->data) {
        root->left = insert(root->left, data);
    }
    // 如果新节点的值大于当前节点的值，则递归调用函数，将新节点插入到右子树中
    else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// 中序遍历二叉排序树
void inorder(BSTNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    BSTNode *root = NULL;
    int data;
    printf("请输入节点数据（以 -1 结束）：\n");
    while (1) {
        scanf("%d", &data);
        if (data == -1) {
            break;
        }
        root = insert(root, data);
    }
    printf("中序遍历结果为：");
    inorder(root);
    printf("\n");
    return 0;
}

运行结果示例：

请输入节点数据（以 -1 结束）：
5 3 7 2 4 6 8 -1
中序遍历结果为：2 3 4 5 6 7 8

以上代码可以根据用户输入的数据生成一个二叉排序树，并输出中序遍历的结果。可以看到，中序遍历结果是按照从小到大的顺序输出的，符合二叉排序树的定义。