Сериализация двоичного дерева

Ответ 1

Все эти статьи говорят в основном о части сериализации. Части десериализации немного сложно сделать за один проход.

Я также внедрил эффективное решение для десериализации.

Проблема: Сериализация и десериализация двоичного дерева, содержащего положительные числа.

Сериализация:

• Использовать 0 для представления null.
• Сериализовать список целых чисел, используя обход предварительного порядка.

Часть десериализации:

• Входит в список целых чисел и использует рекурсивный вспомогательный метод для десериализации.
• Рекурсивный десериализатор возвращает пару (BTNode node, int nextIndexToRead), где node - это дерево node, построенное до сих пор, а nextIndexToRead - это позиция следующего числа, которое должно быть прочитано в сериализованном списке чисел.

Ниже приведен код в 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;
    }
}

Ответ 2

Подход 1: Выполняйте обход букв Inorder и Preorder для поиска данных дерева. При де-сериализации используйте предварительный порядок и сделайте BST на Inorder, чтобы правильно сформировать дерево.

Вам нужны оба, потому что A → B → C может быть представлен как предварительный порядок, хотя структура может быть разной.

Подход 2: Используйте # как часовое, если левый или правый ребенок равен нулю.

Ответ 3

Используя предварительный обход, сериализуйте двоичное дерево. Для десериализации дерева используйте один и тот же предварительный обход. Будьте осторожны с краями. Здесь нулевые узлы представлены "#"

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;
    } 

Ответ 4

Я пытаюсь понять суть этого. Итак, вот моя реализация Java. Как уже упоминалось, это двоичное дерево, а не BST. Для сериализации кажется, что обход предварительного порядка работает легче (для строки с "NULL" для нулевых узлов). Пожалуйста, проверьте приведенный ниже код с полным примером вызовов рекурсии. Для десериализации строка преобразуется в LinkedList, где remove (0) получает верхний элемент в O (1) время выполнения. Также см. Полный пример в комментариях кода для десериализации. Надежда, которая поможет кому-то бороться меньше, чем я.:) Общее время работы для каждого метода (сериализация и десериализация) - это одинаковое время работы для обхода двоичного дерева, т.е. O (n), где n - количество узлов (записей) в дереве

импортировать java.util.LinkedList; import java.util.List;

открытый класс 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();


}

}

Ответ 5

Как выполнить обход в порядке и поместить ключ root и все node ключи в список std:: или другой контейнер по вашему выбору, который выравнивает дерево. Затем просто сериализуйте std:: list или container по вашему выбору, используя библиотеку boost.

Обратное простое, а затем перестроить дерево, используя стандартную вставку в двоичное дерево. Это может быть не совсем эффективно для очень большого дерева, но среда выполнения для преобразования дерева в std:: list - это максимум O (n) и для восстановления дерева - это O (log n) не более.

Я собираюсь сделать это, чтобы сериализовать дерево, которое я только что закодировал в С++, когда я конвертирую свою базу данных с Java на С++.

Ответ 6

Лучший способ - использовать специальный char (например, как предыдущий комментарий) в качестве дозорного. Это лучше, чем создание массива обходного порядка и массива обхода порядка/послепорядка, как по сложности, так и по временной сложности. это также проще реализовать.

Связанный список здесь не подходит, так как для восстановления дерева лучше иметь время доступа к константным элементам

Ответ 7

Вышеупомянутые решения (@AbhishekPrateek и @sreeprasad) могут быть дополнительно оптимизированы по пространству путем дифференцирования и добавления битов для внутренних (узлы, которые имеют дочерние) и внешних (узлы, которые не имеют никаких конечных/дочерних) узлов во время сериализации. Ссылка для получения подробной информации.

Ответ 8

Вот поздний ответ в Python. Он использует (сначала глубину) сериализацию предзаказа и возвращает список strings. Десериализация возвращает дерево.

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

        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

Тестировать:

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

Ответ 9

Я не использую предварительный заказ, но я использую BFS. Это вопрос от leetcode

Реализация большинства людей некорректна при использовании предварительного заказа: ожидаемый результат должен быть

"[1,2,3, null, null, 4,5]", но вместо этого большинство людей выводит вывод как "[1,2,3, NULL, NULL, 4,5, NULL, NULL]" так как они не считают уровни.

Вот моя реализация с правильным результатом.

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)

Ответ 10

Сериализация - это процесс преобразования структуры данных или объекта в последовательность битов, так что они могут быть сохранены в буфере файла или памяти или переданы по каналу сетевого подключения для последующего восстановления в той же или другой компьютерной среде.

Десериализация - это процесс преобразования строки обратно в исходную древовидную структуру.

Концепция сериализации и десериализации очень похожа на то, что компилятор делает с кодом. Есть несколько этапов во всем процессе компиляции, но мы постараемся сохранить его абстрактным.

При наличии фрагмента кода компилятор разбивает различные четко определенные компоненты на токены (например, int - это токен, double - другой токен, {- один токен,} - другой токен и т.д.). [Ссылка на демонстрацию абстрактного уровня компиляции] [1].

Сериализация: Мы используем логику обхода предварительного заказа для сериализации дерева в строку. Мы добавим "X" для обозначения нулевого указателя/узла в дереве. Кроме того, чтобы помнить нашу логику десериализации, нам нужно добавлять "," после каждого сериализованного значения узла, чтобы процесс десериализации мог получить доступ к каждому значению узла, разделенному на ",".

Ссылка на Leetcode: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Объяснение: Back To Back SWE Youtube канал: 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));

Ответ 11

Вот еще один способ сериализации двоичного дерева с использованием (модифицированного) обхода порядка уровней. [Просто скопируйте и вставьте, это работает]. Охватывает все несбалансированное, сбалансированное, наклоненное вправо, наклоненное дерево влево.

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

def getHeight(root):
    if root == None:
        return 0
    return max(getHeight(root.left), getHeight(root.right)) + 1

treeArray = []

def levelOrderTraversal(root, level, numOfNodes):
    if level <= 0 and numOfNodes <=0:
        return

    numOfNodes -= 1

    if root != None and level == 1:
        treeArray.append(root.val)
    elif root == None and level == 1:
        treeArray.append("$")

    if root != None:
        levelOrderTraversal(root.left, level-1, numOfNodes)
        levelOrderTraversal(root.right, level-1, numOfNodes)
    else:
        levelOrderTraversal(root, level-1, numOfNodes)
        levelOrderTraversal(root, level-1, numOfNodes)



def treeToIntArray(root):
    h = getHeight(root)

    for i in range(1, h+1):
        levelOrderTraversal(root,i, i*2)

    return treeArray


def intArrayToTree():
    n = len(treeArray)

    treeArrayOfObjects = [0]*len(treeArray)
    for i in range(n):
        if treeArray[i] != "$":
            root = TreeNode(treeArray[i])
            treeArrayOfObjects[i] = root


    #Linking the child nodes
    for i in range(n):
        if treeArray[i] != "$":
            root = treeArrayOfObjects[i]
            if 2 * i + 1 < n:
                root.left = treeArrayOfObjects[2*i + 1]
            if 2 * i + 2 < n:
                root.right = treeArrayOfObjects[2*i + 2]
            treeArray[i] = root
    return treeArrayOfObjects[0]

"""
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(9)
root.left.left = TreeNode(1)
root.left.right = None
root.right.left = None
root.right.right = TreeNode(4)
"""
root = TreeNode(7)
root.right = TreeNode(9)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(5)

print treeToIntArray(root)
root = intArrayToTree()

print root.val
print root.right.val
print root.right.right.val
print root.right.right.right.val