如何以一种不同的策略将二叉树表示为文件,以便能够轻松地重新创建树结构?我正在使用C语言。
如何以一种不同的策略将二叉树表示为文件,以便能够轻松地重新创建树结构?我正在使用C语言。
将树的中序遍历和前序遍历存储在文件中。任何二叉树都可以通过中序遍历和前序遍历进行重建[1]。
[1] http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
为了能够构建出精确的树形结构,您至少需要对树进行两次遍历。因为从一个给定的遍历序列中可能存在多个唯一的树形结构。
例如 - 您可以将二叉树的中序遍历和前序遍历存储到文本文件中,并按照下面的链接进行操作,以便在重新创建树形结构时进行还原。
http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html
这里有一个天真的方法,假设你有类似于:
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;
}
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
数组。然后,您的代码无需关心它是处理来自磁盘的树还是刚刚创建的树。执行中序遍历,并将节点值写入以换行符为分隔符的文件中。如果一个节点是叶子节点,在叶子值之后存储一个特殊字符(例如“#”)。
当你读取文件时,直到遇到“#”之前插入值,并向左下降。如果遇到“#”,则向上升至没有右元素可用的位置,并向右下降。递归地执行这个操作。