Eric Lippert - Generieren aller binären Bäume

Ursprünglicher Autor: Eric Lippert
  • Übersetzung
Ich habe einen kleinen Algorithmus beschrieben, der kleine Operationen an Binärbäumen ausführte. Ich wollte es testen. Ich habe mehrere kleine Tests ausprobiert und sie haben bestanden, aber ich war nicht zufrieden. Ich war mir fast sicher, aber vielleicht könnte eine unverständliche binäre Baumtopologie zu einem Fehler führen. Mir wurde klar, dass es eine endliche Anzahl von Binärbäumen einer bestimmten Größe gibt. Ich beschloss, sie alle auszuprobieren.

Bevor ich anfange, brauche ich einen praktischen binären Baumeintrag. Hier ist die Spitze meines Baumes:
class Node
{
  public Node Left { get; private set; }
  public Node Right { get; private set; }
  public Node(Node left, Node right)
  {
    this.Left = left;
    this.Right = right;
  }
}

* This source code was highlighted with Source Code Highlighter.


Alles ist sehr einfach: der linke Knoten, der rechte Knoten und alles. Bitte beachten Sie, dass ich aus Gründen der Übersichtlichkeit in diesem Artikel Daten, die normalerweise in einem Binärbaum gespeichert sind, von oben entfernt habe. Nehmen wir an, dies sind gewöhnliche Zahlen. Ich werde den Baum als kompakte Zeichenfolge darstellen. Ein leerer Link im Baum wird mit x bezeichnet. Ein nicht leerer Scheitelpunkt in meinem „Baum ohne Werte“ wird angegeben (<linker Nachkomme> <rechter Nachkomme>). Stellen Sie sich einen Baum vor:
  1
 / \
x 2
   / \
  x x

Vertex 2 hat zwei untergeordnete Nullpunkte und wird mit (xx) bezeichnet. Scheitelpunkt 1 hat einen leeren linken Nachkommen, und der rechte Nachkomme ist Scheitelpunkt 2. Daher wird der Baum als (x (xx)) bezeichnet. Was ist der Punkt? Wir können einen kleinen rekursiven Code schreiben, der diese Zeilen erstellt:
public static string BinaryTreeString(Node node)
{
  var sb = new StringBuilder();
  Action f = null;
  f = n =>
  {
    if (n == null)
      sb.Append("x");
    else
    {
      sb.Append("(");
      f(n.Left);
      f(n.Right);
      sb.Append(")");
    }
  };
  f(node);
  return sb.ToString();
}

* This source code was highlighted with Source Code Highlighter.

Wie nummeriere ich alle möglichen Binärbäume einer bestimmten Größe? Wir werden es rekursiv machen.

Es gibt genau einen Baum mit 0 Eckpunkten. Es wird mit x bezeichnet. Dies ist die Basis.

Wählen Sie nun eine Nummer. Zum Beispiel vier. Wir wollen alle Bäume von vier nicht leeren Gipfeln aus nummerieren. Angenommen, wir haben bereits alle Scheitelpunkte von drei, zwei und einem Scheitelpunkt nummeriert. Bezeichnen Sie die Menge der Binärbäume von n Eckpunkten als B (n). Angenommen, wir erstellen alle möglichen Kombinationen von B (x) und B (y), wobei zu berücksichtigen ist, dass B (x) dem linken Nachkommen der Wurzel und B (y) dem rechten Nachkommen der Wurzel entspricht. Ich werde B (x) B (y) aufschreiben. In diesem Datensatz können Bäume mit vier nicht leeren Eckpunkten in vier Sätze unterteilt werden: B (0) B (3), B (1) B (2), B (2) B (1), B (3) (0).

Dies ist recht einfach zu verallgemeinern: Wir können alle Bäume mit k Eckpunkten nummerieren und jedes Mal k Fälle sortieren, in denen wir Probleme kleinerer Größe betrachten. Wunderbare rekursive Lösung. Betrachten Sie den Code:
static IEnumerable AllBinaryTrees(int size)
{
  if (size == 0)
    return new Node[] { null };
  return from i in Enumerable.Range(0, size)
      from left in AllBinaryTrees(i)
      from right in AllBinaryTrees(size - 1 - i)
      select new Node(left, right);
}

* This source code was highlighted with Source Code Highlighter.


Beachten Sie, dass LINQ den Algorithmus seiner Beschreibung ähnlicher macht als ein äquivalentes Programm mit einer großen Anzahl von Schleifen.

Und in der Tat, wenn wir rennen:
foreach (var t in AllBinaryTrees(4))
  Console.WriteLine(BinaryTreeString(t));

* This source code was highlighted with Source Code Highlighter.

Dann erhalten wir alle Bäume von vier nicht leeren Eckpunkten.
(x (x (x (xx))))
(x (x ((xx) x)))
(x ((xx) (xx))
(x ((x (xx)) x))
(x () ((xx) x) x))
((xx) (x (xx)))
((xx) ((xx) x))
((x (xx)) (xx))
(((xx) x) ( xx))
((x (x (xx))) x)
((x ((xx) x)) x)
(((xx) (xx)) x)
(((x (xx)) x) x)
((((xx) x) x) x)

Jetzt habe ich einen Mechanismus, der alle Baumtopologien erstellt, und ich kann meinen Algorithmus testen.

Wie viele solcher Bäume? Es sieht so aus, als ob es ziemlich viele davon geben kann.

Die Anzahl der Binärbäume von n Eckpunkten wird als katalanische Zahl bezeichnet, die viele interessante Eigenschaften aufweist. Die N-te Zahl des Katalanischen wird nach der Formel (2n) berechnet! / (n + 1)! n!, das exponentiell wächst. (Wikipedia bietet einige Beweise dafür, dass dies eine Form der katalanischen Zahl ist.) Die Anzahl der Binärbäume einer bestimmten Größe

0 1
1 1
2 2
4 14
8 1430
12 208012
16 35357670

Daher ist mein Plan, alle Bäume dieser Größe auszuprobieren, nicht sehr gut. Es gibt zu viele Optionen und Sie können nicht alles in kurzer Zeit überprüfen.

Ich verwundere Sie: Nehmen wir an, wir haben Binärbäume vergessen und werden im Moment beliebige Bäume in Betracht ziehen. Ein beliebiger Baum kann 0, 1 oder eine beliebige endliche Anzahl von Kindern haben. Lassen Sie einen nicht leeren beliebigen Baum in Klammern als Liste von Nachkommen schreiben. Somit ist {{} {} {{}}} ein Baum

    1
   / | \
  2 3 4
      |
      5

T.K. Die Eckpunkte 2, 3 und 5 haben keine Nachkommen, sie werden als {} geschrieben. Welcher Sinn? Achten Sie auf die Bestellung. {{}}} {{}}} und {{} {{}} {}} sind verschiedene Bäume mit einer ähnlichen Struktur.

Meine erste Aufgabe: Was für willkürlichere Bäume aus n Eckpunkten oder binäre Bäume aus n Eckpunkten.
Meine zweite Aufgabe: Können Sie einen Mechanismus zur Nummerierung beliebiger Bäume entwickeln?

Jetzt auch beliebt: