Gegeben eine BST und ihre Wurzel, drucke alle Knotenfolgen, die zum gleichen BST führen.

Question

Gegeben eine BST, finde alle Sequenzen von Knoten beginnend mit der Wurzel, die im Wesentlichen denselben binären Suchbaum ergeben.

ein bst gegeben, sagen

3 
/\ 
1 5 

die Antwort 3,1,5 und 3,5,1 sein sollte.

weiteres Beispiel

 5 
    / \ 
    4  7 
/ /\ 
    1  6 10 

die Ausgänge werden

5,4,1,7,6,10

5,4,7,6,10,1

5,7,6,10,4,1

usw.

Die Invariante hier ist jedoch, dass der Index des Elternteils immer kleiner als seine Kinder sein muss. Ich habe Schwierigkeiten, es umzusetzen.

Answer 1

Ich nehme an, Sie wollen eine Liste aller Sequenzen, die die gleiche BST erzeugen.
In dieser Antwort werden wir Teilen und Conquer verwenden.
Wir werden eine Funktion findAllSequences(Node *ptr) erstellen, die einen Knotenzeiger als Eingabe verwendet und alle eindeutigen Sequenzen zurückgibt, die den Teilbaum erzeugen, der von ptr hängt. Diese Funktion wird einen Vektor des Vektors von int zurückgeben, d. H. vector<vector<int>>, der alle Sequenzen enthält.

Die Leitgedanke für Sequenz zu erzeugen ist, dass Wurzel vor allem seine Kinder kommen müssen.

Algorithm:

Basisfall 1:
Wenn ptrNULL, dann wird ein Vektor mit einer leeren Sequenz zurück.

if (ptr == NULL) { 
    vector<int> seq; 
    vector<vector<int> > v; 
    v.push_back(seq); 
    return v; 
} 

Basis-Szenario 2:
Wenn ptr ein leaf node ist, kehrt dann einen Vektor mit einer einzigen Sequenz. Sein Trivial, dass diese Sequenz nur ein einzelnes Element enthält, d. H. Den Wert dieses Knotens.

if (ptr -> left == NULL && ptr -> right == NULL) { 
    vector<int> seq; 
    seq.push_back(ptr -> val); 
    vector<vector<int> > v; 
    v.push_back(seq); 
    return v; 
} 

Teilen Teil (dieser Teil ist sehr einfach.)
Wir gehen davon aus, dass wir eine Funktion haben, die dieses Problem lösen können, und damit lösen wir es für linke Unterbaum und rechten Unterbaum.

vector<vector<int> > leftSeq = findAllSeq(ptr -> left); 
vector<vector<int> > rightSeq = findAllSeq(ptr -> right); 

Zusammenführen der beiden Lösungen. (Der springende Punkt ist in diesem Schritt.)
Bis jetzt haben wir zwei Satz containg verschiedene Sequenzen:

i. leftSeq - all sequences in this set will generate left subtree. 
ii. rightSeq - all sequences in this set will generate right subtree. 

Jetzt jede Sequenz in der linken Unterbaum kann mit jeder Sequenz des rechten Unterbaum zusammengefasst werden. Beim Zusammenführen sollten wir darauf achten, dass die relative Reihenfolge der Elemente erhalten bleibt. Auch in jeder der zusammengeführten Sequenz werden wir den Wert des aktuellen Knotens am Anfang hinzufügen, da Wurzel muss vor allen Kindern kommen.

Pseudocode für Merge

vector<vector<int> > results 
for all sequences L in leftSeq 
    for all sequences R in rightSeq 
     create a vector flags with l.size() 0's and R.size() 1's 
     for all permutations of flag 
      generate the corresponding merged sequence. 
      append the current node's value in beginning 
      add this sequence to the results. 

return results. 

