Хотите сохранить двоичное дерево на диск для игры "20 вопросов"

Question

Короче говоря, я хотел бы изучить / разработать элегантный метод сохранения двоичного дерева на диск (общее дерево, не обязательно BST). Вот описание моей проблемы:

Я реализую игру "20 вопросов". Я написал двоичное дерево, внутренними узлами которого являются вопросы, а листьями - ответы. Левый потомок узла - это путь, по которому вы бы пошли, если бы кто-нибудь ответил «да» на ваш текущий вопрос, а правый потомок - «нет». Обратите внимание, что это не двоичное дерево search , а просто двоичное дерево, левый дочерний элемент которого - "да", а правый - "нет".

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

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

Я думал о сохранении дерева в виде представления массива (для узла i левый потомок равен 2i + 1 и 2i + 2 справа, (i-1) / 2 для родителя), но он не чистый в конечном итоге много потерянного пространства.

Какие-нибудь идеи для элегантного решения для сохранения разреженного двоичного дерева на диск?

Answer 1

Я бы сделал обход уровня порядка. То есть вы в основном выполняете алгоритм поиска в ширину .

У вас есть:

1. Создать очередь с корневым элементом, вставленным в нее
2. Удалить элемент из очереди, назовите его E
3. Добавьте левого и правого потомка E в очередь. Если нет ни левого, ни правого, просто поместите нулевое представление узла.
4. запись узла E на диск.
5. Повторите с шага 2.

Последовательность обхода уровня порядка: F, B, G, A, D, I, C, E, H

Что вы будете хранить на диске: F, B, G, A, D, NullNode, I, NullNode, NullNode, C, E, H, NullNode

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

Шаг 1:

F

Шаг 2, чтение:

  F 
B

Шаг 3:

  F 
 B  G

Шаг 4:

   F 
 B  G
A

И так далее ...

Примечание. Если у вас есть представление узла NULL, вам больше не нужно перечислять его дочерние элементы на диск. При загрузке назад вы будете знать, чтобы перейти к следующему узлу. Так что для очень глубоких деревьев это решение все еще будет эффективным.

Answer 2

Вы можете сохранить его рекурсивно:

 void encodeState(OutputStream out,Node n) {
        if(n==null) {
            out.write("[null]");
        } else {
           out.write("{");
           out.write(n.nodeDetails());
           encodeState(out, n.yesNode());
           encodeState(out, n.noNode());
           out.write("}");
        }
  }

Разработайте свой собственный менее выходной формат texty. Я уверен, что мне не нужно описывать метод, чтобы прочитать полученный результат.

Это обход в глубину. Работает в ширину тоже.

Answer 3

Не уверен, что это элегантно, но это просто и объяснимо: Назначьте уникальный идентификатор каждому узлу, будь то ствол или лист. Подойдет простое целое число.

При сохранении на диск просмотрите дерево, сохранив идентификатор каждого узла, идентификатор ссылки «да», идентификатор ссылки «нет» и текст вопроса или ответа. Для нулевых ссылок используйте ноль в качестве нулевого значения. Вы можете добавить флаг, чтобы указать, является ли вопрос или ответ, или, проще, проверить, являются ли обе ссылки нулевыми. Вы должны получить что-то вроде этого:

1,2,3,"Does it have wings?"
2,0,0,"a bird"
3,4,0,"Does it purr?"
4,0,0,"a cat"

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

Чтобы восстановить с диска, прочитайте строку, затем добавьте ее в дерево. Вероятно, вам понадобится таблица или массив для хранения узлов с прямой ссылкой, например, при обработке узла 1 вам нужно будет отслеживать 2 и 3, пока вы не сможете заполнить эти значения.

Answer 4

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

Answer 5

Вот код C ++, использующий PreOrder DFS:

void SaveBinaryTreeToStream(TreeNode* root, ostringstream& oss)
{
    if (!root)
    {
        oss << '#';
        return;
    }

    oss << root->data;
    SaveBinaryTreeToStream(root->left, oss);
    SaveBinaryTreeToStream(root->right, oss);
}
TreeNode* LoadBinaryTreeFromStream(istringstream& iss)
{
    if (iss.eof())
        return NULL;

    char c;
    if ('#' == (c = iss.get()))
        return NULL;

    TreeNode* root = new TreeNode(c, NULL, NULL);
    root->left  = LoadBinaryTreeFromStream(iss);
    root->right = LoadBinaryTreeFromStream(iss);

    return root;
}

