11

Diese Frage erklärt ziemlich genau, dass sie es können, zeigt jedoch keine Beispiele dafür, dass es zwei verschiedene Bäume mit derselben Vorbestellungsdurchquerung gibt.

Es wird auch erwähnt, dass das Durchlaufen von zwei verschiedenen Bäumen in der Reihenfolge gleich sein kann, obwohl sie strukturell unterschiedlich sind. Gibt es ein Beispiel dafür?

trees binary-trees graph-traversal search-trees Sharan Duggirala
quelle

2

Dies ist eine sehr Einstiegsübung. Was hast du versucht und wo bist du festgefahren?

Raphael

1

Selbst wenn Sie die Nachbestellung haben, können Sie zusätzlich zur Vorbestellung Traversal immer noch verschiedene Bäume erhalten. Warum ist ein Baum bei gegebener Vor- und Nachbestellungsdurchquerung nicht eindeutig möglich? Ein Beispiel für die Reihenfolge finden Sie unter Von der Darstellung in der Reihenfolge zum Binärbaum . Ebenfalls verwandt / dupliziert: Welche Kombinationen von Sequenzierung vor, nach und nach der Reihenfolge sind einzigartig?

Dukeling

28

Baumbeispiele (Bild) :

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3

Dies ist ein Beispiel, das zu Ihrem Szenario passt. Der Wert von Tree A root ist 1, hat ein linkes Kind mit dem Wert 2 und sein linkes Kind hat auch ein linkes Kind mit dem Wert 3.

Der Wert der Wurzel von Baum B ist 1, wobei ein linkes Kind mit dem Wert 2 und ein rechtes Kind mit dem Wert 3 vorhanden sind.

In beiden Fällen beträgt die Vorbestellungsdurchquerung 1-> 2-> 3.

Royashcenazi
quelle

11

Dies ist tatsächlich ein spezieller Fall einer allgemeinen Regel, dass es für jeden Baum einer bestimmten Reihenfolge einen linearen Baum von nur linken (oder nur rechten) Kindern gibt, der dieselbe Reihenfolge hat.

Dancrumb

5

@Dancrumb Dies ist wiederum ein spezieller Fall einer allgemeinen Regel, nach der für jeden Baum mit N Knoten und für jede Baumform (= unbeschrifteter Baum) mit N Knoten eine Möglichkeit besteht, letzteren so zu kennzeichnen, dass er die Durchquerung mit teilt das Vorherige. Dies gilt für jede Durchquerung (Besuch vor / nach / in der Reihenfolge).

Chi

8

$n$ $n$ $1,2,\dots,n$

Dies bedeutet, dass wir die Knoten jeder binären Baumstruktur so benennen können, dass sie dieselbe Vorbestellungssequenz wie die eines anderen gegebenen Baums erzeugt.

Dies funktioniert nicht, wenn wir andere Eigenschaften des Baums annehmen müssen. Wenn der Baum beispielsweise ein binärer Suchbaum sein soll, bei dem alle Schlüssel unterschiedlich sind, bestimmt seine Vorbestellungssequenz den Baum eindeutig.

Hendrik Jan.
quelle

8

Argument zählen

$n$ $n^\text{th}$ $C_n=(2n)!/(n!(n+1)!).$

    o         o         o         o         o
   /         /         / \         \         \
  o         o         o   o         o         o      .
 /           \                     /           \
o             o                   o             o

$n!$

\frac{(2 n)!}{(n + 1)!} = 2 n \cdot (2 n - - 1) \cdot \dots (n + 2) .

$\frac{(2n)!}{(n+1)!} = 2n\cdot(2n-1)\cdot \dots (n+2).$

$n!$ $n$ Knoten. Da haben wir gerade erstere mit multipliziert $n!$ Daher kann keine Durchquerung die vollständige Struktur des Baums für enthalten $C_n>1$ daher $n>1.$ Dies gilt im Allgemeinen für jede Datenstruktur, die mehr als eine Konfiguration mit unbeschrifteten Knoten aufweist. Sie nicht brauchen überhaupt dieses Detail über die katalanische Zahlen zu wissen, wie lange , wie Sie wissen , dass es mindestens zwei unmarkierten Binärbäumen der Größe $n$ .

CR Drost
quelle

1

In Bezug auf Ihre zweite Frage können zwei strukturell unterschiedliche Bäume dieselbe Ordnungsdurchquerung aufweisen. Ein solches Beispiel ist:

     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

Die Durchquerung beider Bäume ist gleich. 2 -> 1 -> 3

Navjot Singh
quelle

Kann die Vorbestellung von zwei verschiedenen Bäumen gleich sein, obwohl sie unterschiedlich sind?

Antworten:

Argument zählen