urz gesagt, ich möchte eine elegante Methode zum Speichern eines Binärbaums auf der Festplatte erlernen / entwickeln (ein allgemeiner Baum, nicht unbedingt ein BST). Hier ist die Beschreibung meines Problems:

Ich implementiere ein Spiel mit "20 Fragen". Ich habe einen binären Baum geschrieben, dessen interne Knoten Fragen und Blätter Antworten sind. Das linke Kind eines Knotens ist der Pfad, dem Sie folgen würden, wenn jemand Ihre aktuelle Frage mit "Ja" beantwortet hätte, während das rechte Kind eine "Nein" -Antwort ist. Beachten Sie, dass dies kein binäres @ isSuch tree, nur ein binärer Baum, dessen linkes Kind "yes" und dessen rechtes "no" ist.

Das Programm fügt einem Baum einen Knoten hinzu, wenn es auf ein Blatt stößt, das null ist, indem es den Benutzer auffordert, seine Antwort von der zu unterscheiden, an die der Computer gedacht hat.

Dies ist ordentlich, weil der Baum sich beim Spielen des Benutzers selbst aufbaut. Was nicht gerade gut ist, ist, dass ich den Baum nicht gut auf der Festplatte speichern kann.

Ich habe darüber nachgedacht, den Baum als Array-Darstellung zu speichern (für Knoten i ist linkes Kind 2i + 1 und 2i + 2 rechts (i-1) / 2 für Eltern), aber es ist nicht sauber und ich lande mit viel Platzverschwendung.

Haben Sie Ideen für eine elegante Lösung zum Speichern eines spärlichen Binärbaums auf der Festplatte?