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

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

У тебя есть:

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

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

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

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

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

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

 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("}");
        }
  }

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

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

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

<parent>,<relation>,<child>

Т.е.:

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

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

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

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

The problem here is rebuilding the tree afterwards. If I create the "does it have wings" object upon reading the first line, I have to somehow locate it when I later encounter the line reading "does it have wings","yes","Has it got a beak?"

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

[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 ]

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

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

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

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, пока вы не заполните эти значения.

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

Вот код 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
 */