Serializar y deserializar un árbol N-ario

Dado un árbol N-ario donde cada Node tiene como máximo N hijos. ¿Cómo serializarlo y deserializarlo? La serialización consiste en almacenar un árbol en un archivo para que luego pueda restaurarse. La estructura del árbol debe ser mantenida. La deserialización es volver a leer el árbol desde el archivo.
Esta publicación es principalmente una extensión de la siguiente publicación. 
Serializar y deserializar un árbol binario

En un árbol N-ario, no hay hijos derechos e izquierdos designados. Un árbol N-ario se representa almacenando una array o lista de punteros secundarios con cada Node. 

La idea es almacenar un marcador de ‘fin de hijos’ con cada Node. El siguiente diagrama muestra la serialización donde ‘)’ se usa como marcador de final de hijos. 

A continuación se muestra la implementación en C++ de la idea anterior.  

C++

// A C++ Program serialize and deserialize an N-ary tree
#include<cstdio>
#define MARKER ')'
#define N 5
using namespace std;
 
// A node of N-ary tree
struct Node {
   char key;
   Node *child[N];  // An array of pointers for N children
};
 
// A utility function to create a new N-ary tree node
Node *newNode(char key)
{
    Node *temp = new Node;
    temp->key = key;
    for (int i = 0; i < N; i++)
        temp->child[i] = NULL;
    return temp;
}
 
// This function stores the given N-ary tree in a file pointed by fp
void serialize(Node *root, FILE *fp)
{
    // Base case
    if (root == NULL) return;
 
    // Else, store current node and recur for its children
    fprintf(fp, "%c ", root->key);
    for (int i = 0; i < N && root->child[i]; i++)
         serialize(root->child[i],  fp);
 
    // Store marker at the end of children
    fprintf(fp, "%c ", MARKER);
}
 
// This function constructs N-ary tree from a file pointed by 'fp'.
// This function returns 0 to indicate that the next item is a valid
// tree key. Else returns 0
int deSerialize(Node *&root, FILE *fp)
{
    // Read next item from file. If there 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;
 
    // Else create node with this item and recur for children
    root = newNode(val);
    for (int i = 0; i < N; i++)
      if (deSerialize(root->child[i], fp))
         break;
 
    // Finally return 0 for successful finish
    return 0;
}
 
// A utility function to create a dummy tree shown in above diagram
Node *createDummyTree()
{
    Node *root = newNode('A');
    root->child[0] = newNode('B');
    root->child[1] = newNode('C');
    root->child[2] = newNode('D');
    root->child[0]->child[0] = newNode('E');
    root->child[0]->child[1] = newNode('F');
    root->child[2]->child[0] = newNode('G');
    root->child[2]->child[1] = newNode('H');
    root->child[2]->child[2] = newNode('I');
    root->child[2]->child[3] = newNode('J');
    root->child[0]->child[1]->child[0] = newNode('K');
    return root;
}
 
// A utility function to traverse the constructed N-ary tree
void traverse(Node *root)
{
    if (root)
    {
        printf("%c ", root->key);
        for (int i = 0; i < N; i++)
            traverse(root->child[i]);
    }
}
 
// Driver program to test above functions
int main()
{
    // Let us create an N-ary tree shown in above diagram
    Node *root = createDummyTree();
 
    // 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");
        return 0;
    }
    serialize(root, fp);
    fclose(fp);
 
    // Let us deserialize the stored tree into root1
    Node *root1 = NULL;
    fp = fopen("tree.txt", "r");
    deSerialize(root1, fp);
 
    printf("Constructed N-Ary Tree from file is \n");
    traverse(root1);
 
    return 0;
}

Producción: 

Constructed N-Ary Tree from file is
A B E F K C D G H I J

La implementación anterior se puede optimizar de muchas maneras, por ejemplo, mediante el uso de un vector en lugar de una array de punteros. Lo hemos mantenido de esta manera para que sea fácil de leer y comprender.
Este artículo es una contribución de varun . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *