Serialisierung eines Binärbaums

Question

Ich war heute bei einem Vorstellungsgespräch, bei dem ich gebeten wurde, einen Binärbaum zu serialisieren. Ich habe einen Array-basierten Ansatz implementiert, bei dem die Kinder des Knotens i (Nummerierung im Level-Order-Traversal) beim Index 2*i für das linke Kind und 2*i + 1 für das rechte Kind liegen. Der Interviewer schien mehr oder weniger zufrieden zu sein, aber ich frage mich, was serialisieren genau bedeutet? Bezieht es sich speziell auf die Verflachung des Baums, um ihn auf die Festplatte zu schreiben, oder würde das Serialisieren eines Baums auch die Umwandlung des Baums in eine verknüpfte Liste einschließen, zum Beispiel. Und wie würde man den Baum in eine (doppelt) verknüpfte Liste umwandeln und dann rekonstruieren? Kann man die genaue Struktur des Baums aus der verknüpften Liste wiederherstellen?

Answer 1

In all diesen Artikeln geht es hauptsächlich um den Teil der Serialisierung. Die Deserialisierung Teil ist etwas schwierig, in einem Durchgang zu tun.

Ich habe auch eine effiziente Lösung für die Deserialisierung implementiert.

Problem: Serialisieren und Deserialisieren eines Binärbaums mit positiven Zahlen.

Teil der Serialisierung:

1. Verwenden Sie 0, um Null darzustellen.
2. Serialisierung in eine Liste von Ganzzahlen unter Verwendung von Preorder Traversal.

Teil der Deserialisierung:

1. Nimmt eine Liste von Ganzzahlen auf und verwendet eine rekursive Hilfsmethode zur Deserialisierung.
2. Der rekursive Deserialisierer gibt ein Paar (BTNode node, int nextIndexToRead) zurück, wobei node der bisher konstruierte Baumknoten ist und nextIndexToRead die Position der nächsten zu lesenden Zahl in der serialisierten Liste der Zahlen.

Nachfolgend finden Sie den Code 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 2

Serialisierung des Binärbaums mittels Pre-Order-Traversal. Verwenden Sie denselben Pre-Order-Traversal, um den Baum zu deserialisieren. Seien Sie vorsichtig mit den Randfällen. Hier werden Null-Knoten durch "#" dargestellt.

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 3

Ansatz 1: Führen Sie sowohl Inorder- als auch Preorder-Traversal durch, um die Baumdaten zu searialisieren. Bei der De-Serialisierung verwenden Sie Pre-order und führen BST auf Inorder aus, um den Baum richtig zu formen.

Sie brauchen beides, weil A -> B -> C als Vorordnung dargestellt werden kann, auch wenn die Struktur unterschiedlich sein kann.

Ansatz 2: Verwenden Sie # als Sentinel, wo immer das linke oder rechte Kind null ist.....

Answer 4

Ich habe versucht, das Wesentliche zu verstehen. Hier ist also meine Java-Implementierung. Wie bereits erwähnt, handelt es sich um einen Binärbaum und nicht um eine BST. Für die Serialisierung scheint ein Pre-Order-Traversal einfacher zu funktionieren (in einen String mit "NULL" für Null-Knoten). Bitte sehen Sie sich den Code unten mit einem vollständigen Beispiel für Rekursionsaufrufe an. Für die Deserialisierung wird die Zeichenkette in eine LinkedList konvertiert, wobei remove(0) das oberste Element in einer Laufzeit von O(1) erhält. Ein vollständiges Beispiel für die Deserialisierung finden Sie in den Kommentaren des Codes. Ich hoffe, das hilft jemandem, der weniger Probleme hat als ich :) Die Gesamtlaufzeit für jede Methode (serialize und deserialize) ist die gleiche Laufzeit für die Durchquerung eines Binärbaums, d.h. O(n), wobei n die Anzahl der Knoten (Einträge) im Baum ist

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

public class SerDesBinTree<T> {

    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();

    }
}

Answer 5

Wie wäre es, ein in-order traversal durchzuführen und den Root-Schlüssel und alle Knotenschlüssel in eine std::list oder einen anderen Container Ihrer Wahl zu packen, der den Baum flach macht. Dann serialisieren Sie einfach die std::list oder den Container Ihrer Wahl mit der boost-Bibliothek.

Die Umkehrung ist einfach, und dann bauen Sie den Baum mit der Standardeinfügung in einen Binärbaum um. Dies mag für einen sehr großen Baum nicht ganz effizient sein, aber die Laufzeit für die Konvertierung des Baums in eine std::list ist höchstens O(n) und der Wiederaufbau des Baums ist höchstens O(log n).

Ich bin im Begriff, dies zu tun, um einen Baum zu serialisieren, den ich gerade in C++ kodiert habe, da ich meine Datenbank von Java nach C++ konvertiere.