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

Question

我需要 3 项任务的帮助。我对 Haskell 和函数式编程还很陌生。

data Tree = Node Int Tree Tree | Nil

1. Define with help of the function collapse

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

   a Haskell-Function check :: Tree -> Bool which checks if the Tree is a binary search tree.

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

2. Define a Haskell-Function insert :: Int -> Tree -> Tree which adds the Integer Value to the Tree and return also a binary search tree.

3. Define with the function insert (2) a Haskell-Function merge :: Tree -> Tree -> Tree which merges two trees to another binary search tree.

Answer 1

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

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

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

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

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 的根所在的位置将被插入并将整棵树粘在那里。