Von BST (binärer Suchbaum) zum verknüpften Listenfeld

Question

Ein binärer Suchbaum wurde erstellt, indem ein Array von links nach rechts durchlaufen und jedes Element eingefügt wurde. Dieser Baum ist möglicherweise kein ausgewogener Baum. Bei einem binären Suchbaum mit verschiedenen Elementen drucken Sie alle möglichen Arrays, die zu diesem Baum hätten führen können.

Um auf diese Frage zu antworten, habe ich den folgenden Code geschrieben. Dennoch scheint es, dass es nicht alle möglichen Arrays druckt, die in allen Fällen zum Baum führen könnten. Was sollte Ihrer Meinung nach geändert werden?

Answer 1

Was das Array betrifft ist, dass, wenn A Vorfahre von B in der Grafik ist dann A im Array B vorausgeht. Nichts anderes kann angenommen werden. So können die Arrays durch die folgende rekursive Funktion erzeugt werden.

function sourceArrays(Tree t) 

    // leafe node 
    if t == null 
    return empty list; 

    r = root(t); 
    append r to existing arrays; 

    la = sourceArrays(t.left); 
    ra = sourceArrays(t.right); 

    ac = createArrayCombitations(la, ra); 
    append ac to existing arrays; 

end 

function createArrayCombitations(la, ra) 


    foreach a in la 
    foreach b in ra 
     r = combineArrays(a,b); 
     add r to result; 
    end 
    end 

end 

function combineArrays(a, b) 
    generate all combinations of elements from two array such that order of elements in each array is preserved. 
    Ie if x precedes y in a or b the x precedes y in result