BST（バイナリ検索ツリー）からリンクリストアレイ

Question

左から右へ配列を横切って各要素を挿入することにより、バイナリ検索ツリーが作成されました。この木はバランスのとれた木ではないかもしれません。異なる要素を持つバイナリ検索ツリーがある場合、このツリーにつながっている可能性のあるすべての配列を出力します。

この質問に答えるために、私は次のコードを書きました。それでも、すべてのケースでツリーにつながる可能性のあるすべての配列を出力するわけではありません。あなたは何を修正すべきだと思いますか？

Answer 1

グラフでAがBの祖先であり、Aが配列内でBよりも先にあるとします。他に何も仮定することはできません。 したがって、配列は次の再帰関数によって生成できます。

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