Serialize And Deserialize A Given N-Ary Tree
Serialize and Deserialize Binary Tree. Design an algorithm to serialize and deserialize a binary tree. I have given the sequence from 1 to the number of nodes. Given a binary tree, how can you serialize and deserialize it? Serialization: Storing a given tree in a file or in an array. Deserialization: Reverse of seri.
Embed
| // |
| // 40 |
| // 20 21 22 |
| //10 11 12 13 14 |
| // 2 |
| //serialised value is : 40 20 10 ) 11 2 ) ) ) 21 ) 22 12 ) 13 ) 14 ) ) ) |
| // A C++ program to demonstrate serialization and deserialiation of |
| // n-ary Tree |
| #include<iostream> |
| #include<vector> |
| usingnamespacestd; |
| //char MARKER=')'; |
| #defineMARKER -1 |
| /* A binary Node has key, vector of Node * for children */ |
| structNode |
| { |
| int key; |
| vector< structNode * > child; |
| }; |
| /* Helper function that allocates a new Node with the |
| given key and NULL children pointer. */ |
| Node* newNode(int key) |
| { |
| Node* temp = new Node; |
| temp->key = key; |
| return (temp); |
| } |
| // This function stores a tree in a file pointed by fp |
| voidserialize(Node *root, FILE *fp) |
| { |
| // Else, store current node and recur for its children |
| fprintf(fp, '%d ', root->key); |
| unsigned i=0; |
| while(i<root->child.size()) |
| { |
| serialize(root->child[i], fp); |
| i++; |
| } |
| fprintf(fp, '%d ', MARKER ); |
| } |
| // This function constructs a tree from a file pointed by 'fp' |
| // 40 20 10 ) 11 2 ) ) ) 21 ) 22 12 ) 13 ) 14 ) ) ) |
| voiddeSerialize(Node *&root, FILE *fp) |
| { |
| } |
| /* |
| // A simple inorder traversal used for testing the constructed tree |
| void inorder(Node *root) |
| { |
| if (root) |
| { |
| inorder(root->left); |
| printf('%d ', root->key); |
| inorder(root->right); |
| } |
| } |
| */ |
| voidprintTree(structNode * root) |
| { cout<< root->key<<''; |
| unsigned i=0;//becoz vectoe size returns unsigned int |
| while(i < (root->child).size()) |
| { |
| printTree(root->child[i]); |
| i++; |
| } |
| cout<<endl; |
| } |
| /* Driver program to test above functions*/ |
| intmain() |
| { |
| // Let us construct a tree shown in the above figure |
| structNode *root = newNode(40); |
| root->child.push_back( newNode(20) ); |
| root->child.push_back( newNode(21) ); |
| root->child.push_back( newNode(22) ); |
| root->child[0]->child.push_back(newNode(10)); |
| root->child[0]->child.push_back(newNode(11)); |
| root->child[0]->child[1]->child.push_back(newNode(2)); |
| root->child[2]->child.push_back(newNode(12)); |
| root->child[2]->child.push_back(newNode(13)); |
| root->child[2]->child.push_back(newNode(14)); |
| //level order traversal of tree |
| printTree(root); |
| // Let us open a file and serialize the tree into the file |
| FILE *fp = fopen('tree.txt', 'w'); |
| if (fp NULL) |
| { |
| puts('Could not open file'); |
| return0; |
| } |
| serialize(root, fp); |
| fclose(fp); |
| // Let us deserialize the storeed tree into root1 |
| Node *root1 = NULL; |
| fp = fopen('tree.txt', 'r'); |
| deSerialize(root1, fp); |
| /*printf('Inorder Traversal of the tree constructed from file:n'); |
| inorder(root1);*/ |
| return0; |
| } |
commented Nov 15, 2014
De serialize part is remaining to implement |
commented Nov 15, 2014
commented Nov 18, 2014
int deSerialize(Node *&root, FILE *fp) } |
I recently faced this question during the interview and the interviewer asking me to create two function. Function1 should take the n-ary tree and convert to byte array and function2 should take the byte[] and build the n-ary tree. If it was a binary tree, i would have made pre-order traversal with the special character for null and stored in an array and converted to byte[] but here n-ary tree (with many children). I don't know how to store this and rebuild the n-ary tree with an array. Any ideas or formula to store this n-ary tree into array?. I appreciate your help.
4 Answers
It is needed to distinguish between two cases: 1. complete n-ary Trees and 2. sparse n-ary or non-Complete Trees. In the first case, assuming that N=5 so each level i in the Tree will have exactly (i.e. no less, no more) 5^i nodes; on the other hand, in the second case, this rule isn't valid since the Tree can be filled randomly by construction.
Complete n-ary Trees can be serialized into an array; simply extending from the complete Binary Search Tree: nodes (intermediary and leaves) are related each other by the level i and the actual N by the forum Ni+1+c* where c is the c-th child. Adopting a level-order traversal, the Tree can be optimally serialized in an array of bytes (no further characters are needed, read hereafter). Here a comprehensive explanation.
Unfortunately, for the non-Complete n-ary Trees, as anticipated, the above formula doesn't apply. Therefore a different approach needs to be adopted. One approach would consist in serializing special characters indicating the absence of children, or better serializing the NULL values of the children pointers. This approach is not optimal, since a further number of characters are needed (totally N additional bytes are needed) but it's a pretty straightforward and viable one. Let's examine an example:
adopting a pre-order traversal, the above non-Complete n-ary Tree is serialized as follows
the '/' maps the NULL and provides the ability to deserialize the Tree into the original one. A pre-order traversal is adopted to visit the Tree and output the above array of characters. In total *2*N* bytes are serialized, since in that case the Tree values are exactly 1 character each. As deserialization algorithm, still the pre-order traversal can be adopted: few modifications are needed to recognize the NULLs mapping pattern, as above represented. A C++ code example is here.
Concluding, serializing and deserializing a non-Complete or sparse n-ary Tree is a bit more tricky and needs a further amount of bytes to forcely map the NULLs.
Looks to me like a good use for recursion. Write a method (subroutine, function) that writes out one node and all the tree below it. It would write out the node, then write out the number of children (zero for leaf nodes), then call itself to write each child if there are any. Now call the method on the top node in the tree and you've serialized it.
To deserialize, write a method that reads in a node. It would read in the node itself, read in the number of child nodes, then read in each child node, if any. Call it once on the stream and it will hand you the top node with all the descendant nodes in place--the entire tree.
The moral of this story is that recursion (which is really just a convenient way to get and use a stack) is really useful for working with graphs. And a lot more things than you might think are graphs.
Actually wikipedia helped me to find solution. I am able to store the n-ary tree into array and convert into byte[] and then convert the byte[] back to array using the below formulac-th child is found at index k*i + 1 + c parent is found at index i -1/2
Here is the code, BFS + Queue, should be straight forward to read.