Come serializzare l'albero binario

Question

Oggi sono andato a un'intervista dove mi è stato chiesto di serializzare un albero binario. Ho implementato un approccio basato su array in cui i figli del nodo i (numerazione in traversal di ordine di livello) erano nell'indice 2 * i per il figlio sinistro e 2 * i + 1 per il figlio destro. L'intervistatore sembrava più o meno soddisfatto, ma mi chiedo quale serializzazione significhi esattamente? Riguarda specificamente l'appiattimento dell'albero per la scrittura su disco, o la serializzazione di un albero include anche la semplice rotazione dell'albero in una lista collegata, ad esempio. Inoltre, come dovremmo procedere per appiattire l'albero in una lista (doppiamente) collegata e quindi ricostruirla? Riesci a ricreare la struttura esatta dell'albero dalla lista collegata?

Answer 1

Metodo 1: Effettuare l'attraversamento di Inorder e Preorder per eseguire la searializzazione dei dati dell'albero. Nella mancata serializzazione, utilizzare Pre-order e BST su Inorder per formare correttamente l'albero.

È necessario sia perché A -> B -> C può essere rappresentato come pre-ordine anche se la struttura può essere diversa.

Approccio 2: Usa # come una sentinella dovunque il bambino a sinistra oa destra è nullo .....

Answer 2

Come sull'esecuzione di un attraversamento in ordine e mettendo la chiave radice e tutte le chiavi dei nodi in uno std :: elenco o altro contenitore a scelta che appiattisce l'albero. Quindi, serializzate semplicemente la lista std :: o il contenitore di vostra scelta usando la libreria boost.

Il contrario è semplice e quindi ricostruire l'albero utilizzando l'inserimento standard in un albero binario. Questo potrebbe non essere del tutto efficiente per un albero molto grande ma il runtime per convertire l'albero in una std :: list è O (n) al massimo e per ricostruire l'albero è O (log n) al massimo.

Sto per fare questo per serializzare un albero che ho appena codificato in C++ mentre sto convertendo il mio database da Java a C++.

Answer 3

Tutti questi articoli parlano principalmente della parte di serializzazione. La parte di deserializzazione è leggermente complicata da fare in un solo passaggio.

Ho implementato anche una soluzione efficiente per la deserializzazione.

Problema: serializza e deserializza un albero binario contenente numeri positivi.

serializzazione parte:

1. Usa 0 per rappresentare nullo.
2. Serializzare su un elenco di numeri interi utilizzando il preorder traversal.

deserializzazione parte:

1. prende in lista di interi e utilizza metodo di supporto ricorsivo per la deserializzazione.
2. Il deserializzatore ricorsivo restituisce una coppia (nodo BTNode, int nextIndexToRead) dove nodo è un nodo struttura costruito finora e nextIndexToRead è la posizione del prossimo numero da leggere nell'elenco di numeri serializzato.

Di seguito si riporta il codice in Java:

public final class BinaryTreeSerializer 
{ 
    public static List<Integer> Serialize(BTNode root) 
    { 
     List<Integer> serializedNums = new ArrayList<Integer>(); 

     SerializeRecursively(root, serializedNums); 

     return serializedNums; 
    } 

    private static void SerializeRecursively(BTNode node, List<Integer> nums) 
    { 
     if (node == null) 
     { 
      nums.add(0); 
      return; 
     } 

     nums.add(node.data); 
     SerializeRecursively(node.left, nums); 
     SerializeRecursively(node.right, nums); 
    } 

    public static BTNode Deserialize(List<Integer> serializedNums) 
    { 
     Pair pair = DeserializeRecursively(serializedNums, 0); 

     return pair.node; 
    } 

