使用foldr構建平衡二叉樹

Question

我編寫從列表構建平衡二叉樹的函數foldTree。 我必須使用foldr，它沒問題，我用它，但我讓insertInTree函數遞歸=（現在我只知道這種方式走過樹=））。

UPDATE：iam不知道函數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 

輸出：當兩個子樹的高度EQU

*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> 

Answer 1

你插入功能是錯誤的al，因爲如果它已經滿了，插入到右邊的子樹中將增加它的高度。我不清楚這種情況是否會出現在您的代碼中。

插入一個新元素放入樹顯然是正確的方法似乎是

insertInTree x (Node n t1 val t2) 
    | h1 < h2 = Node n (insertInTree x t1) val t2 
    | h1 > h2 = Node n t1 val t2n 
    | otherwise = Node (h+1) t1 val t2n 
    where h1 = heightTree t1 
     h2 = heightTree t2 
     t2n = insertInTree x t2 
     h = heightTree t2n  -- might stay the same 

這將創建幾乎平衡樹（又名AVL樹）。但它會將每個新元素推到樹的最底部。

編輯：這些樹可以很好地看出與

showTree Leaf = "" 
showTree n@(Node i _ _ _) = go i n 
    where 
    go _ (Leaf) = "" 
    go i (Node _ l c r) = go (i-1) l ++ 
    replicate (4*fromIntegral i) ' ' ++ show C++ "\n" ++ go (i-1) r 

嘗試

putStr。 showTree $ foldTree「ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890」

是的，你可以寫foldTree較短，如

foldTree = foldr insertInTree Leaf 

Answer 2

只是想指出的是，公認的答案是好的，但具有一定高度後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