Representation of a binary tree in a file

Question

What are the different strategies for representing a binary tree in a file so that you can easily recreate the tree structure? I use C.

Answer 1

Save the traversal and prerecord of the tree traversal in a file. Any binary tree can be reconstructed in the order and in the traversal order [1].

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

Answer 2

Here's a naive way if you have something like:

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

Create another structure:

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

Then malloc represents an array of bst_serial , the size of which is equal to your tree:

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

So make the tree walk the same (untested):

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

Now you can write() output the array to disk. If you write functions to move the bst_serial tree bst_serial , you don't even need to deserialize it - you can just mmap() it. For extra points, do not even use the pointer tree in the first place - create and increase the bst_serial array when creating the binary tree. Then your code does not need to worry about whether it is related to the tree from the disk or to the tree you just created.

Answer 3

You will need at least 2 tree walks to be able to build the exact tree. Because there can be several unique trees from one given round.

For example, you can save traversal of the order and preorders of the binary tree in a text file and follow the link below to work it out there, recreating the tree.

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

Answer 4

Crawl in order and write the node value to a file delimited by newlines. If node is a leaf store, then after the leaf value, use a special character (for example, #).

When you read the file until you get the insert value "#" and go down to the left. If you get a "#", go up until you see any elements on the right and go down to the right. Do it recursively.