haskell檢查平衡樹

如何檢查這棵樹是否平衡？haskell檢查平衡樹

data Tree a = Leaf a | Node (Tree a) (Tree a) 

size :: Tree a -> Int 
size (Leaf n) = 1 
size (Node x z) = size x + size z + 1

這是我到目前爲止有：

isBalancedTree :: Tree a -> Bool 
isBalancedTree (Node l r) = abs (size l - size r) <= 1 
          && isBalancedTree l && isBalancedTree r 
isBalancedTree _ = False

來源

2015-05-04 user3633383

葉是平衡的，所以最後一行應該真正評估到True，從而導致你：

isBalancedTree :: Tree a -> Bool 
isBalancedTree (Leaf _) = True 
isBalancedTree (Node l r) = 
    let diff = abs (size l - size r) in 
    diff <= 1 && isBalancedTree l && isBalancedTree r

來源

2015-05-04 00:48:44 Shoe

我想讓平衡的樹有大小不同的分支是非常標準的。在某些情況下，它甚至意味着兩個分支在高度上至多有一個不同，或者其他鬆弛（例如，我會稱之爲平衡的紅黑樹，它承諾的是任何子樹的最深葉不超過兩倍像最淺的葉一樣深）。所以它真的取決於上下文。 –

@DanielWagner這是絕對正確的。 – Shoe

調用isBalancedTree（Node（Node（Leaf 1）（Leaf 3））（Leaf 2））應該等於True，但事實並非如此，輸出是False？ – user3633383

haskell檢查平衡樹

回答

相關問題