C语言有序一维数组转二叉搜索树：代码无法得到预期输出

你的代码问题出在递归创建左右子树的步骤——调用BST()后没有把返回的子树根节点赋值给当前节点的left和right指针，导致左右子树根本没挂到当前节点上，最终生成的树只有根节点，没有子节点。

修复后的完整代码 #

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

int arr[7] = {-10,-3,-1,0,3,7,9};

typedef struct tree{
   int data;
   struct tree *left;
   struct tree *right;
}bst;

struct tree *CreateNode(int data){
   bst *node = (bst*)malloc(sizeof(bst));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}

struct tree *BST(bst *root,int start,int end){
    if(start>end){
        return NULL;
    }
    int mid = start + (end-start)/2;
    root = CreateNode(arr[mid]);
    // 关键修改：将递归返回的子树节点赋值给当前节点的left和right
    root->left = BST(root->left,start,mid-1);
    root->right = BST(root->right,mid+1,end);
    return root;
 }

// 中序遍历验证结果
void inorderTraversal(bst *root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    bst *root = BST(NULL, 0, 6);
    printf("中序遍历结果：");
    inorderTraversal(root);
    return 0;
}

关键修改说明 #

原来的代码只是调用了BST(root->left, start, mid-1)，但没有把这个函数返回的子树根节点赋值给root->left，同理right也是如此。修复后，递归生成的左右子树会正确挂载到当前节点的对应指针上，这样才能构建出完整的平衡二叉搜索树。

运行修复后的代码，中序遍历会输出和原数组一致的有序序列：-10 -3 -1 0 3 7 9，符合二叉搜索树的特性。

内容的提问来源于stack exchange，提问作者Jitraj Swargiari