1

考虑一下我已经有一个函数调用int* binToArrayInOrder(TreeRoot* tr)它创建一个排序的树值数组（因为它是有序的）。

无论如何从给定的数组中构造回树，而没有其他信息，例如前序数组中的相同树表示？

如何将数组写入 C 中的文本文件，请给我看代码。

4

2 回答 2

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);
}

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

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到文件中。我将把恢复树作为练习。再考虑一下这个问题，遍历是前序还是有序（或后序）并不重要。恢复步骤只需要能够让所有孩子找到父母，以便他们可以正确填充左右指针。

于 2012-07-07T19:22:20.890 回答
0

对于第一个问题：不，节点的有序列表不允许您重建同一棵树。

例如，树

  3
 2
1

产生中序遍历 1 2 3

那个树

 2
1 3

也产生 1 2 3。因此，您无法分辨使用哪棵树来产生给定的 1 2 3。

对于第二个问题：对不起，我还没有使用过 STL 文件 I/O。

于 2012-07-07T19:22:34.423 回答