Speichern möchten binäre Struktur auf der Festplatte für das "20-Fragen" - Spiel

Kurz gesagt, ich würde es gerne lernen/entwickeln, die eine elegante Methode zum speichern eines binären Baums auf der Festplatte (eine Allgemeine Struktur, die nicht unbedingt eine BST). Hier ist die Beschreibung meines Problems:

Ich bin Implementierung ein Spiel der "20-Fragen". Ich habe geschrieben ein binärer Baum, dessen innere Knoten sind Fragen und lässt Antworten gibt. Das linke Kind eines Knotens ist der Weg, dem Sie Folgen würden, wenn jemand antwortete "ja" zu Ihrer aktuellen Frage, während das Rechte Kind ist ein "Nein" zu beantworten. Hinweis: dies ist nicht eine binäre Suche Baum, nur ein binärer Baum, dessen linke Kind ist "ja" und rechts "Nein".

Das Programm fügt einen Knoten zu einem Baum, wenn er auf ein Blatt, das null ist, indem der Benutzer gefragt wird, unterscheiden Sie Ihre Antwort von der einen war der computer zu denken.

Dies ist ordentlich, weil der Baum baut sich auf wie der Benutzer spielt. Was nicht ordentlich ist, dass ich nicht haben eine gute Möglichkeit zum speichern des Baumes auf der Festplatte.

Habe ich mir Gedanken über die Rettung der Baum als array-Darstellung (für Knoten i, linke Kind ist 2i+1 und 2i+2, (i-1)/2 für die Eltern), aber es ist nicht sauber, und ich am Ende mit sehr viel Platz verschwendet.

Ideen für eine elegante Lösung zum speichern eines sparse binary tree auf der Festplatte?

InformationsquelleAutor Rich | 2008-12-03
  1. 9

    Können Sie es speichern, rekursiv:

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

    Entwickeln Ihre eigenen weniger texty Ausgabe-format. Ich bin sicher, ich brauche nicht zu beschreiben die Methode zum Lesen der Ausgabe.

    Dies ist depth-first-traversal. Zuerst der Breite funktioniert auch.

    • Ja, natürlich! Vielen Dank, das ist schön...
    • Genauer gesagt, dies ist eine preorder-Traversierung. [Knuth, vol. 1], was sonst?
    InformationsquelleAutor slim
  2. 9

    Ich würde eine Level-order-traversal. Das heißt, Sie sind im Grunde tun, eine Breite-zuerst-Suche Algorithmus.

    Haben Sie:

    1. Erstellen Sie eine qeueue mit dem root-element eingefügt
    2. Entfernen Sie ein element aus der queue, nenne es E
    3. Fügen Sie die linken und rechten Kinder von E in die Warteschlange. Wenn es kein Links oder rechts, einfach eine null-node Darstellung.
    4. schreiben, der Knoten E auf der Festplatte.
    5. Wiederholen Sie das Verfahren ab Schritt 2.

    Speichern möchten binäre Struktur auf der Festplatte für das

    Level-order-traversal Reihenfolge: F, B, G, A, D, I, C, E, H

    Was Sie speichern auf dem Datenträger: F, B, G, A, D, NullNode, ich, NullNode, NullNode, C, E, H, NullNode

    Laden von der Festplatte ist noch einfacher. Lesen Sie einfach von Links nach rechts die Knoten, die Sie auf der Festplatte gespeichert. Dies wird Ihnen jeder Ebene der linken und rechten Knoten. I. e. der Baum füllt sich von oben nach unten von Links nach rechts.

    Schritt 1 Lesen in:

    F

    Schritt 2 Lesen in:

      F 
B

    Schritt 3 Lesen in:

      F 
 B  G

    Schritt 4 Lesen in:

       F 
 B  G
