Рубрики

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

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

Этот пост в основном является продолжением нижнего поста.
Сериализация и десериализация двоичного дерева

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

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

// Программа на C ++ сериализует и десериализует N-арное дерево
#include<cstdio>
#define MARKER ')'
#define N 5

using namespace std;

  
// Узел N-арного дерева

struct Node {

   char key;

   Node *child[N];  // Массив указателей для N детей

};

  
// Вспомогательная функция для создания нового узла N-арного дерева

Node *newNode(char key)

{

    Node *temp = new Node;

    temp->key = key;

    for (int i = 0; i < N; i++)

        temp->child[i] = NULL;

    return temp;

}

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

void serialize(Node *root, FILE *fp)

{

    // Базовый вариант

    if (root == NULL) return;

  

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

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

    for (int i = 0; i < N && root->child[i]; i++)

         serialize(root->child[i],  fp);

  

    // Хранить маркер в конце детей

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

}

  
// Эта функция создает N-арное дерево из файла, на который указывает 'fp'.
// Этот функционер возвращает 0, чтобы указать, что следующий элемент является допустимым
// ключ дерева. Остальное возвращает 0

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

{

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

    // элемент является маркером, затем возвращается 1, чтобы указать то же самое

    char val;

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

       return 1;

  

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

    root = newNode(val);

    for (int i = 0; i < N; i++)

      if (deSerialize(root->child[i], fp))

         break;

  

    // Наконец возвращаем 0 для успешного завершения

    return 0;

}

  
// Вспомогательная функция для создания фиктивного дерева, показанного на диаграмме выше
Node *createDummyTree()
{

    Node *root = newNode('A');

    root->child[0] = newNode('B');

    root->child[1] = newNode('C');

    root->child[2] = newNode('D');

    root->child[0]->child[0] = newNode('E');

    root->child[0]->child[1] = newNode('F');

    root->child[2]->child[0] = newNode('G');

    root->child[2]->child[1] = newNode('H');

    root->child[2]->child[2] = newNode('I');

    root->child[2]->child[3] = newNode('J');

    root->child[0]->child[1]->child[0] = newNode('K');

    return root;

}

  
// Функция utlity для обхода построенного N-арного дерева

void traverse(Node *root)

{

    if (root)

    {

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

        for (int i = 0; i < N; i++)

            traverse(root->child[i]);

    }

}

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

int main()

{

    // Давайте создадим N-арное дерево, показанное на диаграмме выше

    Node *root = createDummyTree();

  

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

    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("Constructed N-Ary Tree from file is \n");

    traverse(root1);

  

    return 0;

}

Выход:

Constructed N-Ary Tree from file is
A B E F K C D G H I J

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

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

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

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

0.00 (0%) 0 votes