7

foldTreeリストから平衡二分木を構築する関数を書きます。私は使用foldrしなければならず、それは大丈夫です、私はそれを使用しましたが、私はinsertInTree関数を再帰的にします=（今のところ、木の中を歩くこの方法しか知りません=））。

更新:関数についてよくわかりませんinsertTree:再帰で高さを計算するのは正しいですか?? =(( ここで助けが必要です。

insertInTree再帰なしで書くこと（何かを含むuntil/iterate/unfoldr）またはfoldTreeヘルパー関数なしで関数を作成することは可能ですか？

これは私の以下の試みです：

data Tree a = Leaf
            | Node Integer (Tree a) a (Tree a)
            deriving (Show, Eq)

foldTree :: [a] -> Tree a
foldTree = foldr (\x tree -> insertInTree x tree) Leaf

insertInTree :: a -> Tree a -> Tree a
insertInTree x Leaf = Node 0 (Leaf) x (Leaf)
insertInTree x (Node n t1 val t2) = if h1 < h2 
                                    then Node (h2+1) (insertInTree x t1) val t2 
                                    else Node (h1+1) t1 val (insertInTree x t2) 
  where h1 = heightTree t1
        h2 = heightTree t2

heightTree :: Tree a -> Integer
heightTree Leaf = 0
heightTree (Node n t1 val t2) = n

出力：

*Main> foldTree "ABCDEFGHIJ"
Node 3 (Node 2 (Node 0 Leaf 'B' Leaf) 'G' (Node 1 Leaf 'F' (Node 0 Leaf 'C' Leaf))) 'J' (Node 2 (Node 1 Leaf 'D' (Node 0 Leaf 'A' Leaf)) 'I' (Node 1 Leaf 'H' (Node 0 Leaf 'E' Leaf)))
*Main>
4

2 に答える 2

3

受け入れられた答えは良いですが、挿入後に左の木の高さが右の木よりも低くなる可能性があるという事実を考慮していないため、高さ3のバランスの取れたバイナリツリーを作成した後は機能しないことを指摘したいだけです。

どうやら、コードは追加の条件を追加することで機能した可能性があります。

insertInTree x (Node n t1 val t2) 
    | h1 < h2   = Node  n      t1n val t2 
    | h1 > h2   = Node  n      t1  val t2n
    | nh1 < nh2 = Node  n      t1n val t2
    | otherwise = Node (nh2+1) t1  val t2n 
  where h1  = heightTree t1
        h2  = heightTree t2
        t1n = insertInTree x t1
        t2n = insertInTree x t2
        nh1 = heightTree t1n
        nh2 = heightTree t2n
于 2016-03-12T12:02:48.670 に答える