Erklärung: Lassen Sie uns eine Folge nehmen, sagen L(of size n) aus der Menge leftSeq, und einer Sequenz, sagen R(of size m) aus gesetzt rightSeq.
Nun können diese beiden Sequenzen in ^{m + n} C _n Wege zusammengeführt werden!
Proof: Nach dem Zusammenführen wird die neue Sequenz m + n Elemente haben. Da wir die relative Reihenfolge der Elemente beibehalten müssen, werden wir zunächst alle n Elemente aus L in einer der n Stellen unter insgesamt (m+n) Plätze füllen. Danach können die restlichen m Plätze mit Elementen von R gefüllt werden. So müssen wir choose n places from (m+n) places.
Um dies zu tun, läßt einen Booleschen Vektor nehmen erstellen, sagt flags und füllt es mit n0's und m1's .Ein Wert von 0 repräsentiert ein Mitglied aus left Sequenz und ein Wert von 1 darstellt Mitglied von right Sequenz. Alles, was übrig bleibt, ist, alle permutations dieses Flags-Vektors zu erzeugen, was mit next_permutation gemacht werden kann. Jetzt haben wir für jede Permutation von Flags eine eindeutige gemischte Sequenz von L und R.
Beispiel: Say L = {1, 2, 3} R = {4, 5}
so, n=3 und m=2
So können wir ^{3 + 2} C Sequenzen fusionierte Anfänglich, dh 10.
1.now, flags = {0 0 0 }, gefüllt mit 0's und 1's
dies in dieser fusionierten Sequenz führen wird: 1 2 3 4 5
2.after nextPermutation rufen wir
flags = {0 0 }
haben wird, und dies wird Folge erzeugen: 1 2 4 3 5
3 .wieder nach nextPermutation Aufruf werden wir
flags = haben {0 0 1 1 0}
ans dies Sequenz erzeugen: 1 2 4 5 3
und so weiter ...

-Code in C++

Update 3. März 2017: Diese Lösung wird nicht funktionieren einwandfrei, wenn der Originalbaum Duplikate enthält.

Answer 2

gut hier ist mein Python-Code, der alle Sequenzen von Elementen/Nummern für die gleiche BST produziert. für die Logik i auf das Buch von Gayle Laakmann Mcdowell die Codierung Interview Cracken bezeichnet

from binarytree import Node, bst, pprint 

def wavelist_list(first, second, wave, prefix): 
    if first: 
     fl = len(first) 
    else: 
     fl = 0 

    if second:  
     sl = len(second) 
    else: 
     sl = 0 
    if fl == 0 or sl == 0: 
     tmp = list() 
     tmp.extend(prefix) 
     if first: 
      tmp.extend(first) 
     if second: 
      tmp.extend(second) 
     wave.append(tmp) 
     return 

    if fl: 
     fitem = first.pop(0) 
     prefix.append(fitem) 
     wavelist_list(first, second, wave, prefix) 
     prefix.pop() 
     first.insert(0, fitem) 

    if sl: 
     fitem = second.pop(0) 
     prefix.append(fitem) 
     wavelist_list(first, second, wave, prefix) 
     prefix.pop() 
     second.insert(0, fitem)   


def allsequences(root): 
    result = list() 
    if root == None: 
     return result 

    prefix = list() 
    prefix.append(root.value) 

    leftseq = allsequences(root.left) 
    rightseq = allsequences(root.right) 
    lseq = len(leftseq) 
    rseq = len(rightseq) 

    if lseq and rseq: 
     for i in range(lseq): 
      for j in range(rseq): 
      wave = list() 
      wavelist_list(leftseq[i], rightseq[j], wave, prefix) 
      for k in range(len(wave)): 
       result.append(wave[k]) 

    elif lseq: 
     for i in range(lseq): 
     wave = list() 
     wavelist_list(leftseq[i], None, wave, prefix) 
     for k in range(len(wave)): 
      result.append(wave[k]) 

    elif rseq: 
     for j in range(rseq): 
     wave = list() 
     wavelist_list(None, rightseq[j], wave, prefix) 
     for k in range(len(wave)): 
      result.append(wave[k]) 
    else: 
     result.append(prefix) 

    return result 



