Algorithmus zum Auflisten aller Binärbäume einer bestimmten Höhe

Ich habe versucht, einen Algorithmus zu finden, um alle Binärbäume einer bestimmten Höhe .$h$

Beachten Sie, dass ich nicht versuche, sie zu zählen: Die Anzahl solcher Bäume ist im OEIS ( A001699 ) angegeben.

Alle Algorithmen, die ich sehen konnte, listen alle Binärbäume für eine bestimmte Anzahl von Knoten auf. Eine sehr ineffiziente Methode zur Lösung des Problems würde darin bestehen, alle Bäume mit einer Anzahl von Knoten zwischen und überprüfen. Dies ist jedoch überhaupt nicht großartig.$h+1$$2^{h+1}-1$

Alle Hinweise oder Referenzen wäre sehr dankbar.

Folgen Sie, wie in den Kommentaren angedeutet, einfach der rekursiven Struktur von Binärbäumen.

Wir erstellen eine Funktion listbt(h), die alle Binärbäume mit exakter Höhe auflistet h.

type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
|   listbt h = {
  result = []
  for T in (listbt h-1) {
    for k in (0..h-1) {
      for t in (listbt k) {
         result += Node(T, t)
         result += Node(t, T) if k < h-1 || t != T
      }
    }
  }
  return result
}

Die Korrektheit folgt mit einem elementaren induktiven Beweis h.

Wenn Sie sich die Ergebnisse merken listbt, wird dies so effizient wie möglich sein. Die schiere Anzahl der Bäume und damit die Anzahl der Schecks t != Tdominieren.

Beachten Sie, dass Sie die Größe der Ausgabe erheblich reduzieren können , wenn Sie Term Sharing verwenden (dh nur Link tund TIn, Node(t, T)aber nicht kopieren). Dies ist jedoch nur dann sinnvoll, wenn Ihre BTreeImplementierung unveränderlich ist.

Mein erster Gedanke war, dass dies nur Bäume betrifft, die aus Pfaden der Länge h gebaut wurden, die isomorph zu h-Bit-Ganzzahlen sind, aber dies ist nur eine Teilmenge dessen, was benötigt wird. Beginnen Sie jedoch damit, dass Sie jeden nicht vollständigen Zwischenknoten mit Bäumen füllen müssen, die nicht bis zur Blattebene reichen.

Das heißt: Zählen Sie die nicht leeren Mengen von h-Bit-Ganzzahlen auf und konvertieren Sie sie in Bäume. Fügen Sie dann für jeden Baum T für jeden nicht vollständigen Nicht-Blatt-Knoten N (dh nur ein Kind, da er sich per Definition bereits auf einem Pfad zu mindestens einem Blatt befindet) alle möglichen Teilbäume hinzu, die die Blattebene nicht erreichen (Höhe <Höhe (N) -1, einschließlich des leeren Baums). Geben Sie dann das kartesische Produkt über alle N in T aus.$2^{2^h}-1$

Meine Behauptung ist, dass dies alle Bäume erzeugt und nicht zweimal erzeugt, da die Bedingung, dass das Blatt nicht erreicht wird, es unmöglich macht, mit einem T zu beginnen und es in ein anderes T 'mit einem anderen Blatt der Tiefe h umzuwandeln.