Передача двоичного дерева

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.

Другой метод, похожий на первый, заключается в том, чтобы хранить все дерево в одной части памяти, которые можно сбрасывать и считывать с диска.Указатели в этом случае будут относиться к началу этого фрагмента памяти, а не к абсолютным указателям. Это было бы быстрым способом для двух программ на одном и том же типе машины (с использованием той же самой ширины памяти ЦП) для совместного использования деревьев (или других графиков), но, вероятно, будет трудно реализовать.

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

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

Независимо от того, что вы выберете, вам необходимо убедиться, что вы можете обрабатывать все значения, которые могут присутствовать в качестве данных узла. Например, если данные узла могут содержать ", ) или \n, тогда это может вызвать проблемы в некоторых форматах, которые я показываю, и эти символы должны быть экранированы. Тем не менее, вы можете префикс полей с их длиной или использовать компоновку постоянной структуры.

Вам также необходимо убедиться, что любые двоичные поля сохраняются согласованным образом, если вы планируете обмен данными между различными типами машин. Вы также захотите, чтобы эти данные имели согласованный размер (используйте типы stdint.h, а не int и long) и каноническое представление для таких вещей, как числа с плавающей запятой.

Answer 5

Подход 1: Мы можем перемещаться по дереву дважды:

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 Traversal:

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

Чтобы Получить PostOrder Traversal:

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