使用foldr构建平衡二叉树

Question

我写了一个名为foldTree的函数，可以从列表构建平衡二叉树。我必须使用foldr，我已经使用它了，但我让insertInTree函数递归 =( 目前我只知道通过这种方式遍历树 =))。

更新: 我不确定insertInTree函数是否正确在递归中计算高度？ =(( 在这里需要一些帮助。

有可能编写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计算的相匹配？ - Chris Kuklewicz

我只有这个作业任务的定义：二叉树的高度是从根节点到最深节点的路径长度。例如，一个只有一个节点的树的高度为0；一个根节点有两个子节点的三个节点的树的高度为1；以此类推。哦！计算高度时出了些问题=(( - Сергей Кузминский

我现在不确定insertTree函数：它正确计算高度吗？我的意思是Node(h2+1) Node(h1+1)？如何将insertTree作为一对管道函数？ - Сергей Кузминский

计算高度对于平衡是必要的。你已经在每个节点中保存了高度，所以heightTree的时间复杂度是O(1)。 - Emil Vikström

具有相同高度值的叶子和两个叶子的节点存在问题吗？当我创建一个值为1的新节点时， Leaf=0 和 Node 0 Leaf a Leaf。我认为一切都很好。 - Сергей Кузминский

Answer 1

当两个子树的高度相等时，您的插入函数存在错误，因为如果右子树已满，则在右子树中插入将增加其高度。我无法立即确定在您的代码中是否会出现这种情况。

似乎正确的向树中插入新元素的方法是

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

- Will Ness

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

- Kenneth Tang

---

不，被接受的答案考虑了所有可能性，并且按照广告宣传的那样工作。它创建了树，使得对于树中的每个节点，该节点的两个分支的深度之差最多为1，也就是AVL树。我没有发现深度超过3的问题。我已经使用新函数编辑了答案，以图形化树形方式显示这些树，并提供了建议的测试。 - Will Ness

刚刚使用了你的函数进行了测试；对于我在答案中展示的测试用例，我的函数创建了深度为7的树形结构；而你的确创建了更加平衡的树形结构，深度为6，但需要付出代码更复杂的代价。 - Will Ness

你可以通过将叶子的高度定义为-1（heightTree Leaf = -1）并使用@WillNess的答案来实现更平衡的树。生成的树不像这个答案那样平衡，但会更有效率。 - AAL