haskell - Haskell 中的二叉搜索树函数

Question

我需要 3 项任务的帮助。我真的是 Haskell 和函数式编程的新手。

data Tree = Node Int Tree Tree | Nil

1. 借助函数定义collapse

   collapse :: Tree -> [Int]
   collapse Nil = []
   collapse (Node x y z) = (collapse y) ++ [x] ++ (collapse z)
   

   一个 Haskell 函数check :: Tree -> Bool，它检查树是否是二叉搜索树。

   我用一棵树测试它并得到2 4 7 8 10 | 5 6 10 12. 在这里您可以看到中间的所有值都已排序，但我不知道应该如何编码。

2. 定义一个 Haskell 函数insert :: Int -> Tree -> Tree，它将整数值添加到树中并返回一个二叉搜索树。

3. 使用函数insert(2) 定义一个 Haskell-Function merge :: Tree -> Tree -> Tree，它将两棵树合并到另一棵二叉搜索树。

Answer 1

好吧，我不会回答所有这些问题，但我可以提供一些帮助。

1. 如果我们真的尝试collapse一棵看起来像这样的树

             a
            / \
           /   \             
          b     c
         / \   / \
        d   e f   g
   

   我们会得到[d, b, e, a, f, c, g]。请注意，如果一个元素出现在树中某个元素的“左侧”，那么它就是我们平面列表中该元素的“左侧”。我们知道，如果元素, 在二叉搜索树中a元素 , 的左侧，则< 。所以我们只需要检查这个属性是否适用于我们的列表。cac

2. 在树中插入一个元素。我们有4个案例要处理

   insert newVal (Node treeVal left right) | newVal < treeVal = <1>
                                           | newVal > treeVal = <2>
                                           | otherwise        = <3>
   insert newVal Nil = <4>
   

   其中 <1> 插入到节点中，其值大于节点中的值。<2> 则相反：节点的值大于新值。在 3 中它们是相等的，在 4 中我们插入Nil基本情况。您几乎可以直接翻译二叉搜索树的定义来填补这里的漏洞。

3. 由于我们没有尝试拥有平衡的二叉树，如果我们有 2 棵树，A并且B. 我们所要做的就是找到B要插入的根的位置并将整棵树粘在那里。