В main() вы можете сделать:

ostringstream oss;
root = MakeCharTree();
PrintVTree(root);
SaveBinaryTreeToStream(root, oss);
ClearTree(root);
cout << oss.str() << endl;
istringstream iss(oss.str());
cout << iss.str() << endl;
root = LoadBinaryTreeFromStream(iss);
PrintVTree(root);
ClearTree(root);

/* Output:
               A

       B               C

   D               E       F

     G           H   I
ABD#G###CEH##I##F##
ABD#G###CEH##I##F##
               A

       B               C

   D               E       F

     G           H   I
 */

DFS легче понять.

*********************************************************************************

Но мы можем использовать BFS для проверки уровня, используя очередь

ostringstream SaveBinaryTreeToStream_BFS(TreeNode* root)
{
    ostringstream oss;

    if (!root)
        return oss;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty())
    {
        TreeNode* tn = q.front(); q.pop();

        if (tn)
        {
            q.push(tn->left);
            q.push(tn->right);
            oss << tn->data;
        }
        else
        {
            oss << '#';
        }
    }

    return oss;
}
TreeNode* LoadBinaryTreeFromStream_BFS(istringstream& iss)
{
    if (iss.eof())
        return NULL;

    TreeNode* root = new TreeNode(iss.get(), NULL, NULL);
    queue<TreeNode*> q; q.push(root); // The parents from upper level
    while (!iss.eof() && !q.empty())
    {
        TreeNode* tn = q.front(); q.pop();

        char c = iss.get();
        if ('#' == c)
            tn->left = NULL;
        else
            q.push(tn->left = new TreeNode(c, NULL, NULL));

        c = iss.get();
        if ('#' == c)
            tn->right = NULL;
        else
            q.push(tn->right = new TreeNode(c, NULL, NULL));
    }

    return root;
}

В main() вы можете сделать:

root = MakeCharTree();
PrintVTree(root);
ostringstream oss = SaveBinaryTreeToStream_BFS(root);
ClearTree(root);
cout << oss.str() << endl;
istringstream iss(oss.str());
cout << iss.str() << endl;
root = LoadBinaryTreeFromStream_BFS(iss);
PrintVTree(root);
ClearTree(root);

/* Output:
               A

       B               C

   D               E       F

     G           H   I
ABCD#EF#GHI########
ABCD#EF#GHI########
               A

       B               C

   D               E       F

     G           H   I
 */

Answer 6

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

Answer 7

Самый простой способ - это просто базовый формат, который можно использовать для представления любого графика.

<parent>,<relation>,<child>

То есть:

"Is it Red", "yes", "does it have wings" 
"Is it Red", "no" , "does it swim"

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

Единственное, что вам действительно нужно наблюдать, это то, что вы случайно не генерируете цикл;)

Если только это не то, что вы хотите.

Проблема здесь в восстановлении дерево потом. Если я создаю "делает у него есть крылья "объект после прочтения Первая строка, я должен как-то найти это когда я позже сталкиваюсь с линией чтение "это имеет крылья "," да "," У него есть клюв? "

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

[0x1111111 "Is It Red"           => [ 'yes' => 0xF752347 , 'no' => 0xFF6F664 ], 
 0xF752347 "does it have wings"  => [ 'yes' => 0xFFFFFFF , 'no' => 0x2222222 ], 
 0xFF6F664 "does it swim"        => [ 'yes' => "I Dont KNOW :( " , ... etc etc ]

Тогда связь «ребенок / родитель» - это просто метаданные.

Answer 8

Я бы сохранил дерево так:

<node identifier>
node data
[<yes child identfier>
  yes child]
[<no child identifier>
  no child]
<end of node identifier>

где дочерние узлы являются просто рекурсивными примерами из вышеперечисленного. Биты в [] являются необязательными, а четыре идентификатора являются просто значениями констант / перечислений.