Сериализация и десериализация двоичного дерева

01.01.2020Деревья

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

Ниже приведены несколько более простых версий проблемы:

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

Если данное Бинарное Дерево — Полное Дерево?
Двоичное дерево завершено, если все уровни полностью заполнены, за исключением, возможно, последнего уровня, и все узлы последнего уровня находятся как можно левее (двоичные кучи являются полным двоичным деревом). Для полного двоичного дерева обход уровня порядка достаточен для хранения дерева. Мы знаем, что первый узел является корневым, следующие два узла являются узлами следующего уровня, следующие четыре узла являются узлами 2-го уровня и так далее.

Если данное Бинарное Дерево — Полное Дерево?
Полный двоичный файл — это двоичное дерево, в котором каждый узел имеет 0 или 2 дочерних элемента. Такие деревья легко сериализовать, так как у каждого внутреннего узла есть 2 дочерних элемента. Мы можем просто сохранить обход предварительного заказа и сохранить бит для каждого узла, чтобы указать, является ли этот узел внутренним узлом или конечным узлом.

Как хранить общее бинарное дерево?
Простое решение — хранить как обходы Inorder, так и Preorder. Для этого решения требуется пространство, в два раза превышающее размер двоичного дерева.
Мы можем сэкономить место, сохранив обход Preorder и маркер для указателей NULL.

Let the marker for NULL pointers be '-1'
Input:
     12
    /
  13
Output: 12 13 -1 -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

Десериализация может быть сделана простым чтением данных из файла по одному.

Ниже приводится реализация вышеуказанной идеи на C ++.

// Программа на C ++ для демонстрации сериализации и десериализации
// Двоичное дерево
#include <stdio.h>
#define MARKER -1

/ * Узел двоичного дерева имеет ключ, указатель на левого и правого потомков * /

struct Node

{

int key;

struct Node* left, *right;

};

/ * Вспомогательная функция, которая выделяет новый узел с

данный ключ и NULL левый и правый указатели. * /

Node* newNode(int key)

{

Node* temp = new Node;

temp->key = key;

temp->left = temp->right = NULL;

return (temp);

}

// Эта функция сохраняет дерево в файле, указанном fp

void serialize(Node *root, FILE *fp)

{

// Если текущий узел НЕДЕЙСТВИТЕЛЕН, сохраняем маркер

if (root == NULL)

{

fprintf(fp, "%d ", MARKER);

return;

}

// Иначе, сохранить текущий узел и повторить для его потомков

fprintf(fp, "%d ", root->key);

serialize(root->left, fp);

serialize(root->right, fp);

}

// Эта функция создает дерево из файла, на который указывает 'fp'

void deSerialize(Node *&root, FILE *fp)

{

// Чтение следующего элемента из файла. Если нет больше предметов или рядом

// элемент маркерный, затем возврат

int val;

if ( !fscanf(fp, "%d ", &val) || val == MARKER)

return;

// Иначе создать узел с этим элементом и повторить для детей

root = newNode(val);

deSerialize(root->left, fp);

deSerialize(root->right, fp);

}

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

void inorder(Node *root)

{

if (root)

{

inorder(root->left);

printf("%d ", root->key);

inorder(root->right);

}

/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

// Построим дерево, показанное на рисунке выше

struct Node *root = newNode(20);

root->left = newNode(8);

root->right = newNode(22);

root->left->left = newNode(4);

root->left->right = newNode(12);

root->left->right->left = newNode(10);

root->left->right->right = newNode(14);

// Давайте откроем файл и сериализуем дерево в файл

FILE *fp = fopen("tree.txt", "w");

if (fp == NULL)

{

puts("Could not open file");

return 0;

}

serialize(root, fp);

fclose(fp);

// Давайте десериализуем сохраненное дерево в root1

Node *root1 = NULL;

fp = fopen("tree.txt", "r");

deSerialize(root1, fp);

printf("Inorder Traversal of the tree constructed from file:\n");

inorder(root1);

return 0;

}

Выход:

Inorder Traversal of the tree constructed from file:
4 8 10 12 14 20 22

Сколько дополнительного места требуется в вышеуказанном решении?
Если имеется n ключей, то для вышеприведенного решения требуются маркеры n + 1, что может быть лучше простого решения (двойное хранение ключей) в ситуациях, когда ключи большие или ключи имеют большие элементы данных, связанные с ними.

Можем ли мы оптимизировать это дальше?
Вышеуказанное решение может быть оптимизировано многими способами. Если мы поближе рассмотрим выше сериализованные деревья, мы можем заметить, что для всех листовых узлов требуются два маркера. Одна простая оптимизация заключается в сохранении отдельного бита для каждого узла, чтобы указать, что узел является внутренним или внешним. Таким образом, нам не нужно хранить два маркера с каждым узлом листа, так как листья могут быть идентифицированы дополнительным битом. Нам все еще нужен маркер для внутренних узлов с одним потомком. Например, на следующей диаграмме «используется для указания внутреннего бита набора узлов, а« / »используется в качестве маркера NULL. Диаграмма взята отсюда .

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

Как сериализовать n-арное дерево?
В n-арном дереве нет обозначенного левого или правого потомка. Мы можем хранить маркер «конец детей» с каждым узлом. Следующая диаграмма показывает сериализацию, где ')' используется как маркер конца дочернего элемента. Скоро мы рассмотрим реализацию n-арного дерева. Диаграмма взята отсюда .

Ссылки:
http://www.cs.usfca.edu/~brooks/S04classes/cs245/lectures/lecture11.pdf

Эта статья предоставлена Шивамом Гуптой. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сериализация и десериализация двоичного дерева

0.00 (0%) 0 votes