Quer salvar a árvore binária no disco para o jogo "20 perguntas"
https://stackoverflow.com/questions/337868
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Em suma, gostaria de aprender/desenvolver um método elegante para salvar uma árvore binária em disco (uma árvore geral, não necessariamente um BST). Aqui está a descrição do meu problema:
Estou implementando um jogo de "20 perguntas". Eu escrevi uma árvore binária cujos nós internos são perguntas e folhas são respostas. O filho esquerdo de um nó é o caminho que você seguiria se alguém respondesse "sim" à sua pergunta atual, enquanto a criança certa é uma resposta "não". Observe que isso não é um binário procurar Árvore, apenas uma árvore binária cuja criança esquerda é "sim" e a direita é "não".
O programa adiciona um nó a uma árvore se encontrar uma folha que seja nula, pedindo ao usuário que distingue sua resposta daquele em que o computador estava pensando.
Isso é legal, porque a árvore se constrói à medida que o usuário toca. O que não é legal é que eu não tenho uma boa maneira de salvar a árvore no disco.
Eu pensei em salvar a árvore como uma representação de matriz (para o nó I, a criança esquerda é 2i+1 e 2i+2 à direita, (i-1)/2 para pai), mas não está limpo e acabo com Muito espaço desperdiçado.
Alguma idéia de uma solução elegante para salvar uma árvore binária esparsa em disco?
Solução
Você pode armazená -lo recursivamente:
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("}");
}
}
Devise seu próprio formato de saída menos Texty. Tenho certeza de que não preciso descrever o método para ler a saída resultante.
Esta é a primeira travessia de profundidade. A largura também funciona.
Outras dicas
Eu faria uma travessia de ordem de nível. Isto é, você está basicamente fazendo um Pesquisa pela primeira vez algoritmo.
Você tem:
- Crie um qeeUuue com o elemento raiz inserido nele
- Dequeue um elemento da fila, chame de e
- Adicione os filhos esquerda e direita de E na fila. Se não houver à esquerda ou à direita, basta colocar uma representação nula de nós.
- Escreva o nó E no disco.
- Repita da etapa 2.
Sequência de travessia de ordem de ordem: F, B, G, A, D, I, C, E, H
O que você armazenará no disco: f, b, g, a, d, nullnode, i, nullnode, nullnode, c, e, h, nullnode
Carregá -lo de volta do disco é ainda mais fácil. Basta ler da esquerda para a direita os nós que você armazenou no disco. Isso fornecerá os nós esquerdo e direito de cada nível. Ou seja, a árvore preencherá de cima para baixo da esquerda para a direita.
Etapa 1 lendo em:
F
Etapa 2 Leitura em:
F
B
Etapa 3 lendo em:
F
B G
Etapa 4 Leitura em:
F
B G
A
E assim por diante ...
NOTA: Depois de ter uma representação de nó nulo, você não precisa mais listar seus filhos no disco. Ao carregar de volta, você saberá pular para o próximo nó. Portanto, para árvores muito profundas, essa solução ainda será eficiente.
Uma maneira simples de fazer isso é atravessar a árvore que emitem cada elemento ao fazê -lo. Em seguida, para carregar a árvore de volta, basta iterar na sua lista, inserindo cada elemento de volta na árvore. Se a sua árvore não for auto -equilíbrio, convém reordenar a lista de tal maneira que a árvore final seja razoavelmente equilibrada.
Não tenho certeza se é elegante, mas é simples e explicável: atribua um ID exclusivo a cada nó, seja caule ou folha. Um número inteiro simples de contagem serve.
Ao economizar no disco, atravesse a árvore, armazenando cada ID do nó, "sim" ID do link, "não" ID do link e o texto da pergunta ou resposta. Para links nulos, use zero como valor nulo. Você pode adicionar um sinalizador para indicar se a pergunta ou resposta ou, mais simplesmente, verifique se os dois links são nulos. Você deve conseguir algo assim:
1,2,3,"Does it have wings?"
2,0,0,"a bird"
3,4,0,"Does it purr?"
4,0,0,"a cat"
Observe que, se você usar a abordagem de números inteiros seqüenciais, salvar o ID do nó pode ser redundante, como mostrado aqui. Você poderia apenas colocá -los em ordem por id.
Para restaurar do disco, leia uma linha e adicione -a à árvore. Você provavelmente precisará de uma tabela ou matriz para manter nós de referência avançada, por exemplo, ao processar o nó 1, precisará acompanhar 2 e 3 até que possa preencher esses valores.
A maneira simples mais arbitrária é apenas um formato básico que pode ser usado para representar qualquer gráfico.
<parent>,<relation>,<child>
Ou seja:
"Is it Red", "yes", "does it have wings"
"Is it Red", "no" , "does it swim"
Não há Muito de Redundância aqui, e os formatos são mais legíveis humanos, a única duplicação de dados é que deve haver uma cópia de um pai para cada criança direta que possui.
A única coisa que você realmente precisa assistir é que não gera acidentalmente um ciclo;)
A menos que seja isso que você quer.
O problema aqui está reconstruindo a árvore depois. Se eu criar o objeto "Ele tem asas" ao ler a primeira linha, tenho que localizá -lo de alguma forma quando mais tarde encontro a linha de leitura "Ele tem asas", "Sim", "tem um bico?"
É por isso que tradicionalmente uso estruturas de gráficos na memória para tal coisa com dicas indo para qualquer lugar.
[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 ]
Então a conectividade "criança/pai" é apenas metadados.
Em Java, se você fizer uma classe serializável, você pode apenas escrever o objeto de classe para disco e lê -lo novamente usando fluxos de entrada/saída.
Eu armazenaria a árvore assim:
<node identifier>
node data
[<yes child identfier>
yes child]
[<no child identifier>
no child]
<end of node identifier>
onde os nós da criança são apenas instâncias recursivas do exposto. Os bits em [] são opcionais e os quatro identificadores são apenas valores de constantes/enum.
Aqui está o código C ++ usando DFS de pré -encomenda:
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;
}
Dentro main(), você pode fazer:
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
*/
O DFS é mais fácil de entender.
*********************************************************************************
Mas podemos usar BFs de varredura de nível usando uma fila
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;
}
Dentro main(), você pode fazer:
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
*/
