二叉樹轉移

Question

如何有效地跨兩個不同系統傳輸二叉樹（非平衡樹），保留其完整結構？

Answer 1

顯而易見的方法是將二叉樹轉換爲一個節點數組，將原始樹中的每個指針替換爲數組中節點的索引。然後您可以傳輸該數組，並在另一端重建具有相同結構的樹。

Answer 2

這種結構下面

[x] 
/ \ 
[L] [R] 
    \ 
    [P] 

給出可以很容易地被翻譯成

(X,(L,-,(P,-,-)),(R,-,-)) 

另外，通過Eric Lippert讀取的柱。

注：我覺得，類似的東西應該適用於任意樹。任何意見？

Answer 3

定義序列化函數。

void serialize(FILE *f, my_tree *node, _Bool is_root) { 
    if (node == NULL) { 
     fputc(no_child, f); 
     return; 
    } 

    if (! is_root) fputc(data_prefix, f); 
    write_data(f, node->data); 
    fputc(data_terminator, f); 

    write_data(node->left_child); 
    write_data(node->right_child); 
} 

void deserialize_node(FILE *f, my_tree *node) { 
    node->data = read_data_field(f); 

    if (fgetc(f) != no_child) { 
     node->left_child = calloc(1, sizeof(my_tree)); 
     deserialize(f, node->left_child, false); 
    } 

    if (fgetc(f) != no_child) { 
     node->right_child = calloc(1, sizeof(my_tree)); 
     deserialize(f, node->right_child, false); 
    } 
} 

試想想起來了，這個簡單的方案（其中data_terminator和no_child必須是單個字符），同時允許data_terminator和no_child相等。

Answer 4

與此相關的主要問題是，您必須使用可用於明確表示指向的節點的其他內容來替換內存表示中的指針或引用。

 foo 
    / \ 
cat  zebra 
    \ 
    dog 

做到這一點的一種方法是交換鍵的指針 - 更像是一個數組索引而不是正確的指針。

1 2 "foo" 
3 _ "cat" 
_ _ "zebra" 
_ _ "dog" 

在該表示中的第一個字段是行號（在0開始計數，這是根節點）的左子，所述第二字段是右孩子，並且第三字段是值。樹按字母順序排列。這看起來很簡單，但實際上很難做到。

類似的方法將把關鍵在每個條目，而不是依靠位置。該方法可以使用原始指針作爲關鍵字，並且讀入代碼必須建立翻譯/符號表以在關鍵字和新指針之間切換。

另一種方式去了解這是口齒不清式的樹： （FOO（貓（）（狗（）（））（斑馬（）（）））

格式化，便於查看：

(foo 
    (cat 
    () 
     (dog 
     () 
     () 
    ) 
    ) 
    (zebra 
     () 
     () 
    ) 
) 

這可以通過一個簡單的中序遍歷容易產生，它也可以用一個很簡單的遞歸體面解析器讀取，也可以改變這個被省略以減少葉子節點的尺寸在序列化格式nil或()或任何您選擇的NULL指針。

另一種類似於第一種的方法是將所有樹存儲在一塊可以轉儲到磁盤上並從磁盤讀回的內存中。這裏的指針將相對於這個內存塊的開始，而不是絕對指針。對於同一類型機器上的兩個程序（使用相同的CPU內存寬度）共享樹（或其他圖），這將是一種快速方式，但可能難以實現。

這個Lisp-esqe版本非常容易實現，但不容易擴展到非樹的東西，其中可能有一個循環引用或一個特定節點的多個父代，雖然它可以做完了。它也不容易擴展來處理在一個特定的文件中存儲多個結構。

行位置索引版本適用於大多數類型的圖形，但在特定文件中存儲多個結構將需要稍微改變此格式。

無論您選擇什麼，您都需要確保您可以處理所有可能作爲節點數據存在的值。例如，如果節點數據可能包含",)或\n，那麼它可能會導致我顯示的某些格式出現問題，並且這些字符需要被轉義。儘管如此，你可以用它們的長度爲字段添加前綴或者使用不變的結構佈局來解決這個問題

如果您計劃在不同機器類型之間共享數據，您還需要確保任何二進制字段都以字節順序存儲。你還會希望這些數據具有一致的大小（使用stdint.h類型而不是int和long）以及像浮點數字這樣的規範表示。

Answer 5

方法一：我們可以遍歷樹兩次：

1. 第一時間拿到了InOrder穿越
2. SecondTime得到PostOrder穿越

現在，通過使用這兩個列表目的地我們可以如下重構二叉樹：

public class ConstructBinaryTreeFromInorderAndPostorder { 

    int index; 

    public TreeNode buildTree(List<Integer> inOrder, List<Integer> postOrder) { 
     index = postOrder.size() - 1; 
     if (postOrder.size() == 1) 
      return new TreeNode(postOrder.get(0)); 

     return constructTree(inOrder,postOrder, 0, postOrder.size() - 1); 
    } 


    public TreeNode constructTree(List<Integer> inOrder, List<Integer> postOrder, int start, int end) { 

     if (start > end) { 
      return null; 
     } 
     TreeNode root = new TreeNode(postOrder.get(index--)); 

     if (start == end) { 
      return root; 
     } 
     int indexInInorder = search(inOrder, start, end, root.val); 

     root.right = constructTree(inOrder, postOrder, indexInInorder + 1, end); 
     root.left = constructTree(inOrder, postOrder, start, indexInInorder - 1); 


     return root; 
    } 


    public int search(List<Integer> inOrder, int strt, int end, int value) { 
     int i = 0; 
     for (i = strt; i <= end; i++) { 
      if (inOrder.get(i) == value) 
       return i; 
     } 
     return i; 
    } 

    public static void main(String[] args) { 
     List<Integer> inorder = Arrays.asList(2, 1, 3); 
     List<Integer> postOrder = Arrays.asList(2, 3, 1); 
     System.out.println(new ConstructBinaryTreeFromInorderAndPostorder().buildTree(inorder,postOrder)); 
    } 
} 

要獲得InOrder穿越：

public class InorderTraversal { 
    void inOrderTraversal2(TreeNode node) { 
     if (node == null) { 
      return; 
     } 
     inOrderTraversal2(node.left); 
     System.out.println(node.val); 
     inOrderTraversal2(node.right); 
    } 
} 

，以獲得PostOrder穿越：

public class PostOrderTraversal { 

    void postOrderTraversal(TreeNode node) { 
     if (node == null) { 
      return; 
     } 
     postOrderTraversal(node.left); 
     postOrderTraversal(node.right); 
     System.out.println(node.val); 
    } 
} 

方法2： 我們可以通過存儲Preorder traversal和null指針的標誌節省空間。 讓爲null指針標記爲「-1」

Input: 
    12 
    /
    13 
Output: 12 13 -1 -1 

Input: 
     20 
    / \ 
    8  22 
Output: 20 8 -1 -1 22 -1 -1 

Input: 
     20 
    / 
     8  
    /\ 
    4 12 
    /\ 
    10 14 
Output: 20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1 

Input: 
      20 
     / 
     8  
    /
    10 
    /
    5 
Output: 20 8 10 5 -1 -1 -1 -1 -1 

Input: 
      20 
      \ 
      8 
       \ 
       10 
       \ 
        5 
Output: 20 -1 8 -1 10 -1 5 -1 -1