C语言使用一维数组实现二叉搜索树插入功能问题求助

问题核心错误点 #

首先明确回答你的疑问：你不需要把返回值类型从int*改为int，原代码无法运行的核心问题和返回值类型无关，是以下几个逻辑错误导致的：

• 递归参数类型不匹配：insert函数第一个参数要求传入int数组，你递归调用时传入的tree[parent]是int类型的数组元素，类型完全不匹配，编译阶段就会报错。
• 递归定位逻辑错误：每次进入insert函数时parent都被初始化为0，递归调用时根本无法定位到子节点的位置，相当于每次递归都回到根节点处理，逻辑完全错误。
• 赋值类型不匹配：你把insert返回的int*类型指针直接赋值给int类型的数组成员tree[parent]，类型冲突。

修复方案 #

数组实现二叉搜索树的递归插入逻辑，需要新增参数标记当前处理的节点下标，同时要加数组越界判断避免访问非法内存。首先你需要预先定义一个占位值（比如#define EMPTY -1，要保证该值不会作为正常插入的元素出现），初始化数组时所有元素都赋值为EMPTY。

递归实现版本 #

#define EMPTY -1
// tree: 存储二叉树的数组
// size: 数组的最大容量，防止越界
// cur_idx: 当前正在判断的节点下标
// element: 要插入的元素
void insert(int tree[], int size, int cur_idx, int element) {
    // 超出数组容量，插入失败
    if (cur_idx >= size) {
        // 可自行添加错误提示逻辑
        return;
    }
    // 当前位置为空，直接插入
    if (tree[cur_idx] == EMPTY) {
        tree[cur_idx] = element;
        return;
    }
    // 小于当前节点值，走左子树
    if (element < tree[cur_idx]) {
        insert(tree, size, cur_idx * 2 + 1, element);
    } 
    // 大于等于当前节点值，走右子树
    else {
        insert(tree, size, cur_idx * 2 + 2, element);
    }
}

调用方式示例（根节点下标固定为0）：

// 初始化数组
int tree[100];
for (int i = 0; i < 100; i++) {
    tree[i] = EMPTY;
}
// 插入元素10
insert(tree, 100, 0, 10);

迭代实现版本（不需要递归，更省栈空间） #

如果你不想新增cur_idx参数，也可以用迭代逻辑实现：

#define EMPTY -1
int* insert(int tree[], int size, int element) {
    int cur = 0;
    while (cur < size) {
        if (tree[cur] == EMPTY) {
            tree[cur] = element;
            return tree;
        }
        cur = element < tree[cur] ? cur * 2 + 1 : cur * 2 + 2;
    }
    // 数组容量不足，插入失败返回NULL
    return NULL;
}

注意事项 #

• 这种基于数组的实现仅适合接近完全二叉树的场景，如果树是极端斜树（比如所有元素都比根节点小，一直向左延伸），会浪费大量数组空间，甚至需要超大容量数组才能存储少量元素，性能远低于链式实现的二叉搜索树。
• 占位值EMPTY必须选择不会被当成正常插入元素的值，否则会出现逻辑混乱。

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