c - 如何在 C+ 中使用文件将打包在数组中的有序(LDR)二叉树转换回二叉树

Question

假设我已经有一个名为 int* binToArrayInOrder(TreeRoot* tr) 的函数，它创建一个排序的树值数组(因为它是有序的)。

有没有办法从给定的有序数组中构造树，没有其他信息，例如在预序数组中的相同树表示？

如何用 C 将数组写入文本文件，请显示代码。

Answer 1

[1] 您可以将数组元素重新插入到二叉树中。不过，根据平衡算法的不同，树可能看起来与将它们提取到数组中时完全不同。

[2]这个怎么样？

void print_array (int *array, size_t sz, FILE *f) {
    if (!sz) return;
    fprintf(f, "%d\n", *array);
    print_array(array+1, sz-1, f);
}

根据您的评论，您的实际问题是如何将二叉树保存到磁盘，然后将其恢复。这是一个数据结构序列化问题。对于这个问题，按顺序遍历可能不是您想要的。相反，序列化应该反射(reflect)数据结构的布局方式。因此，您需要一个描述二进制节点的记录:

struct binary_node_file_data {
    char data_[MAX_BINARY_NODE_DATA_SIZE];
    int parent_;
};

现在，您可以执行二叉树的预序遍历来填充节点。

struct binary_node_fila_data *bfd = malloc(sizeof(*bfd)*nodeCount);
int count = 0;
populate_binary_node_file(tree, bfd, &count, -1);

void populate_binary_node_file(binary_tree_t *tree,
                               struct binary_node_file_data *bfd,
                               int *count,
                               int parent) {
    if (tree) {
        int me = *count;
        *count += 1;
        export_binary_node_data(tree, &bfd[me], parent);
        populate_binary_node_file(tree->left_subtree, bfd, count, me);
        populate_binary_node_file(tree->right_subtree, bfd, count, me);
    }
}

在这里，我希望 -1 被视为一个 NULL 指针。然后，将 bfd 转储到文件中。我将把恢复树作为练习。稍微反射(reflection)一下这个问题，遍历是前序还是中序(或后序)其实并不重要。恢复步骤只需要能够让所有的 child 找到 parent ，以便他们可以正确地填充左指针和右指针。