    private static Pair DeserializeRecursively(List<Integer> serializedNums, int start) 
    {   
     int num = serializedNums.get(start); 

     if (num == 0) 
     { 
      return new Pair(null, start + 1); 
     } 

     BTNode node = new BTNode(num); 

     Pair p1 = DeserializeRecursively(serializedNums, start + 1); 
     node.left = p1.node; 

     Pair p2 = DeserializeRecursively(serializedNums, p1.startIndex); 
     node.right = p2.node; 

     return new Pair(node, p2.startIndex); 
    } 

    private static final class Pair 
    { 
     BTNode node; 
     int startIndex; 

     private Pair(BTNode node, int index) 
     { 
      this.node = node; 
      this.startIndex = index; 
     } 
    } 
} 

public class BTNode 
{ 
    public int data; 
    public BTNode left; 
    public BTNode right; 

    public BTNode(int data) 
    { 
     this.data = data; 
    } 
} 

Answer 4

Il modo migliore è quello di utilizzare un carattere speciale (come # come commento precedente menzionato) come sentinella. È meglio che costruire un array inorder traversal e un array preorder/postorder traversal, sia in termini di complessità spaziale sia in termini di complessità temporale. è anche molto più semplice da implementare.

lista

Collegato non è una buona misura qui dal al fine di ricostruire l'albero, è meglio avere il tempo di accesso const elemento

Answer 5

Utilizzando pre traversal ordine, serializzare albero binario. Utilizzare lo stesso traversal pre-ordine per deserializzare l'albero. Fai attenzione ai casi limite. Qui nodi nulli sono rappresentati da "#"

public static String serialize(TreeNode root){ 
      StringBuilder sb = new StringBuilder(); 
      serialize(root, sb); 
      return sb.toString(); 
     } 

    private static void serialize(TreeNode node, StringBuilder sb){ 
     if (node == null) { 
      sb.append("# "); 
     } else { 
      sb.append(node.val + " "); 
      serialize(node.left, sb); 
      serialize(node.right, sb); 
     } 
    } 

    public static TreeNode deserialize(String s){ 
     if (s == null || s.length() == 0) return null; 
     StringTokenizer st = new StringTokenizer(s, " "); 
     return deserialize(st); 
    } 

    private static TreeNode deserialize(StringTokenizer st){ 
     if (!st.hasMoreTokens()) 
      return null; 
     String val = st.nextToken(); 
     if (val.equals("#")) 
      return null; 
     TreeNode root = new TreeNode(Integer.parseInt(val)); 
     root.left = deserialize(st); 
     root.right = deserialize(st); 
     return root; 
    } 

Answer 6

Ho cercato di ottenere l'essenza di esso. Quindi ecco la mia implementazione Java. Come accennato, questo è un albero binario non un BST. Per la serializzazione, un attraversamento preordinato sembra funzionare più facilmente (su una stringa con "NULL" per i nodi null). Si prega di controllare il codice qui sotto con un esempio completo di chiamate di ricorsione. Per la deserializzazione, la stringa viene convertita in una lista collegata dove remove (0) ottiene l'elemento superiore in un tempo di esecuzione O (1). Si prega di vedere anche un esempio completo nei commenti del codice per la deserializzazione. Spero che questo aiuti qualcuno a combattere meno di quanto ho fatto :) Il tempo di esecuzione complessivo per ciascun metodo (serializza e deserializza) è lo stesso tempo di esecuzione per l'attraversamento di un albero binario, ovvero O (n) dove n è il numero di nodi (voci) nell'albero

import java.util.LinkedList; import java.util.List;

