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,它检查Tree是否是二叉搜索树.

   我用树测试,然后得到2 4 7 8 10 | 5 6 10 12.在这里你可以看到中间的所有值都被排序,但我不知道我应该如何编码.

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

3. 使用函数insert(2)定义Haskell函数merge :: Tree -> Tree -> 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插入根部的位置并将整棵树粘在那里.