Хочу сохранить бинарное дерево на диск для игры «20 вопросов»
https://stackoverflow.com/questions/337868
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Короче говоря, я хотел бы выучить/разработать элегантный метод, чтобы сохранить бинарное дерево на диск (общее дерево, не обязательно BST). Вот описание моей проблемы:
Я внедряю игру «20 вопросов». Я написал бинарное дерево, внутренние узлы, вопросы, и листья - это ответы. Левый ребенок узла - это путь, которым вы бы следовали, если бы кто -то ответил «да» на ваш текущий вопрос, в то время как правильный ребенок - это ответ «нет». Обратите внимание, что это не бинарный поиск Дерево, просто двоичное дерево, левое ребенка, «да», а правое - «нет».
Программа добавляет узел к дереву, если она встречается с нулевым листом, попросив пользователя отличить ее ответ от того, о котором думал компьютер.
Это аккуратно, потому что дерево нарастает, когда пользователь играет. Что не известно, так это то, что у меня нет хорошего способа спасти дерево на диск.
Я думал о сохранении дерева в качестве представления массива (для узла I левый ребенок 2i+1 и 2i+2 справа, (i-1)/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("}");
}
}
Разработайте свой собственный формат вывода Mestexty. Я уверен, что мне не нужно описывать метод для чтения полученного вывода.
Это первая глубина. Ширина-тоже работает.
Другие советы
Я бы сделал обход на уровне порядка. То есть вы в основном делаете Широкий первый поиск алгоритм.
У вас есть:
- Создайте QEUEUE с корневым элементом, вставленным в него
- Dequeue элемент из очереди, назовите его E
- Добавьте левого и правого детей E в очередь. Если нет влево или вправо, просто поместите нулевое представление узла.
- Напишите узел E на диск.
- Повторите с шага 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
И так далее ...
Примечание. Как только у вас будет новое представление узла, вам больше не нужно перечислить его детей на диск. При загрузке вы узнаете, чтобы пропустить следующий узел. Таким образом, для очень глубоких деревьев это решение все еще будет эффективным.
Простой способ достичь этого - пересечь дерево, выводящее каждый элемент, когда вы это делаете. Затем, чтобы загрузить дерево назад, просто перечислите через свой список, вставив каждый элемент обратно в дерево. Если ваше дерево не сбалансирует, вы можете переупорядочить список таким образом, чтобы последнее дерево было разумно сбалансировано.
Не уверен, что это элегантно, но это просто и объяснимо: назначить уникальный идентификатор каждому узлу, будь то стебель или лист. Простое целое число счетов подойдет.
При сохранении на диск пересекайте дерево, хранение каждого идентификатора узла, идентификатор ссылки «да», идентификатор ссылки без »и текст вопроса или ответа. Для нулевых ссылок используйте ноль в качестве нулевого значения. Вы можете либо добавить флаг, чтобы указать, вопрос ли или ответ, либо проще говоря, проверить, являются ли обе ссылки нуль. Вы должны получить что -то вроде этого:
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, пока вы не сможете заполнить эти значения.
Самый произвольный простой способ - это просто базовый формат, который можно использовать для представления любого графика.
<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 ]
Тогда подключение к «ребенку/родителю» - это просто метаданные.
В Java, если вы должны были сделать класс сериализуемым, вы можете просто написать объект класса для диска и прочитать его обратно, используя потоки ввода/вывода.
Я бы хранил дерево таким образом:
<node identifier>
node data
[<yes child identfier>
yes child]
[<no child identifier>
no child]
<end of node identifier>
где дочерние узлы являются просто рекурсивными случаями вышеупомянутого. Биты в [] являются необязательными, а четыре идентификатора - это просто константы/enum значения.
Вот код C ++ с использованием предварительного заказа 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 легче понять.
*********************************************************************************
Но мы можем использовать уровни сканирования BF, используя очередь
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
*/
