使用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