Представление двоичного дерева в файле

Question

Какие существуют разные стратегии представления двоичного дерева в файле, чтобы можно было легко воссоздать древовидную структуру? Я использую C.

Answer 1

Сохраняет порядок и порядок обхода дерева в файле. Любое двоичное дерево может быть восстановлено путём обхода по порядку и по порядку [1].

[1] http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Answer 2

Вот наивный способ, предполагая, что у вас есть что-то вроде:

struct bst {
   int val;
   struct bst *left; // NULL when no node
   struct bst *right;
}

Создайте еще одну структуру:

struct bst_serial {
   int val;
   int left; // NULL when no node
   int right;
}

Затем malloc массив bst_serial s размером с ваше дерево:

struct bst_serial *serial_bst = malloc(sizeof(struct bst_serial) * tree_size);

Теперь выполните обход дерева следующим образом (не проверено):

int current_pos = 0;

int convert_node(bst *root) {
    int this_pos = current_pos;
    current_pos++;        

    serial_bst[this_pos].val = root->val;
    if(root->left != NULL) {
       serial_bst[this_pos].left = convert_node(root->left);
    } else {
       serial_bst[this_pos].left = -1;
    } 

    if(root->right != NULL) {    
       serial_bst[this_pos].right = convert_node(root->right);
    } else {
       serial_bst[this_pos].right = -1;
    } 
    return this_pos;
}

Теперь вы можете write() вывести массив на диск. Если вы пишете функции для обхода дерева типа bst_serial, вам даже не нужно десериализовать его - вы можете просто mmap() это сделать. Для дополнительных точек, даже не используйте дерево указателей в первую очередь - создавайте и увеличивайте массив bst_serial, когда вы создаете двоичное дерево. Тогда вашему коду не нужно заботиться о том, имеет ли он дело с деревом с диска или с деревом, которое вы только что создали.

Answer 3

Вам понадобится как минимум 2 обхода дерева, чтобы иметь возможность построить точное дерево. Поскольку из одного данного обхода может быть более одного уникального дерева.

Например, вы можете сохранить обходы и обходы бинарного дерева в вашем текстовом файле и перейти по ссылке ниже, чтобы отработать его при воссоздании дерева.

http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

Answer 4

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

Когда вы читаете файл, пока не получите '#', вставьте значения и спуститесь влево. Если вы получаете «#», поднимайтесь до тех пор, пока нет элементов справа, и спускайтесь вправо. Делать это рекурсивно.