二叉树转移

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