Serialize And Deserialize A Given N-Ary Tree

 Posted admin
Serialize And Deserialize A Given N-Ary Tree Rating: 5,0/5 6995 reviews
  1. // A C++ Program serialize and deserialize an N-ary tree
  2. #define MARKER ')'
  3. usingnamespace std;
  4. // A node of N-ary tree
  5. char key;
  6. Node *child[N];// An array of pointers for N children
  7. // A utility function to create a new N-ary tree node
  8. {
  9. temp->key = key;
  10. temp->child[i]=NULL;
  11. }
  12. // This function stores the given N-ary tree in a file pointed by fp
  13. {
  14. if(root NULL)return;
  15. // Else, store current node and recur for its children
  16. for(int i =0; i < N && root->child[i]; i++)
  17. fprintf(fp, '%c ', MARKER);
  18. // This function constructs N-ary tree from a file pointed by 'fp'.
  19. // This functionr returns 0 to indicate that the next item is a valid
  20. int deSerialize(Node *&root, FILE*fp)
  21. // Read next item from file. If theere are no more items or next
  22. char val;
  23. return1;
  24. // Else create node with this item and recur for children
  25. for(int i =0; i < N; i++)
  26. break;
  27. // Finally return 0 for successful finish
  28. }
  29. // A utility function to create a dummy tree shown in above diagram
  30. {
  31. root->child[0]= newNode('B');
  32. root->child[2]= newNode('D');
  33. root->child[0]->child[1]= newNode('F');
  34. root->child[2]->child[1]= newNode('H');
  35. root->child[2]->child[3]= newNode('J');
  36. root->child[0]->child[1]->child[0]= newNode('K');
  37. }
  38. // A utlity function to traverse the constructed N-ary tree
  39. {
  40. {
  41. for(int i =0; i < N; i++)
  42. }
  43. int main()
  44. // Let us create an N-ary tree shown in above diagram
  45. // Let us open a file and serialize the tree into the file
  46. if(fp NULL)
  47. puts('Could not open file');
  48. }
  49. fclose(fp);
  50. // Let us deserialize the storeed tree into root1
  51. fp =fopen('tree.txt', 'r');
  52. traverse(root1);
  53. return0;
Embed
treeSerialisation.cpp
//
// 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;
}
Owner Author

commented Nov 15, 2014

De serialize part is remaining to implement

Owner Author

commented Nov 15, 2014

Owner Author

commented Nov 18, 2014

int deSerialize(Node *&root, FILE *fp)
{
// Read next item from file. If theere are no more items or next
// item is marker, then return 1 to indicate same
char val;
if ( !fscanf(fp, '%c ', &val) val MARKER )
return 1;

}

Sign up for freeto join this conversation on GitHub. Already have an account? Sign in to comment