c - 如何从 C 中的整数数组构建二叉搜索树？

Question

我尝试编写一个函数，用于从整数数组构建 BST。它有两个参数:指向数组的指针和数组的大小

• 通过连续插入创建 BST 并返回指向树的指针
• 如果大小为0，返回NULL

示例；

int a[3] = {2,1,3};
return build(a, 3);

我的工作到这里，但是递归部分有问题，我找不到我的错误，实际上我知道我不能正确使用for循环，但无法解决。

在我的代码中，首先我按升序改变了数组的格式，然后取中间的数字作为根，然后对于左右部分，我应该做同样的事情。

顺便说一句，我有一个插入函数实现，但我不确定，我们是否需要或在构建函数中使用它。

typedef struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;


TreeNode* build(int *array, int size) {
    TreeNode *root = malloc(sizeof(TreeNode));
    int a,i,j;
    int mid = size/2;
    if(size==0)
        return NULL;
    else {
        for(i=0;i<size;i++) {
            for(j=i+1;j<size;j++) {
                if(array[i] > array[j]) {
                    a = array[i];
                    array[i] = array[j];
                    array[j] = a;
                }
            }
        }
        root->val = array[mid];
        for(i=0;i<mid;i++)
            root->left = build(array, mid);
        for(i=(mid+1);i<size;i++)
            root->right = build(array, mid);
        return root;
    }
}

Answer 1

根据你的概念修改:

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

typedef struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* build(int *array, int size) {
    if(size == 0)
        return NULL;
    else {
        TreeNode *root = malloc(sizeof(TreeNode));//in the case of return NULL there is before if-block, cause of memory leak
        int i, j, mid;
        int swap = 1;

        j = size-1;
        while(swap){//To deter a repeat of the sort
            swap = 0;
            for(i = 0; i < j; ++i) {
                if(array[i] > array[i+1]) {
                    int temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                    swap = 1;
                }
            }
            --j;
        }
        root->val = array[mid = size / 2];
        root->left  = build(array, mid);
        root->right = build(array + mid + 1, size - mid -1);
        return root;
    }
}

void print(TreeNode *p){
    if(p){
        print(p->left);
        printf("%d ", p->val);
        print(p->right);
    }
}

int main(void){
    //test
    int a[] = {1,5,9,2,6,4,8,3,7,0};
    TreeNode *root = build(a, 10);
    print(root);
    //deallocate
    return 0;
}