Serializar y deserializar un árbol binario

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.

Las siguientes son algunas versiones más simples del problema:

Si el árbol dado es un árbol de búsqueda binario?  
Si el árbol binario dado es el árbol de búsqueda binaria, podemos almacenarlo almacenando el recorrido previo o posterior al pedido. En el caso de los árboles de búsqueda binarios, solo el recorrido previo o posterior al pedido es suficiente para almacenar información de estructura . 

Si el árbol binario dado es el árbol completo?  
Un árbol binario está completo si todos los niveles están completamente llenos, excepto posiblemente el último nivel, y todos los Nodes del último nivel están lo más a la izquierda posible (los montones binarios son un árbol binario completo). Para un árbol binario completo, el recorrido de orden de niveles es suficiente para almacenar el árbol. Sabemos que el primer Node es raíz, los siguientes dos Nodes son Nodes del siguiente nivel, los siguientes cuatro Nodes son Nodes del segundo nivel y así sucesivamente. 

Si el árbol binario dado es el árbol completo?  
Un binario completo es un árbol binario donde cada Node tiene 0 o 2 hijos. Es fácil serializar tales árboles ya que cada Node interno tiene 2 hijos. Simplemente podemos almacenar el recorrido de preorden y almacenar un bit con cada Node para indicar si el Node es un Node interno o un Node de hoja.

¿Cómo almacenar un árbol binario general?  
Una solución simple es almacenar recorridos tanto en orden como en preorden. Esta solución requiere espacio el doble del tamaño de Binary Tree. 
Podemos ahorrar espacio almacenando el recorrido Preorder y un marcador para punteros NULL. 

Let the marker for NULL pointers be '-1'
Input:
     12
    /
  13
Output: 12 13 -1 -1 -1

Input:
      20
    /   \
   8     22 
Output: 20 8 -1 -1 22 -1 -1 

Input:
         20
       /    
      8     
     / \
    4  12 
      /  \
     10  14
Output: 20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1 

Input:
          20
         /    
        8     
      /
    10
    /
   5
Output: 20 8 10 5 -1 -1 -1 -1 -1 

Input:
          20
            \
             8
              \   
               10
                 \
                  5   
Output: 20 -1 8 -1 10 -1 5 -1 -1

La deserialización se puede realizar simplemente leyendo los datos del archivo uno por uno. 

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

// A C++ program to demonstrate serialization and deserialization of
// Binary Tree
#include <iostream>
#define MARKER -1
 
/* A binary tree Node has key, pointer to left and right children */
struct Node
{
    int key;
    struct Node* left, *right;
};
 
/* Helper function that allocates a new Node with the
   given key and NULL left and right pointers. */
struct Node* newNode(int key)
{
    struct Node* temp = new Node();
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// This function stores a tree in a file pointed by fp
void serialize(Node *root, FILE *fp)
{
    // If current node is NULL, store marker
    if (root == NULL)
    {
        fprintf(fp, "%d ", MARKER);
        return;
    }
 
    // Else, store current node and recur for its children
    fprintf(fp, "%d ", root->key);
    serialize(root->left, fp);
    serialize(root->right, fp);
}
 
// This function constructs a tree from a file pointed by 'fp'
void deSerialize(Node *&root, FILE *fp)
{
    // Read next item from file. If there are no more items or next
    // item is marker, then return
    int val;
    if ( !fscanf(fp, "%d ", &val) || val == MARKER)
       return;
 
    // Else create node with this item and recur for children
    root = newNode(val);
    deSerialize(root->left, fp);
    deSerialize(root->right, 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);
    }
}
 
/* Driver program to test above functions*/
int main()
{
    // Let us construct a tree shown in the above figure
    struct Node *root        = newNode(20);
    root->left               = newNode(8);
    root->right              = newNode(22);
    root->left->left         = newNode(4);
    root->left->right        = newNode(12);
    root->left->right->left  = newNode(10);
    root->left->right->right = newNode(14);
 
    // 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("Inorder Traversal of the tree constructed from file:\n");
    inorder(root1);
 
    return 0;
}

// A JAVA program to demonstrate serialization and
// deserialization of Binary Tree
import java.util.*;
 
/* A binary tree Node has key, pointer to left and right
 * children */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
class BinaryTree {
    TreeNode root;
 
    // Encodes a tree to a single string.
    public static String serialize(TreeNode root)
    {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
 
        List<String> l = new ArrayList<>();
        while (!s.isEmpty()) {
            TreeNode t = s.pop();
            // If current node is NULL, store marker
            if (t == null) {
                l.add("#");
            }
            else {
                // Else, store current node and recur for
                // its children
                l.add("" + t.val);
                s.push(t.right);
                s.push(t.left);
            }
        }
        return String.join(",", l);
    }
 
    static int t;
 
    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data)
    {
        if (data == null)
            return null;
        t = 0;
        String[] arr = data.split(",");
        return helper(arr);
    }
 
    public static TreeNode helper(String[] arr)
    {
        if (arr[t].equals("#"))
            return null;
        // create node with this item and recur for children
        TreeNode root
            = new TreeNode(Integer.parseInt(arr[t]));
        t++;
        root.left = helper(arr);
        t++;
        root.right = helper(arr);
        return root;
    }
 
    // A simple inorder traversal used for testing the
    // constructed tree
    static void inorder(TreeNode root)
    {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
        }
    }
 
    /* Driver program to test above functions*/
    public static void main(String args[])
    {
        // Let us construct a tree shown in the above figure
        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(20);
        tree.root.left = new TreeNode(8);
        tree.root.right = new TreeNode(22);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(12);
        tree.root.left.right.left = new TreeNode(10);
        tree.root.left.right.right = new TreeNode(14);
 
        String serialized = serialize(tree.root);
        System.out.println("Serialized view of the tree:");
        System.out.println(serialized);
        System.out.println();
 
        // Let us deserialize the stored tree into root1
        TreeNode t = deserialize(serialized);
 
        System.out.println(
            "Inorder Traversal of the tree constructed from serialized String:");
        inorder(t);
    }
}

¿Cuánto espacio adicional se requiere en la solución anterior?  
Si hay n claves, entonces la solución anterior requiere n+1 marcadores, lo que puede ser mejor que una solución simple (almacenar las claves dos veces) en situaciones en las que las claves son grandes o las claves tienen elementos de datos grandes asociados con ellas.

¿Podemos optimizarlo aún más?  
La solución anterior se puede optimizar de muchas maneras. Si observamos más de cerca los árboles serializados anteriores, podemos observar que todos los Nodes de hoja requieren dos marcadores. Una optimización simple es almacenar un bit separado con cada Node para indicar que el Node es interno o externo. De esta manera, no tenemos que almacenar dos marcadores con cada Node de hoja, ya que las hojas se pueden identificar con un bit adicional. Todavía necesitamos un marcador para los Nodes internos con un hijo. Por ejemplo, en el siguiente diagrama, ‘ se usa para indicar un bit de conjunto de Node interno, y ‘/’ se usa como marcador NULL. El diagrama está tomado de aquí . 

Tenga en cuenta que siempre hay más Nodes hoja que Nodes internos en un árbol binario (la cantidad de Nodes hoja es la cantidad de Nodes internos (con grado 2) más 1, por lo que esta optimización tiene sentido).

¿Cómo serializar el árbol n-ario?  
En un árbol n-ario, no hay un hijo izquierdo o derecho designado. Podemos 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. Pronto cubriremos la implementación del árbol n-ario. El diagrama está tomado de aquí .