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

Der beste Weg ist, ein spezielles Zeichen (wie #, wie vorherige Kommentar erwähnt) als Sentinel zu verwenden. Es ist besser als ein inorder traversal Array und ein preorder/postorder traversal Array zu konstruieren, sowohl im Raum Komplexität weise und Zeit Komplexität weise. es ist auch viel einfacher zu implementieren.

Eine verknüpfte Liste ist hier nicht gut geeignet, da man für die Rekonstruktion des Baums besser eine konstante Zugriffszeit auf die Elemente hat

Answer 2

Hier ist eine späte Antwort in Python. Sie verwendet (depth-first) preorder serialization und gibt eine Liste von strings . Die Deserialisierung gibt den Baum zurück.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# This method serializes the tree into a string
def serialize(root):
    vals = []
    def encode(node):
        vals.append(str(node.val))
        if node.left is not None:
            encode(node.left)
        else:
            vals.append("L")
        if node.right is not None:
            encode(node.right)
        else:
            vals.append("R")
    encode(root)
    print(vals)
    return vals

# This method deserializes the string back into the tree
def deserialize(string_list):
    def create_a_tree(sub_list):
        if sub_list[0] == 'L' or sub_list[0] == 'R':
            del sub_list[0]
            return None
        parent = Node(sub_list[0])
        del sub_list[0]
        parent.left = create_a_tree(sub_list)
        parent.right = create_a_tree(sub_list)
        return parent
    if len(string_list) != 0:
        root_node = create_a_tree(string_list)
    else:
        print("ERROR - empty string!")
        return 0
    return root_node

Zum Testen:

tree1 = Node('root', Node('left'), Node('right'))
t = deserialize(serialize(tree1))
print(str(t.right.val))

Answer 3

Ich benutze keine Vorbestellung, aber ich benutze BFS. Dies ist eine Frage von leetcode

Die Mehrheit der Menschen Umsetzung sind falsch, wenn mit Vorbestellung: das erwartete Ergebnis sollte sein

"[1,2,3,null,null,4,5]", aber stattdessen drucken die meisten Leute die Ausgabe als "[1,2,3,null,null,4,5,null,null]" aus, da sie die Ebenen nicht mitzählen.

Hier ist meine Implementierung mit dem richtigen Ergebnis.

class Node(object):
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data

def serialize(root):
        queue = [(root,0)]
        result = []
        max_level_with_value = 0
        while queue:
            (node,l) = queue.pop(0)
            if node:
                result.append((node.data,l))
                queue.extend([(node.left,l+1),
                              (node.right,l+1)
                              ])
                max_level_with_value = max(max_level_with_value,l)
            else:
                result.append(('null',l))
        filter_redundant(result,max_level_with_value)

def filter_redundant(result,max_level_with_value):
    for v,l in result:
        if l<= max_level_with_value:
            print(v)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)
serialize(root)

Answer 4

Umwandlung in ein Array mit der Größe (2n + 1) jeder linke Sohn und rechte Sohn wird anstelle von (2 * Knotennummer) und ((2 * Knotennummer) + 1 entsprechend sein.

mit https://www-inst.eecs.berkeley.edu//~cs61bl/r/cur/trees/array-repr.html?topic=lab20.topic&step=1&course=

Answer 5

Serialisieren deserialisieren eines Binärbaums:

public class BTSerialization {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("()");
            return;
        }
        sb.append('(').append(root.val);
        serialize(root.left, sb);
        serialize(root.right, sb);
        sb.append(')');
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if ("()".equals(data)) return null;
        data = data.substring(1, data.length() - 1); // Unwrap the two parenthesis (root(left)(right))
        int i = 0;
        while (data.charAt(i) != '(') i++;
        TreeNode root = new TreeNode(Integer.parseInt(data.substring(0, i)));
        data = data.substring(i);
        i = -1;
        int open = 0;
        while (true) { // Find left child- starts with parenthesis
            i++;
            if (data.charAt(i) == '(') open++;
            else if (data.charAt(i) == ')') {
                open--;
                if (open == 0) break;
            }
        }
        root.left = deserialize(data.substring(0, i + 1));
        data = data.substring(i + 1); // The rest is right child- starts with parenthesis
        root.right = deserialize(data);
        return root;
    }

    public static void main(String[] args) {
        BTSerialization b = new BTSerialization();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        TreeNode root = b.deserialize(b.serialize(node1));
        System.out.println();
    }

}

Serialisieren deserialisieren N-ärer Baum: Mit diesem Code können Sie jeden n-ären Baum serialisieren und deserialisieren. Im Grunde ist ein Binärbaum ein 2-ärer Baum. N gibt die maximale Anzahl der Kinder aller Knoten im gesamten Baum an.

public class CodecNry {

    class Node {
        public int val;
        public List<Node> children;
        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public String serialize(Node root) {
        if (root == null) return ""; // Serialization base case
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(root.val).append(",").append(root.children.size()); // Add root val+,+num of children
        for (Node child : root.children)
            stringBuilder.append(",").append(serialize(child)); // Add children recursively, one by one
        return stringBuilder.toString(); // Return result
    }

    int i;

    public Node deserialize(String data) {
        if (data.isBlank()) return null; // Base case root is null
        i = 0; // The index on the tokens
        return recursiveDeserialize(data.split(",")); // Recursively build the tree from the tokenized string
    }

    private Node recursiveDeserialize(String[] nums) {
        if (i == nums.length) return null; // Base case- no more child
        Node root = new Node(Integer.parseInt(nums[i++]), new ArrayList<>()); // Build the root
        int childrenCount = Integer.parseInt(nums[i++]); // Get number of children
        for (int j = 0; j < childrenCount; j++) { // Add children recursively one by one
            Node child = recursiveDeserialize(nums);
            if (child != null) root.children.add(child); // If child is not null, add it to the children of root
        }
        return root; // Return the root of the tree
    }

}