Desideri salvare l'albero binario su disco per & # 8220; 20 domande & # 8221; gioco
https://stackoverflow.com/questions/337868
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
In breve, vorrei imparare / sviluppare un metodo elegante per salvare un albero binario su disco (un albero generale, non necessariamente un BST). Ecco la descrizione del mio problema:
Sto implementando un gioco di "20 domande". Ho scritto un albero binario i cui nodi interni sono domande e le foglie sono risposte. Il figlio sinistro di un nodo è il percorso che seguiresti se qualcuno rispondesse "sì" alla tua domanda attuale, mentre il bambino giusto è un "no" risposta. Nota che questo non è un albero cerca binario, ma solo un albero binario il cui figlio sinistro è " si " e il diritto è "no".
Il programma aggiunge un nodo a un albero se incontra una foglia che è nulla chiedendo all'utente di distinguere la sua risposta da quella a cui stava pensando il computer.
Questo è pulito, perché l'albero si accumula mentre l'utente gioca. Ciò che non è pulito è che non ho un buon modo per salvare l'albero su disco.
Ho pensato di salvare l'albero come rappresentazione di array (per il nodo i, il figlio sinistro è 2i + 1 e 2i + 2 a destra, (i-1) / 2 per il genitore), ma non è pulito e io finiscono con un sacco di spazio sprecato.
Qualche idea per una soluzione elegante per salvare un albero binario sparso su disco?
Soluzione
Puoi memorizzarlo in modo ricorsivo:
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("}");
}
}
Elabora il tuo formato di output meno texty. Sono sicuro di non aver bisogno di descrivere il metodo per leggere l'output risultante.
Questo è l'attraversamento in profondità. Anche il primo funziona.
Altri suggerimenti
Farei un attraversamento di ordine di livello. Questo significa che stai fondamentalmente facendo un Ricerca per primo . >
Hai:
- Crea una qeueue con l'elemento root inserito in essa
- Dequeue un elemento dalla coda, chiamalo E
- Aggiungi i figli sinistro e destro di E nella coda. Se non c'è sinistra o destra, basta inserire una rappresentazione di nodo null.
- scrivi il nodo E sul disco.
- Ripeti dal passaggio 2.
Sequenza di attraversamento dell'ordine dei livelli: F, B, G, A, D, I, C, E, H
Cosa memorizzerai sul disco: F, B, G, A, D, NullNode, I, NullNode, NullNode, C, E, H, NullNode
Il caricamento di nuovo dal disco è ancora più semplice. Basta leggere da sinistra a destra i nodi memorizzati sul disco. Questo ti darà i nodi sinistro e destro di ogni livello. Cioè l'albero si riempirà dall'alto verso il basso da sinistra a destra.
Passaggio 1: lettura in
F
Passaggio 2: lettura in
F
B
Passaggio 3: lettura in
F
B G
Passaggio 4: lettura in
F
B G
A
E così via ...
Nota: una volta che si dispone di una rappresentazione del nodo NULL, non è più necessario elencare i relativi figli su disco. Durante il caricamento, saprai di passare al nodo successivo. Quindi, per alberi molto profondi, questa soluzione sarà comunque efficiente.
Un modo semplice per raggiungere questo obiettivo è attraversare l'albero producendo ogni elemento mentre lo fai. Quindi per caricare nuovamente l'albero, è sufficiente scorrere l'elenco, inserendo nuovamente ciascun elemento nell'albero. Se il tuo albero non si autobilancia, potresti voler riordinare l'elenco in modo tale che l'albero finale sia ragionevolmente bilanciato.
Non sono sicuro che sia elegante, ma è semplice e spiegabile: Assegnare un ID univoco a ciascun nodo, sia esso radice o foglia. Farà un semplice numero intero.
Quando si salva su disco, attraversare l'albero, memorizzando ciascun ID nodo, " yes " ID collegamento, " no " ID collegamento e il testo della domanda o risposta. Per i collegamenti null, utilizzare zero come valore null. È possibile aggiungere un flag per indicare se la domanda o la risposta o, più semplicemente, verificare se entrambi i collegamenti sono nulli. Dovresti ottenere qualcosa del genere:
1,2,3,"Does it have wings?"
2,0,0,"a bird"
3,4,0,"Does it purr?"
4,0,0,"a cat"
Nota che se usi l'approccio degli interi sequenziali, il salvataggio dell'ID del nodo potrebbe essere ridondante, come mostrato qui. Potresti semplicemente metterli in ordine per ID.
Per ripristinare dal disco, leggere una riga, quindi aggiungerla all'albero. Probabilmente avrai bisogno di una tabella o di un array per contenere nodi con riferimento in avanti, ad es. durante l'elaborazione del nodo 1, è necessario tenere traccia di 2 e 3 fino a quando non è possibile inserire tali valori.
Il modo più arbitrario semplice è solo un formato di base che può essere utilizzato per rappresentare qualsiasi grafico.
<parent>,<relation>,<child>
Vale a dire:
"Is it Red", "yes", "does it have wings"
"Is it Red", "no" , "does it swim"
Non c'è molta ridondanza qui, e i formati sono per lo più leggibili dall'uomo, l'unica duplicazione dei dati è che ci deve essere una copia di un genitore per ogni figlio diretto che ha.
L'unica cosa che devi davvero guardare è che non generi accidentalmente un ciclo;)
A meno che non sia quello che vuoi.
Il problema qui è la ricostruzione di albero in seguito. Se creo " lo fa ha le ali " oggetto dopo aver letto il file prima riga, devo in qualche modo individuare quando in seguito incontro la linea leggendo " ha ali "," "sì", "ha un becco?"
Questo è il motivo per cui tradizionalmente uso solo strutture grafiche in memoria per una cosa del genere con puntatori che vanno ovunque.
[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 ]
Quindi il " figlio / genitore " la connettività è semplicemente metadata.
In java se dovessi rendere una classe serializzabile puoi semplicemente scrivere l'oggetto classe su disco e rileggerlo usando flussi di input / output.
Vorrei memorizzare l'albero in questo modo:
<node identifier>
node data
[<yes child identfier>
yes child]
[<no child identifier>
no child]
<end of node identifier>
dove i nodi figlio sono solo istanze ricorsive di quanto sopra. I bit in [] sono opzionali e i quattro identificatori sono solo costanti / valori di enum.
Ecco il codice C ++ che utilizza 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;
}
In main () , puoi fare:
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
*/
Il DFS è più facile da capire.
*********************************************************************************
Ma possiamo usare la scansione di livello BFS usando una coda
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;
}
In main () , puoi fare:
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
*/