A

    Und so weiter ...

    Hinweis: wenn Sie einen NULL-Knoten-Darstellung, die Sie nicht mehr benötigen, um die Liste seiner Kinder auf die Festplatte. Beim laden zurück, werden Sie wissen, zu überspringen, um den nächsten Knoten. Also für sehr Tiefe Bäume, diese Lösung wird immer noch effizient sein.

    • Sie können auch trimmen alle NullNodes vom Ende, denke ich. Für einige Grund Sie getrimmt alle aber 1.
    • Wenn Sie laden Sie es wieder von der Platte, wie Sie stecken die Kinder zurück zu einem übergeordneten Knoten?
    • Das laden ist tatsächlich NICHT einfach. Wir müssen noch eine Warteschlange zu erinnern, die Obere Ebene der Eltern...... und dann stecken Sie Ihre jeweiligen Kinder.
    InformationsquelleAutor Brian R. Bondy
  3. 1

    Einen einfachen Weg, dies zu erreichen, Durchlaufen den Baum Ausgabe jedes element, wie Sie das tun. Dann laden Sie den Baum wieder, einfach Durchlaufen Ihre Liste einfügen, die jedes element wieder in den Baum. Wenn Sie Ihren Baum nicht selbst balancing, möchten Sie vielleicht die Reihenfolge der Liste in einer Weise, dass der endgültige Baum ist einigermaßen ausgewogen.

    • Einfachsten Lösungen sind meist die besten 🙂 auch die Serialisierung helfen könnte
    • Gute Idee, außer es wird nicht funktionieren, wenn der Baum ist nicht eine binäre Suchbaum (wie, wissen Sie, wo legen Sie das nächste element?)
    • Wenn Sie bauen den Baum, Sie wissen, wo Sie einfügen möchten, so Lesen Sie es wieder an ist das gleiche. Ich ziemlich viel vorgeschlagen, die gleiche Sache, wie schlank die Antwort, aber ohne den code.
    • Ich sehe, wenn es Informationen darüber, wo Sie jede Ebene endete, Sie würde es wissen. Ihr Kommentar zu balancing-es warf mich ab und machte mich denken, dass Sie reden BST einfügen.
    • Gut, wenn es ist ein BST, dann Lesen Sie in welcher Reihenfolge Sie Durchlaufen wird wahrscheinlich produzieren ein unausgeglichener Baum, das ist der Grund, warum ich das erwähnt. Die Frage erwähnt, ein "binärer Baum", so nahm ich an, dass balancing ein Problem sein kann. Wie haben Sie das geschafft am Ende? Ich wäre daran interessiert zu wissen.
    InformationsquelleAutor
  4. 1

    Nicht sicher, es ist elegant, aber es ist einfach und erklärbar:
    Eine eindeutige ID zuweisen, um jeden Knoten, ob stengel oder Blätter. Ein einfaches zählen integer tun.

    Beim speichern auf der Festplatte, Durchlaufen den Baum und speichert jede Knoten-ID", "ja" link-ID "kein" link-ID und den text der Frage oder Antwort. Für null-links, verwenden Sie null als null-Wert. Sie können entweder fügen Sie eine Flagge, um anzuzeigen, ob Frage oder Antwort, oder einfacher, zu überprüfen, ob beide links sind null. Sie sollten etwas wie diese:

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

    Beachten Sie, dass wenn Sie verwenden die sequentielle Ganzzahlen Ansatz, speichern die Knoten-ID kann redundant sein, wie hier gezeigt. Sie konnte einfach legen Sie Sie in der Reihenfolge von ID.

    Zur Wiederherstellung von Festplatte, eine Zeile Lesen, dann fügen Sie es an den Baum. Sie werden wahrscheinlich brauchen eine Tabelle oder ein array zu halten, weiterleiten-referenzierten Knoten, z.B. bei der Verarbeitung von Knoten 1, halten Sie track 2 und 3, bis Sie diese Werte.

    InformationsquelleAutor Frank Ames
  5. 0

    Die beliebige einfache Art und Weise ist nur eine grundlegende format, das verwendet werden kann, zum darstellen von jeder Grafik. 

    <parent>,<relation>,<child>

    Ie: 

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

    Gibt es nicht viel Redundanz hier, und die Formate, die meist von Menschen lesbar, die nur die Duplizierung der Daten ist, dass es eine Kopie von einem Elternteil für jedes direkte Kind es hat.

    Die einzige Sache, die Sie wirklich achten müssen ist, dass Sie nicht versehentlich erzeugen einen Zyklus 😉

    Es sei denn, das, was Sie wollen.

    Das problem hier ist der Wiederaufbau der
    Baum danach. Wenn ich die "macht
    es haben Flügel" - Objekt nach dem Lesen der
    erste Zeile, ich muss irgendwie lokalisieren
    wenn ich später die Begegnung mit der Zeile
    Lesen "hat es
    Flügel","ja","Hat es einen schnabel?"

    Dies ist der Grund, warum ich traditionell nur verwenden graph-Strukturen im Speicher für so ein Ding mit Zeigern geht überall. 

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

    Dann das "Kind/Eltern" - Konnektivität ist lediglich Metadaten.

    • Das problem hier ist der Wiederaufbau der Baum danach. Wenn ich die "nicht haben Flügel" - Objekt nach dem Lesen der ersten Zeile habe ich irgendwie finden, wenn ich später die Begegnung mit der Zeile Lesen "hat es Flügel","ja","Hat es einen schnabel?"
    InformationsquelleAutor Kent Fredric
  6. 0

    In java, wenn Sie waren, um eine Klasse serializeable Sie können schreiben Sie einfach die Objekt-Klasse-disc und Lesen Sie wieder mit input/output-streams.

    InformationsquelleAutor Aaron
  7. 0

    Ich würde lagern Sie den Baum wie diesem:

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

    wo die Kind Knoten werden nur rekursive Instanzen der oben genannten. Die bits in [] sind optional, und die vier Kennungen sind nur Konstanten/enum-Werte.

    InformationsquelleAutor Skizz
  8. 0

    Hier ist der C++ - code mit 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() Sie tun können:

    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
 */

    Die DFS ist einfacher zu verstehen.

    *********************************************************************************

    Aber wir können level-scan BFS mit Hilfe des queue -

    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() Sie tun können:

    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
 */
    InformationsquelleAutor Peter Lee
Schreibe einen Kommentar