Mögliche Permutationen der BST-Eingabe

Question

Ich habe eine Zeichenfolge, d. H. "CPHBDZ". Durch das Einfügen (in dieser Reihenfolge) Briefe an eine BST werde ich:

C 
/\ 
B P 
/\ 
    H Z 
/
D 

Wenn wir um die Zeichenfolge ändern „CBPHDZ“ werden wir gleich Baum erhalten. Und ich muss alle Permutationen der Eingabezeichenfolge finden und auflisten, die die gleiche BST bereitstellen. Ich habe herausgefunden, wie man eine Anzahl dieser Permutationen berechnet, aber ich kann keinen Algorithmus finden, der sie tatsächlich findet.

Answer 1

Angenommen, Sie führen keine Rotationen (etc.) durch, um den Baum auszugleichen, können Sie eine Antwort aus der Baumstruktur ableiten: Neue Knoten werden immer als Nachfolger vorhandener Knoten hinzugefügt, also jeder Knoten höher in der Der Baum muss seinen eigenen Nachkommen vorausgehen, kann aber nach Belieben mit seinen "Peers" (alles, was weder der Vater noch der Nachkomme ist) neu arrangiert werden.

Zum Beispiel, da Sie C als Wurzel des Baumes haben, muss C das erste Element gewesen sein, das aus dem Stream gelesen wurde. Da seine Nachkommen B und P sind, musste der nächste Eintrag in der Eingabe einer dieser beiden sein. B hat keine Nachkommen, aber P hat zwei: H und Z, so dass sie nach P gelesen werden mussten, aber in Bezug auf B in beliebiger Reihenfolge sein können. Gleichermaßen kann Z in einer beliebigen Reihenfolge bezüglich H und sein, aber H muss vorausgehen.

Edit: Was die Generierung all dieser Permutationen angeht, wäre ein einfacher (betrügerischer) Weg, Prolog zu verwenden. Im Grunde kodieren Sie diese Abhängigkeiten als "Fakten" und generieren alle Permutationen, die zu diesen Fakten passen. In der Tat (kein Wortspiel beabsichtigt), das ist so ziemlich eine Beschreibung dessen, was Prolog ist/tut.

Tun Sie es auf eigene Faust, würden Sie wahrscheinlich den größten Teil der Arbeit rekursiv tun. Eine gültige Reihenfolge ist eine Wurzel, gefolgt von einer Verschachtelung der gültigen Ordnungen ihrer Nachkommen.

Für das Interleaving würden Sie (zum Beispiel) eine gültige Reihenfolge des linken Unterbaums und eine gültige Reihenfolge des rechten Unterbaums generieren. Ordne sie zu einem Array mit allen Elementen aus dem linken Unterbaum am Anfang und allen aus dem rechten Unterbaum am Ende zusammen. Nehmen wir als Beispiel an, dass der Baum auch einen A (als Nachkomme des B, den Sie anzeigen) enthält. In einer Anordnung, unsere Daten aus unseren Unterbäumen würden wie folgt aussehen:

B A P H Z D 

Dann starten wir aus dem letzten Eintrag im linken Unterbaum, und „zu Fuß“ jeweils über die Anordnung auf den rechten Seite, Erzeugen einer neue Permutation jedes Mal: ​​

B P A H Z D 
P B A H Z D 
B P H A Z D 
P B H A Z D 
P H B A Z D 
[ ... ]  

Für jede gültige Reihenfolge des linken Unterbaumes, müssen Sie alle diese Verschachtelungen mit jedem gültigen Befehl des rechten Unterbaumes tun (und senden es an den Eltern, die das Gleiche tun).

Answer 2

In Python

tree = { 
    'C' : ['B', 'P'], 
    'P' : ['H','Z'], 
    'H' : ['D']} 

def f(tree, ready): 
    if not ready: 
     return [[]] 
    else: 
     rv = [] 
     for r in ready: 
      for rest in f(tree, 
          [n for n in ready if r != n] + tree.get(r, [])): 
       rv.append([r] + rest) 
     return rv 

for o in f(tree, 'C'): 
    print ''.join(o)