if __name__=="__main__": 
    n = int(input("what is height of tree?")) 
    my_bst = bst(n) 
    pprint(my_bst) 

    seq = allsequences(my_bst) 
    print("All sequences") 
    for i in range(len(seq)): 
     print("set %d = " %(i+1), end="") 
     print(seq[i]) 

example output: 
what is height of tree?3 

     ___12  
    / \  
    __ 6  13 
/ \  \ 
0  11  14 
    \    
    2    


    All sequences 
    set 1 = [12, 6, 0, 2, 11, 13, 14] 
    set 2 = [12, 6, 0, 2, 13, 11, 14] 
    set 3 = [12, 6, 0, 2, 13, 14, 11] 
    set 4 = [12, 6, 0, 13, 2, 11, 14] 
    set 5 = [12, 6, 0, 13, 2, 14, 11] 
    set 6 = [12, 6, 0, 13, 14, 2, 11] 
    set 7 = [12, 6, 13, 0, 2, 11, 14] 
    set 8 = [12, 6, 13, 0, 2, 14, 11] 
    set 9 = [12, 6, 13, 0, 14, 2, 11] 
    set 10 = [12, 6, 13, 14, 0, 2, 11] 
    set 11 = [12, 13, 6, 0, 2, 11, 14] 
    set 12 = [12, 13, 6, 0, 2, 14, 11] 
    set 13 = [12, 13, 6, 0, 14, 2, 11] 
    set 14 = [12, 13, 6, 14, 0, 2, 11] 
    set 15 = [12, 13, 14, 6, 0, 2, 11] 
    set 16 = [12, 6, 0, 11, 2, 13, 14] 
    set 17 = [12, 6, 0, 11, 13, 2, 14] 
    set 18 = [12, 6, 0, 11, 13, 14, 2] 
    set 19 = [12, 6, 0, 13, 11, 2, 14] 
    set 20 = [12, 6, 0, 13, 11, 14, 2] 
    set 21 = [12, 6, 0, 13, 14, 11, 2] 
    set 22 = [12, 6, 13, 0, 11, 2, 14] 
    set 23 = [12, 6, 13, 0, 11, 14, 2] 
    set 24 = [12, 6, 13, 0, 14, 11, 2] 
    set 25 = [12, 6, 13, 14, 0, 11, 2] 
    set 26 = [12, 13, 6, 0, 11, 2, 14] 
    set 27 = [12, 13, 6, 0, 11, 14, 2] 
    set 28 = [12, 13, 6, 0, 14, 11, 2] 
    set 29 = [12, 13, 6, 14, 0, 11, 2] 
    set 30 = [12, 13, 14, 6, 0, 11, 2] 
    set 31 = [12, 6, 11, 0, 2, 13, 14] 
    set 32 = [12, 6, 11, 0, 13, 2, 14] 
    set 33 = [12, 6, 11, 0, 13, 14, 2] 
    set 34 = [12, 6, 11, 13, 0, 2, 14] 
    set 35 = [12, 6, 11, 13, 0, 14, 2] 
    set 36 = [12, 6, 11, 13, 14, 0, 2] 
    set 37 = [12, 6, 13, 11, 0, 2, 14] 
    set 38 = [12, 6, 13, 11, 0, 14, 2] 
    set 39 = [12, 6, 13, 11, 14, 0, 2] 
    set 40 = [12, 6, 13, 14, 11, 0, 2] 
    set 41 = [12, 13, 6, 11, 0, 2, 14] 
    set 42 = [12, 13, 6, 11, 0, 14, 2] 
    set 43 = [12, 13, 6, 11, 14, 0, 2] 
    set 44 = [12, 13, 6, 14, 11, 0, 2] 
    set 45 = [12, 13, 14, 6, 11, 0, 2]