如何序列化二叉樹

Question

今天我去了一個採訪，要求我序列化一棵二叉樹。我實現了一個基於數組的方法，其中節點i的子節點（在水平順序遍歷中編號）位於左側子節點的2 * i索引處，而右側子節點處於2 * i + 1處。面試官似乎或多或少感到高興，但我想知道序列化究竟意味着什麼？比如說，它是專門用於平坦化寫入磁盤的樹，還是序列化樹還包括將樹轉換爲鏈表。另外，我們將如何將樹變成一個（雙重）鏈表，然後重構它？你能從鏈表重新創建樹的確切結構嗎？

Answer 1

方法1： 做既中序和序遍歷到searialize樹數據。 關於反序列化，使用預訂並在Inorder上執行BST以正確形成樹。

同時需要因爲A - >乙 - > C可被表示爲預爲了即使該結構可以是不同的。

方法二：使用 ＃作爲定點徘徊無論向左或向右的孩子是空.....

Answer 2

如何執行中序遍歷並把根密鑰以及所有節點的密鑰到一個std ::你選擇的列表或其他容器使樹變平。然後，只需使用boost庫序列化您選擇的std :: list或container。

反向簡單，然後使用標準插入到二進制樹重建樹。對於非常大的樹來說，這可能不是完全有效的，但運行時將樹轉換爲std :: list最多爲O（n），重建樹最多爲O（log n）。

我即將做到這一點，以序列化我剛剛用C++編碼的樹，因爲我正在將數據庫從Java轉換爲C++。

Answer 3

所有這些文章主要討論序列化部分。反序列化部分在一次傳遞中有點棘手。

我已經實現了反序列化的有效的解決方案了。

問題：序列化和反序列化含有正數的二進制樹。

連載：

1. 用0表示空。
2. 使用預先遍歷序列化爲整數列表。

反序列化部分：

1. 發生在整數的列表，並使用遞歸的helper方法用於反序列化。
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

使用前序遍歷，序列化二進制樹。 使用相同的預遍遍來反序列化樹。小心邊緣情況。這裏空節點由「＃」表示

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是節點數（條目數）在樹中

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


} 

}