在文件中表示二叉树

Question

如何以一种不同的策略将二叉树表示为文件，以便能够轻松地重新创建树结构？我正在使用C语言。

- PaulDaviesC

---

我将使用C程序创建一棵二叉树，并需要将树结构存储到文件中，以便稍后通过从文件中读取来重新创建树。 - PaulDaviesC

@PaulDC 您可以将树存储为（值，左子树，右子树）格式。例如，（1，（2，（4，NULL，NULL），（5，NULL，NULL）），（3，（6，NULL，NULL），（7，NULL，NULL））用于存储具有1作为根，2和3作为第二层节点以及4,5,6和7作为叶子的简单树。编写树的时间复杂度为O(n)，读取树的时间复杂度也为O(n)。如果您需要完整的算法，请告诉我。 - ElKamina

@ElKamina 这个表示法的一个变种是从三元组中删除尾部的 NULL 值。那么您的示例树可以写作 (1, (2, (4), (5)), (3, (6), (7)))。（只能删除尾部的 NULL；如果一个节点有一个空的左子树但是有一个非空的右子树，那么它必须表示为 (value, NULL, rightsubtree)）。 - Ted Hopp

@TedHopp 是的，没错。另一个选项是进行遍历并跟踪回溯。对于同一棵树，您可以将其存储为1、2、4、NULL、NULL、5、NULL、NULL、3、6、NULL、NULL、7、NULL、NULL。 - ElKamina

请访问http://codegolf.stackexchange.com/q/339/152以获取高效表示的详细信息。 - AShelly

Answer 1

将树的中序遍历和前序遍历存储在文件中。任何二叉树都可以通过中序遍历和前序遍历进行重建[1]。

[1] http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

- user1054825

Answer 2

为了能够构建出精确的树形结构，您至少需要对树进行两次遍历。因为从一个给定的遍历序列中可能存在多个唯一的树形结构。

例如 - 您可以将二叉树的中序遍历和前序遍历存储到文本文件中，并按照下面的链接进行操作，以便在重新创建树形结构时进行还原。

http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

- C0deBr8kr

Answer 3

这里有一个天真的方法，假设你有类似于：

struct bst {
   int val;
   struct bst *left; // NULL when no node
   struct bst *right;
}

创建另一个类似的结构体：

struct bst_serial {
   int val;
   int left; // NULL when no node
   int right;
}

然后，使用malloc函数分配一个与您的二叉搜索树一样大的bst_serial数组：

struct bst_serial *serial_bst = malloc(sizeof(struct bst_serial) * tree_size);

现在，像这样遍历树（未经测试）：

int current_pos = 0;

int convert_node(bst *root) {
    int this_pos = current_pos;
    current_pos++;        

    serial_bst[this_pos].val = root->val;
    if(root->left != NULL) {
       serial_bst[this_pos].left = convert_node(root->left);
    } else {
       serial_bst[this_pos].left = -1;
    } 

    if(root->right != NULL) {    
       serial_bst[this_pos].right = convert_node(root->right);
    } else {
       serial_bst[this_pos].right = -1;
    } 
    return this_pos;
}

现在您可以将数组使用write()写入磁盘。如果编写函数来遍历bst_serial类型的树，则甚至不需要对其进行反序列化 - 您只需mmap()即可。为了获得额外的分数，甚至不要在第一次使用指针树 - 在创建二叉树时创建并增长bst_serial数组。然后，您的代码无需关心它是处理来自磁盘的树还是刚刚创建的树。

- Timothy Jones

Answer 4

执行中序遍历，并将节点值写入以换行符为分隔符的文件中。如果一个节点是叶子节点，在叶子值之后存储一个特殊字符（例如“#”）。

当你读取文件时，直到遇到“#”之前插入值，并向左下降。如果遇到“#”，则向上升至没有右元素可用的位置，并向右下降。递归地执行这个操作。

- WebMonster

---

抱歉，它无法保留您的原始树。它只会保留具有相同数字的正确二叉搜索树。 - WebMonster

你所说的“向左下降”，是指将一个子节点附加到左侧，对吗？那么“向上升”又是什么意思呢？ - PaulDaviesC

如果一个节点没有右子节点，这个方法将不起作用。你需要为这种情况添加额外的 #。 - Irit Katriel