我写了函数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>
最佳答案
当两个子树的高度相等时,您的插入函数将出错,因为如果插入到正确的子树中,如果其已满,则会增加其高度。我现在还不清楚在您的代码中是否会出现这种情况。
在树中插入新元素的似乎正确的方法似乎是
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
尝试
是的,您可以将
foldTree
缩短为foldTree = foldr insertInTree Leaf