Serialise Deserialise N-ary Tree

Serialise Deserialise N-ary Tree : N-ary tree’s each node contains at-most N children. Serialise the tree means storing the tree in array or file maintaining tree’s exact structure. On the other hand Deserialise the tree means retrieving/read the Tree from array or file maintaining tree’s exact structure.

Input:

At first a N-ary Tree is created(N=3 here) by a function,inserting new node with data in that node .Suppose consecutively 28,22,2,7,8,13,12,19,25,24 are inserted as data of Tree’s node.Then created Tree will be like below –
 

Output :

The elements of created tree : 28 22 2 7 8 13 12 19 25 24
The elements of tree in serialised form : 28 22 2 -1 -1 -1 7 -1 -1 -1 -1 8 13 -1 -1 -1 -1 -1 12 19 -1 -1 -1 25 -1 -1 -1 24 -1 -1 -1
The retrieved tree from array after deserialisation : 28 22 2 7 8 13 12 19 25 24

Logic :

1.  Create a N-ary Tree ,keep the address of root node in a pointer.
2. Display the elements of created tree by traversing the Tree.
3. Serialise the Tree – store the elements of Tree in an array with marker to indicate leaf node.
A) At first data value of root node is inserted/kept stored in array,then data value of all children of root node are inserted into array one by one through for loop.
B) If leaf node encountered ,then -1 as marker is inserted to array to indicate NULL value in node.
4. Display the serialised form of tree.
5. Deserialise the tree from array – constructing the Tree as earlier from serialised form in array
A) Create root node at first with data value taken from 1st element of array,then create child node and insert data value from element of array into node through for loop.This continues until -1.
B) If array element is -1 ,then NULL is returned to node’s pointer.Same occurs when all elements of array is encountered.
6. Display the retrieved Tree(by deserialisation) by traversing it.

Here code for Serialise Deserialise N-ary Tree with N=3

code :

#include"stdio.h"
#include"stdlib.h"
#define N 3
struct node
{
    int info;
    struct node *child[N];
};
struct node *Root=NULL,*dRoot=NULL;
int dIndex=0,sIndex=0;
struct node* createNode(int data)              //Function to create a new node
{
    struct node * root;
    root=(struct node*)malloc(sizeof(struct node));
    root->info=data;
    for(int k=0; k<N; k++)
        root->child[k]=NULL;
    return root;
}
struct node * createTree()                    //Function to create Tree
{
    struct node * root;
    root=createNode(28);
    root->child[0]=createNode(22);
    root->child[1]=createNode(8);
    root->child[2]=createNode(12);
    root->child[0]->child[0]=createNode(2);
    root->child[0]->child[1]=createNode(7);
    root->child[1]->child[0]=createNode(13);
    root->child[2]->child[0]=createNode(19);
    root->child[2]->child[1]=createNode(25);
    root->child[2]->child[2]=createNode(24);
    return root;
}
void serialize(struct node* root,int arr[])      //Function to serialize Tree
{
    if(root==NULL)
    {
        arr[sIndex]=-1;
        sIndex++;
        return;
    }
    arr[sIndex]=root->info;
    sIndex++;
    for(int k=0; k<N; k++)
        serialize(root->child[k],arr);
}
struct node* deserialize(struct node * root,int arr[]) //Function for deserialization
{
    if(arr[dIndex]==(-1) || dIndex==sIndex-1)
    {
        dIndex++;
        return NULL;
    }
    root=createNode(arr[dIndex]);
    dIndex++;
    for(int k=0; k<N; k++)
    {
        root->child[k]=deserialize(root->child[k],arr);
    }
    return root;
}
void Travers(struct node* root)         //Function to traverse Tree
{
    if(root==NULL)
        return;
    printf(" %d",root->info);
    for(int k=0; k<N; k++)
        Travers(root->child[k]);
}
void main() {
    int array[50];
    Root=createTree();                   //Creating Tree and address of root node returns to Root pointer
    printf("The elements of created tree : ");
    Travers(Root);                      //Displaying the tree by traversing
    serialize(Root,array);              //Serialize the tree
    printf("\nThe elements of tree in serialized form : ");
    for(int j=0; j<sIndex; j++)
        printf("%d ",array[j]);            //Displaying the Tree in serialized form
    printf(" \nThe elements of tree in deserialized form : ");
    dRoot=deserialize(dRoot,array);    //Deserialing
    Travers(dRoot);                    //Displaying the Tree after retrieving after deserialization
}

Click here to see this code running on Ideone platform