平衡树构建算法n>7无输出问题求助：需适配n=11

问题根源分析 #

你的代码在n>7时无输出（实际是程序崩溃终止），核心问题有以下几点：

• int类型变量错误赋值NULL：createNewNode中node->size = NULL;，size是int类型，NULL是指针常量，赋值会引发未定义行为。
• NULL指针解引用：计算节点size时，未判断左/右子树是否为NULL就直接访问node->left->size或node->right->size，当子树为空时会触发崩溃。
• 节点key值错误：构建树时用数组索引mid作为节点key，而不是数组中的实际值arr[mid]。
• 不必要的内存分配：demo中先给root分配内存，又被BUILD_TREE的返回值覆盖，造成内存泄漏。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>     
#define NR_SPATII 7
#define MAX_SIZE 20

typedef struct Tree {
    int key;
    struct Tree* left;
    struct Tree* right;
    int size;
}Tree;

Tree* createNewNode(int givenkey)
{
    Tree* node = (Tree*)malloc(sizeof(Tree));
    node->key = givenkey;
    node->left = NULL;
    node->right = NULL;
    node->size = 1; // 初始化为1，后续根据子树调整
    return node;
}

Tree* BUILD_TREE(int arr[], int low, int high)
{
    if (low > high)
        return NULL;

    int mid = (low + high) / 2;
    Tree* node = createNewNode(arr[mid]); // 使用数组实际值作为key
    node->left = BUILD_TREE(arr, low, mid - 1);
    node->right = BUILD_TREE(arr, mid + 1, high);

    // 计算size时判断子树是否存在，避免NULL解引用
    int left_size = (node->left != NULL) ? node->left->size : 0;
    int right_size = (node->right != NULL) ? node->right->size : 0;
    node->size = left_size + right_size + 1;

    return node;
}

void PRETTY_PRINT(Tree* root, int nivel)
{
    if (root == NULL)
        return;
    nivel += NR_SPATII;
    PRETTY_PRINT(root->right, nivel);
    printf("\n");
    for (int i = NR_SPATII; i < nivel; i++)
        printf(" ");
    printf("%d,%d\n", root->key, root->size);
    PRETTY_PRINT(root->left, nivel);
}

void inOrder(Tree* root)
{
    if (root != NULL) {
        inOrder(root->left);
        printf("%d,%d  ", root->key, root->size);
        inOrder(root->right);
    }
}

void demo()
{
    int n = 11; // 修改为11测试
    int arr[MAX_SIZE];
    for (int i = 1; i <= n; i++)
        arr[i] = i;

    Tree* root = BUILD_TREE(arr, 1, n); // 去掉多余的malloc
    printf("AFISARE INORDINE:\n");
    inOrder(root);
    printf("\nAFISARE PRETTY PRINT:\n");
    PRETTY_PRINT(root, 0);
}

int main()
{
    demo();
    return 0;
}

关键修复说明 #

1. 修正size初始化：createNewNode中把node->size = NULL;改为node->size = 1;，单个节点的size默认是1。
2. 避免NULL指针解引用：计算节点size时，先判断左/右子树是否为NULL，为空则取0，再累加计算当前节点size。
3. 正确设置节点key：构建节点时传入arr[mid]，存储数组中的实际值而非索引。
4. 移除冗余内存分配：demo中直接将BUILD_TREE的返回值赋值给root，不再提前malloc。

测试n=11时，程序会正常输出中序遍历结果和树形打印。

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