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

Unter Serialisierung versteht man die Umwandlung einer Datenstruktur oder eines Objekts in eine Folge von Bits, so dass sie in einer Datei oder einem Speicherpuffer gespeichert oder über eine Netzverbindung übertragen werden können, um später in derselben oder einer anderen Computerumgebung rekonstruiert zu werden.

Bei der Deserialisierung wird die Zeichenkette wieder in die ursprüngliche Baumstruktur umgewandelt.

Das Konzept der Serialisierung und Deserialisierung ist sehr ähnlich zu dem, was ein Compiler mit dem Code macht. Es gibt mehrere Phasen im gesamten Kompilierungsprozess, aber wir werden versuchen, ihn abstrakt zu halten.

Bei einem Stück Code zerlegt der Compiler verschiedene wohldefinierte Komponenten in Token (z. B. int ist ein Token, double ist ein weiteres Token, { ist ein Token, } ist ein weiteres Token usw.). [Link zu einer Demonstration der abstrakten Ebene der Kompilierung][1].

Serialisierung: Für die Serialisierung des Baums in eine Zeichenkette verwenden wir die Traversal-Logik der Vorordnung. Wir fügen "X" hinzu, um einen Null-Zeiger/Knoten in einem Baum zu kennzeichnen. Um unsere Deserialisierungslogik im Auge zu behalten, müssen wir außerdem nach jedem serialisierten Knotenwert ein "," hinzufügen, damit der Deserialisierungsprozess auf jeden mit "," geteilten Knotenwert zugreifen kann.

Leetcode-Link: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Erläuterung von Back To Back SWE Youtube channel : https://www.youtube.com/watch?v=suj1ro8TIVY

For example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,null,null,3,4,null,null,5,null,null,]"

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if(root == null)
            return "X,";

        String leftSerialized = serialize(root.left);
        String rightSerialized = serialize(root.right);

        return root.val + "," + leftSerialized + rightSerialized;
    }

    private TreeNode deserializeHelper(Queue<String> queue)
    {
        String nodeValue = queue.poll();

        if(nodeValue.equals("X"))
            return null;

        TreeNode newNode = new TreeNode(Integer.valueOf(nodeValue));

        newNode.left = deserializeHelper(queue);
        newNode.right = deserializeHelper(queue);

        return newNode;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        Queue<String> queue = new LinkedList<>();
        queue.addAll(Arrays.asList(data.split(",")));

        return deserializeHelper(queue);
    }
}

//Codec object will be instantiated and called as such:
//Codec codec = new Codec();
//codec.deserialize(codec.serialize(root));