4

この関数はリスト xs を取り、xs とまったく同じ要素のセットからなるバランスのとれた二分探索木を構築する必要があります。

結果は次のようになります: (リストが [1,2,3,4,5,6,7,8] の場合)

ノード (ノード (ノード (ノード空 1 空) 2 空) 4 (ノード空 4 空)) 5 (ノード (ノード空 6 空) 7 (ノード空 8 空))

つまり、ツリーは次のようになります。

                5
               / \
              3   7
             / \ / \
            2  4 6  8
           /
          1

これではなく：

                5
               / \
              4   6
             /     \
            3       7
           /         \
          2           8
         /
        1

誰かがこれを行う方法を教えてもらえますか? 完全にバランスが取れていない2番目のツリーを実行できることがわかりましたが、最初のツリーの実行方法がわかりません。

助けていただければ幸いです!! 前もって感謝します！

4

2 に答える 2

7

入力リストをソートします。ここで、ルート ノードがリストの中央の要素であり、左と右のサブツリーが、このプロセスを中央の左と右のサブリストにそれぞれ適用することによって生成されたサブツリーであるツリーを作成します。

ハスケルでは:

buildBalanced []   = Empty
buildBalanced elts = Node (buildBalanced $ take half elts) 
                          (elts !! half) 
                          (buildBalanced $ drop (half+1) elts)
    where half = length elts `quot` 2

main = putStrLn $ show $ buildBalanced [1,2,3,4,5,6,7,8]
-- prints Node (Node (Node (Node Empty 1 Empty) 2 Empty) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node Empty 8 Empty))
于 2013-09-30T09:06:52.517 に答える
1

ツリーの最上部が中間要素でなければならない場合:

mkBalanced [] = Empty
mkBalanced xs = Node mid (mkBalanced half0) (mkBalanced half1)
    where (half0, half') = splitAt ((length xs `div` 2) - 1) xs
          half1 = tail half'
          mid = head half'

そうでない場合:

mkBalanced [] = Empty
mkBalanced (x:xs) = Node x (mkBalanced half0) (mkBalanced half1)
    where (half0, half1) = splitAt (length xs `div` 2) xs
于 2013-10-01T22:56:47.003 に答える