Transferencia de árbol binario

Question

Cómo transferir un árbol binario (no un árbol equilibrado) a través de dos sistemas diferentes de manera eficiente, conservando su estructura completa?

Answer 1

La forma obvia sería convertir su árbol binario a una matriz de nodos, reemplazando cada puntero en el árbol original con un índice a un nodo en la matriz. A continuación, puede transmitir esa matriz y, en el otro extremo, reconstruir un árbol con una estructura idéntica.

Answer 2

Esta estructura dada a continuación

[x] 
/ \ 
[L] [R] 
    \ 
    [P] 

puede traducirse fácilmente en

(X,(L,-,(P,-,-)),(R,-,-)) 

También, leer un mensaje por Eric Lippert.

NOTA: Siento que algo similar debería funcionar para árboles arbitrarios. ¿Algún comentario?

Answer 3

Define las funciones de serialización.

void serialize(FILE *f, my_tree *node, _Bool is_root) { 
    if (node == NULL) { 
     fputc(no_child, f); 
     return; 
    } 

    if (! is_root) fputc(data_prefix, f); 
    write_data(f, node->data); 
    fputc(data_terminator, f); 

    write_data(node->left_child); 
    write_data(node->right_child); 
} 

void deserialize_node(FILE *f, my_tree *node) { 
    node->data = read_data_field(f); 

    if (fgetc(f) != no_child) { 
     node->left_child = calloc(1, sizeof(my_tree)); 
     deserialize(f, node->left_child, false); 
    } 

    if (fgetc(f) != no_child) { 
     node->right_child = calloc(1, sizeof(my_tree)); 
     deserialize(f, node->right_child, false); 
    } 
} 

Ahora que lo pienso, este esquema simple (donde data_terminatorno_child y debe haber caracteres individuales) permite tanto data_terminator y no_child a ser igual.

Answer 4

El problema principal con esto es que debe reemplazar punteros o referencias de su representación en memoria por otra cosa que pueda usarse para representar inequívocamente el nodo al que se ha apuntado.

 foo 
    / \ 
cat  zebra 
    \ 
    dog 

Una forma de hacer esto es intercambiar los punteros para las llaves - más como un índice de matriz de un puntero adecuado.

1 2 "foo" 
3 _ "cat" 
_ _ "zebra" 
_ _ "dog" 

En esta representación el primer campo es el número de línea (contaje comienza en 0, que es el nodo raíz) del hijo izquierdo, el segundo campo es el hijo derecho, y el tercer campo es el valor. El árbol está ordenado alfabéticamente. Esto parece simple, pero puede ser difícil de hacer.

Un enfoque similar colocaría la llave en cada entrada en lugar de depender de la posición. Este método podría usar los punteros originales ya que las claves y el código de lectura tendrían que crear una tabla de traducción/símbolo para alternar entre las teclas y los nuevos punteros.

Otra forma de hacerlo es con un árbol de Lisp-esque: (foo (cat() (perro()()) (cebra()()))

con formato para facilitar la visualización:

(foo 
    (cat 
    () 
     (dog 
     () 
     () 
    ) 
    ) 
    (zebra 
     () 
     () 
    ) 
) 

esto puede ser fácilmente generado por un simple en el recorrido de orden. también se puede leer con un analizador simple decente recursiva. también puede alterar este para disminuir el tamaño de los nodos hoja en el formato serializado omitiendo nil o () o lo que sea que elija para los indicadores NULL.

Otro método, similar al primero, es almacenar todo el árbol en un fragmento de memoria que se puede volcar y leer desde el disco.Los indicadores en esto serían relativos al comienzo de este trozo de memoria, en lugar de punteros absolutos. Esta sería una forma rápida para dos programas en el mismo tipo de máquina (usando el mismo ancho de memoria de la CPU) para compartir árboles (u otros gráficos), pero es probable que sea difícil de implementar.

La versión lisp-esqe de esto es súper fácil de implementar, pero no se extiende fácilmente a cosas que no son árboles, donde podría haber una referencia cíclica o más de un padre para un nodo particular, aunque puede estar hecho. Tampoco se extiende fácilmente para manejar el almacenamiento de más de una estructura en un archivo en particular.

La versión de índice de posición de línea funciona para la mayoría de los tipos de gráficos, pero almacenar más de una estructura en un archivo en particular tendría que alterar este formato.

Independientemente de lo que elija, deberá asegurarse de que puede manejar todos los valores que podrían estar presentes como datos de nodo. Por ejemplo, si los datos del nodo pueden contener un ", ) o \n, entonces podría causar problemas en algunos de los formatos que he mostrado, y esos caracteres deberían escaparse. Sin embargo, podría prefijar los campos con su longitud o usar un diseño de estructura constante para dar cuenta de esto.

También deberá asegurarse de que los campos binarios se almacenen de manera consistente si planea compartir datos entre diferentes tipos de máquinas. También querrá que estos datos tengan un tamaño consistente (use los tipos stdint.h en lugar de int y long) y una representación canónica para cosas como números de coma flotante.

Answer 5

Enfoque 1: Podemos recorrer el árbol dos veces:

1. primera vez para obtener el InOrder Transversal
2. SecondTime para obtener el PostOrder Transversal

Ahora Mediante el uso de estas dos listas en el destino podemos reconstruir el árbol binario de la siguiente manera:

public class ConstructBinaryTreeFromInorderAndPostorder { 

    int index; 

    public TreeNode buildTree(List<Integer> inOrder, List<Integer> postOrder) { 
     index = postOrder.size() - 1; 
     if (postOrder.size() == 1) 
      return new TreeNode(postOrder.get(0)); 

     return constructTree(inOrder,postOrder, 0, postOrder.size() - 1); 
    } 


    public TreeNode constructTree(List<Integer> inOrder, List<Integer> postOrder, int start, int end) { 

     if (start > end) { 
      return null; 
     } 
     TreeNode root = new TreeNode(postOrder.get(index--)); 

     if (start == end) { 
      return root; 
     } 
     int indexInInorder = search(inOrder, start, end, root.val); 

     root.right = constructTree(inOrder, postOrder, indexInInorder + 1, end); 
     root.left = constructTree(inOrder, postOrder, start, indexInInorder - 1); 


     return root; 
    } 


    public int search(List<Integer> inOrder, int strt, int end, int value) { 
     int i = 0; 
     for (i = strt; i <= end; i++) { 
      if (inOrder.get(i) == value) 
       return i; 
     } 
     return i; 
    } 

    public static void main(String[] args) { 
     List<Integer> inorder = Arrays.asList(2, 1, 3); 
     List<Integer> postOrder = Arrays.asList(2, 3, 1); 
     System.out.println(new ConstructBinaryTreeFromInorderAndPostorder().buildTree(inorder,postOrder)); 
    } 
} 

para obtener la Transversal InOrder:

public class InorderTraversal { 
    void inOrderTraversal2(TreeNode node) { 
     if (node == null) { 
      return; 
     } 
     inOrderTraversal2(node.left); 
     System.out.println(node.val); 
     inOrderTraversal2(node.right); 
    } 
} 

para obtener la Transversal PostOrder:

public class PostOrderTraversal { 

    void postOrderTraversal(TreeNode node) { 
     if (node == null) { 
      return; 
     } 
     postOrderTraversal(node.left); 
     postOrderTraversal(node.right); 
     System.out.println(node.val); 
    } 
} 

Enfoque 2: Podemos ahorrar espacio mediante el almacenamiento de Preorder traversal y un marcador para null punteros. Que el marcador para null punteros ser '-1'

Input: 
    12 
    /
    13 
Output: 12 13 -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