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

Question

Как эффективно передать бинарное дерево (не сбалансированное дерево) в две разные системы, сохранив его полную структуру?

Answer 1

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

Answer 2

Эта структура приведена ниже

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

можно легко перевести на

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

Кроме того, прочитайте сообщение Эрик Липперт .

ПРИМЕЧАНИЕ: я чувствую, что аналогичная вещь должна работать для произвольных деревьев,Есть комментарии?

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, то естькорневой узел) левого потомка, второе поле - это правый потомок, а третье поле - это значение.Дерево упорядочено по алфавиту.Это кажется простым, но на самом деле может быть трудным сделать.

Подобный подход поместил бы ключ в каждую запись, а не полагался на позицию.Этот метод мог бы использовать исходные указатели в качестве ключей, а код для чтения должен был бы создать таблицу перевода / символов для переключения между ключами и новыми указателями.

Еще один способ сделать это с помощью lisp-esque tree: (foo (cat () (dog () ()) (zebra () ()))

Отформатировано для удобного просмотра:

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

Это может быть легко сгенерированос помощью простого обхода в порядке. Он также может быть прочитан с помощью очень простого рекурсивного приличного синтаксического анализатора. Вы также можете изменить это, чтобы уменьшить размеры листовых узлов в сериализованном формате, пропустив nil или () или что-либо другоевыбрал для указателей NULL.

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

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

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

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

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

Answer 5

Подход 1: Мы можем пройти через дерево дважды:

1. Первый раз, чтобы получить InOrder Обход
2. Второй тайм, чтобы получить 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