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

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

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

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

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

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

У вас есть:

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

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

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

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

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

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

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

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

<parent>,<relation>,<child>

Ie:

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

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

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

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

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

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

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