Как сериализовать двоичное дерево

Question

Сегодня я отправился на собеседование, где меня попросили сериализовать двоичное дерево. Я применил подход на основе массива, в котором дети узла i (нумерация в обход уровня) находились в индексе 2 * i для левого ребенка и 2 * i + 1 для правильного ребенка. Интервьюер казался более или менее довольным, но мне интересно, что означает сериализация? Это относится к выравниванию дерева для записи на диск или сериализации дерева также включает в себя просто превращение дерева в связанный список, скажем. Также, как мы будем сглаживать дерево в (дважды) связанный список, а затем восстанавливать его? Можете ли вы воссоздать точную структуру дерева из связанного списка?

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Сериализация часть:

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

Десериализация часть:

1. принимает в список целых чисел и использует рекурсивный вспомогательный метод для десериализации.
2. Рекурсивный десериализатор возвращает пару (узел BTNode, int nextIndexToRead), где узел - это узел дерева, построенный до сих пор, а 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; 
    } 
} 

Answer 4

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

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

Answer 5

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

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

Я пытаюсь понять суть этого. Итак, вот моя реализация 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(); 


} 

}