c - 将完整二叉树存储到数组中的算法

Question

我现在正在学习数据结构，从书上我知道对于一个完整的二叉树，我们可以将它存储在一个数组中。但我无法用它提出算法，也无法将数组转换为完整的二叉树。谁能用C语言帮我解决这个问题？我觉得这样的问题可以用递归的方式解决，就像二叉树的遍历一样，但是我做不到，也不能用非递归的方法解决。

Answer 1

您需要一个调用函数指针的遍历按序函数。

编辑:正如@Peter Skarpetis所指出的，您可以避免使用全局变量或static在函数指针之后传递额外的参数:

struct container {
    void *data;
    int count;
};

void tree_walk_recurse(const t_node *node, void (*func)(void *, void *), void *data)
{
    if (node->left) tree_walk_recurse(node->left, func, data);
    func(node->data, data);
    if (node->right) tree_walk_recurse(node->right, func, data);
}

void tree_walk(const t_node *root, void (*func)(void *, void), void *data)
{
    if (root && func) tree_walk_recurse(root, func, data);
}

void insert(void *data, void *ptr)
{
    struct data *array = ptr;

    array->data[array->count++] = data;
}

/* Traverse in-order using insert */
struct container array;

array.data = malloc(sizeof(struct data) * n);
array.count = 0;
tree_walk(root, insert, &array);