public class SerDesBinTree {

public static class TreeEntry<T>{ 
    T element; 
    TreeEntry<T> left; 
    TreeEntry<T> right; 
    public TreeEntry(T x){ 
     element = x; 
     left = null; 
     right = null; 
    } 
} 

TreeEntry<T> root; 
int size; 
StringBuilder serSB = new StringBuilder(); 
List<String> desList = new LinkedList<>(); 

public SerDesBinTree(){ 
    root = null; 
    size = 0; 
} 

public void traverseInOrder(){ 
    traverseInOrder(this.root); 
} 

public void traverseInOrder(TreeEntry<T> node){ 
    if (node != null){ 
     traverseInOrder(node.left); 
     System.out.println(node.element); 
     traverseInOrder(node.right); 
    } 
} 

public void serialize(){ 
    serialize(this.root); 
} 


/* 
*   1 
*  /\ 
*  2 3 
*   /
*   4 
*   
*  ser(1)        
*   serSB.append(1)      serSB: 1 
*   ser(1.left) 
*   ser(1.right) 
*   | 
*   | 
*   ser(1.left=2) 
*    serSB.append(2)     serSB: 1, 2 
*    ser(2.left) 
*    ser(2.right) 
*    | 
*    | 
*    ser(2.left=null) 
*     serSB.append(NULL)   serSB: 1, 2, NULL 
*     return 
*    |  
*    ser(2.right=null) 
*     serSB.append(NULL)   serSB: 1, 2, NULL, NULL 
*     return 
*      
*    | 
*    ser(1.right=3) 
*    serSB.append(3)     serSB: 1, 2, NULL, NULL, 3 
*    ser(3.left) 
*    ser(3.right) 
*     
*    | 
*    ser(3.left=4) 
*     serSB.append(4)    serSB: 1, 2, NULL, NULL, 3, 4 
*     ser(4.left) 
*     ser(4.right) 
*      
*     | 
*     ser(4.left=null) 
*      serSB.append(NULL)  serSB: 1, 2, NULL, NULL, 3, 4, NULL 
*      return 
*       
*     ser(4.right=null) 
*      serSB.append(NULL)  serSB: 1, 2, NULL, NULL, 3, 4, NULL, NULL 
*      return 
*       
*    ser(3.right=null) 
*     serSB.append(NULL)   serSB: 1, 2, NULL, NULL, 3, 4, NULL, NULL, NULL 
*     return 
*   
*/ 
public void serialize(TreeEntry<T> node){ 
    // preorder traversal to build the string 
    // in addition: NULL will be added (to make deserialize easy) 
    // using StringBuilder to append O(1) as opposed to 
    // String which is immutable O(n) 
    if (node == null){ 
     serSB.append("NULL,"); 
     return; 
    } 

    serSB.append(node.element + ","); 
    serialize(node.left); 
    serialize(node.right); 
} 

public TreeEntry<T> deserialize(TreeEntry<T> newRoot){ 
    // convert the StringBuilder into a list 
    // so we can do list.remove() for the first element in O(1) time 

    String[] desArr = serSB.toString().split(","); 

    for (String s : desArr){ 
     desList.add(s); 
    } 


    return deserialize(newRoot, desList); 
} 


/* 
*   1 
*  /\ 
*  2 3 
*   /
*   4 
* 
*  deser(root, list)        list: 1, 2, NULL, NULL, 3, 4, NULL, NULL, NULL 
*   root = new TreeEntry(1)     list: 2, NULL, NULL, 3, 4, NULL, NULL, NULL 
*   root.left = deser(root.left, list) // ** 
*   root.right = deser(root.right, list) // *-* 
*   return root // ^*^ 
*    
*    
*  so far subtree 
*   1 
*  /\ 
*  null null 
*    
*   deser(root.left, list) 
*     root.left = new TreeEntry(2)   list: NULL, NULL, 3, 4, NULL, NULL, NULL 
*     root.left.left = deser(root.left.left, list) // *** 
*     root.left.right = deser(root.left.right, list) // **** 
*     return root.left // eventually return new TreeEntry(2) to ** above after the two calls are done 
*     
*   so far subtree 
*     2 
*    /\ 
*   null null 
*     
*     deser(root.left.left, list)  
*      // won't go further down as the next in list is NULL 
*      return null // to ***     list: NULL, 3, 4, NULL, NULL, NULL 
*      
*   so far subtree (same, just replacing null) 
*     2 
*    /\ 
*   null null 
*    
*     deser(root.left.right, list) 
*      // won't go further down as the next in list is NULL 
*      return null // to ****     list: 3, 4, NULL, NULL, NULL 
*      
*   so far subtree (same, just replacing null) 
*     2 
*    /\ 
*   null null 
*    
*  
*  so far subtree // as node 2 completely returns to ** above 
*   1 
*  /\ 
*  2 null 
*  /\ 
* null null 
*  
*  
*   deser(root.right, list) 
*     root.right = new TreeEntry(3)    list: 4, NULL, NULL, NULL 
*     root.right.left = deser(root.right.left, list) // *&* 
*     root.right.right = deser(root.right.right, list) // *---* 
*     return root.right // eventually return to *-* above after the previous two calls are done 
*     
*   so far subtree 
*     3 
*    /\ 
*   null null 
*    
*    
*     deser(root.right.left, list) 
*      root.right.left = new TreeEntry(4)  list: NULL, NULL, NULL 
*      root.right.left.left = deser(root.right.left.left, list) // *(* 
*      root.right.left.right = deser(root.right.left.right, list) // *)* 
*      return root.right.left // to *&* 
*      
*     so far subtree 
*      4 
*     /\ 
*     null null 
*      
*      deser(root.right.left.left, list) 
*        // won't go further down as the next in list is NULL 
*        return null // to *(*   list: NULL, NULL 
*        
*     so far subtree (same, just replacing null) 
*      4 
*     /\ 
*     null null 
*     
*      deser(root.right.left.right, list) 
*        // won't go further down as the next in list is NULL 
*        return null // to *)*   list: NULL 
*        
*        
*     so far subtree (same, just replacing null) 
*      4 
*     /\ 
*     null null 
*     
*     
*   so far subtree 
*     3 
*    /\ 
*    4 null 
*   /\ 
*   null null 
*     
*     
*    deser(root.right.right, list) 
*      // won't go further down as the next in list is NULL 
*      return null // to *---* list: empty 
*      
*   so far subtree (same, just replacing null of the 3 right) 
*     3 
*    /\ 
*    4 null 
*   /\ 
*   null null 
*   
*   
*   now returning the subtree rooted at 3 to root.right in *-* 
*   
*   1 
*  /\ 
*  / \ 
*  / \ 
*  2  3 
* /\ /\ 
* null null/ null 
*   /
*   4 
*  /\ 
*  null null 
*  
*  
*  finally, return root (the tree rooted at 1) // see ^*^ above 
*  
*/ 
public TreeEntry<T> deserialize(TreeEntry<T> node, List<String> desList){ 

    if (desList.size() == 0){ 
     return null; 
    } 

    String s = desList.remove(0); // efficient operation O(1) 
    if (s.equals("NULL")){ 
     return null; 
    } 

    Integer sInt = Integer.parseInt(s); 
    node = new TreeEntry<T>((T)sInt); 

    node.left = deserialize(node.left, desList); 
    node.right = deserialize(node.right, desList); 

    return node; 
} 


public static void main(String[] args) { 
    /* 
    *   1 
    *  /\ 
    *  2 3 
    *   /
    *   4 
    *   
    */ 
    SerDesBinTree<Integer> tree = new SerDesBinTree<>(); 
    tree.root = new TreeEntry<Integer>(1); 
    tree.root.left = new TreeEntry<Integer>(2); 
    tree.root.right = new TreeEntry<Integer>(3); 
    tree.root.right.left = new TreeEntry<Integer>(4); 
    //tree.traverseInOrder(); 

    tree.serialize(); 
    //System.out.println(tree.serSB); 

    tree.root = null; 
    //tree.traverseInOrder(); 

    tree.root = tree.deserialize(tree.root); 
    //tree.traverseInOrder(); 

    // deserialize into a new tree 
    SerDesBinTree<Integer> newTree = new SerDesBinTree<>(); 
    newTree.root = tree.deserialize(newTree.root); 
    newTree.traverseInOrder(); 


} 

}