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

4

Your insertion function is in error when the two sub-trees' heights are equal, because inserting into the right sub-tree will increase its height if it was already full. It is not immediately clear to me whether such situation will ever arise or not in your code.

The apparently correct way to insert a new element into a tree seems to be

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

This creates almost balanced trees (a.k.a. AVL-trees). But it pushes each new element to the very bottom of the tree.

edit: These trees can be nicely seen with

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

Try

putStr . showTree $ foldTree "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"

And yes, you can write foldTree shorter, as

foldTree = foldr insertInTree Leaf
于 2013-04-23T09:06:42.797 回答
3

Just want to point out that the accepted answer is good but will not work after having a height 3 balanced binary tree as it did not consider the fact that the left tree could have less height than the right after inserting.

Apparently, the code could've worked adding an extra condition:

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 回答