树木折叠式

Question

我试图实现一个foldTree函数，从使用foldr的值列表(问题2 这里)中生成一个平衡的二叉树，但是得到的解决方案实际上并不是以正确的方式编写的：

data Tree a = Leaf
            | Node Int (Tree a) a (Tree a)
            deriving (Show,Eq)


foldTree::[a]-> Tree a
foldTree a=_foldTree a 0 ((getHeight (length a))-1) (length a)
           where 
           _foldTree::[a]->Int->Int->Int->Tree a
           _foldTree a n h l
                        | n>=l = Leaf
                        | otherwise = Node h (_foldTree a (2*n+1) (h-1) l ) (a!!n) (_foldTree a (2*n+2) (h-1) l)


getHeight::Int->Int
getHeight n=ceiling(log (fromIntegral(n))/log 2)

该解决方案存在精度问题。我想我可以用一些我一直缺少的高层次的抽象。

我只是把堆(某种程度上说，没有排序)从列表中删除。

Answer 1

虽然输出应该是一棵平衡的树，但似乎不需要以任何方式排序(至少给定的示例不需要)。所以这绝对不是堆。解决方案需要使用foldr，而您的解决方案并不满足这一要求。

您需要将任务分为两部分：

1. 将新元素插入到平衡树中，以便结果再次成为平衡树。函数的签名应该有点像insert :：->树和->树a--如果您不知道如何实现insert，请在下面的框上悬停，并给出另一个提示(但我强烈建议您先尝试不使用它)：插入空树非常简单。如果树是非空的，请检查两个子树并递归地将元素插入到较低高度的子树中。(如果高度相同，只要选择比较方便的。)由于以这种方式插入元素可以保持树的高度，或者只增加1，所以得到的树也是平衡的。
2. 使用插入函数折叠列表。这部分很容易，当你有1。