0

所以我被要求在 Haskell 中制作一个二叉树，并将整数列表作为输入。下面是我的代码。我的问题是列表的最后一个元素没有插入到树中。例如 [1,2,3,4] 它只插入到树中，直到“3”和 4 没有插入到树中。

    data ArbolBinario a = Node a (ArbolBinario a) (ArbolBinario a) | EmptyNode
deriving(Show)

    insert(x) EmptyNode= insert(tail x) (Node (head x) EmptyNode EmptyNode)

    insert(x) (Node e izq der)
     |x == [] = EmptyNode --I added this line to fix the Prelude.Head Empty List error, after I added this line the last element started to be ignored and not inserted in the tree
     |head x == e = (Node e izq der)
     |head x < e = (Node e (insert x izq) der)
     |head x > e = (Node e izq (insert x der))

关于这里发生了什么的任何想法？非常感谢帮助

4

3 回答 3

4

在这里没有帮助的是您正在混淆关注点。为什么不使用一个将列表插入树中的方法，而不是使用一个将单个元素插入树中的函数，然后使用另一个将列表中的所有元素添加到树中的函数呢？例如。

data ArbolBinario a = Node a (ArbolBinario a) (ArbolBinario a)
                    | EmptyNode
                    deriving(Show)

-- insert handles only one element
insert :: (Ord a) => a -> ArbolBinario a -> ArbolBinario a
insert x EmptyNode = Node x EmptyNode EmptyNode
insert x n@(Node e izq der)
  | x == e = n
  | x < e = (Node e (insert x izq) der)
  | x > e = (Node e izq (insert x der))

-- insertList folds the list into a tree
insertList :: (Ord a) => [a] -> ArbolBinario a -> ArbolBinario a
insertList xs t = foldl (\a x -> insert x a) t xs

使用类似foldl的东西让您不必担心到达列表末尾时会发生什么。结果是：

insertList [5, 3, 7, 9, 1, 4, 2, 6] EmptyNode
-- output:
-- Node 5 (Node 3 (Node 1 EmptyNode (Node 2 EmptyNode EmptyNode)) (Node 4 EmptyNode EmptyNode)) (Node 7 (Node 6 EmptyNode EmptyNode) (Node 9 EmptyNode EmptyNode))

希望有帮助。

编辑 - -

我还想指出，遵循其他 Haskell 函数所做的事情并更改参数的顺序可能是一个更好的主意。看到这个：

data ArbolBinario a = Node a (ArbolBinario a) (ArbolBinario a)
                    | EmptyNode
                    deriving(Show)

insert :: (Ord a) => ArbolBinario a -> a -> ArbolBinario a
insert EmptyNode x = Node x EmptyNode EmptyNode
insert n@(Node e izq der) x
  | x == e = n
  | x < e = (Node e (insert izq x) der)
  | x > e = (Node e izq (insert der x))

insertList :: (Ord a) => ArbolBinario a -> [a] -> ArbolBinario a
insertList = foldl insert

这意味着您的函数可以更好地与通常的嫌疑人一起使用（例如折叠、扫描等）。您可以看到 的定义是如何insertList变得更简单的。

仅供参考：）

于 2012-09-22T03:33:15.093 回答
3

你有一些关于更简洁的方法来编写insert函数的建议，但是到目前为止没有人告诉你你的实现出了什么问题，所以让我从这个开始：

data ArbolBinario a = Node a (ArbolBinario a) (ArbolBinario a) | EmptyNode
                      deriving(Show)

insert(x) EmptyNode= insert(tail x) (Node (head x) EmptyNode EmptyNode)

insert(x) (Node e izq der)
 |x == [] = EmptyNode
 |head x == e = (Node e izq der)
 |head x < e = (Node e (insert x izq) der)
 |head x > e = (Node e izq (insert x der))

为简洁起见，我使用较短的列表并缩写EmptyNode为E.

insert [1,2] E
~> insert [2] (Node 1 E E)
--   2 > 1, so the last clause, head x > e, is used
~> Node 1 E (insert [2] E)
-- insertion in empty tree, first equation is used
~> Node 1 E (insert [] (Node 2 E E))
-- Now the first clause of the second equation is used
~> Node 1 E (E)

当所有元素都被插入并且你到达列表的末尾时，你不是什么都不做，而是删除节点。解决此问题的最小更改是将第二个等式的第一个子句更改insert为

 |x == [] = Node e izq der

但是，这仍然会留下一个失败案例（您已经拥有），

insert [] EmptyNode = insert (tail []) (Node (head []) EmptyNode EmptyNode)

会导致*** Exception: Prelude.tail: empty list.

除了是上述错误的原因之外，这里的headand的使用tail也是非常不习惯的。定义这样一个函数的常用方法是在列表上进行模式匹配。也是unidiomatic 是你检查一个空列表，，x == []惯用的方法是使用null x它。在这种情况下，其他守卫要求元素类型是 的实例Ord，因此没有语义变化，但通常对元素类型x == []施加Eq约束，同时null x适用于任意类型。

最后，尽管您认为您的守卫head x == e, head x < e,head x > e涵盖了所有可能性（对于有效的Ord实例，它们确实如此 - 除了浮点类型，其中 aNaN既不等于也不小于也不大于任何值，但这些Ord实例是否有效是一个问题辩论），编译器无法确定这一点，并且会（当被要求对此类事情发出警告时，通常应该使用 进行编译-Wall）警告insert. 为了以编译器知道所有情况都被覆盖的方式覆盖所有情况，最后一个守卫应该有一个otherwise条件。

将您的代码变成更惯用的形式（并修复突出的insert [] EmptyNode错误）会导致

insert :: Ord a => [a] -> ArbolBinario a -> ArbolBinario a
insert []      t         = t     -- if there's nothing to insert, don't change anything
insert (x:xs)  EmptyNode = insert xs (Node x EmptyNode EmptyNode)
-- Using as-patterns, `l` is the entire list, `x` its head, `t` the entire tree
insert l@(x:_) t@(Node e izq der)
    | x == e             = t
    | x < e              = Node e (insert l izq) der
    | otherwise          = Node e izq (insert l der)

现在我们可以寻找进一步的问题。一个可能意想不到的方面insert是，如果要插入的元素列表的头部已经在树中，则整个列表被丢弃并且树完全不变，例如

insert [1 .. 10] (Node 1 EmptyNode EmptyNode) = Node 1 EmptyNode EmptyNode

处理此类事情的常用方法是仅删除列表的头部并仍然插入其余元素。这可以通过将定义的最后一个方程更改为

insert l@(x:xs) t@(Node e izq der)
    | x == e             = insert xs t
    | x < e              = Node e (insert l izq) der
    | otherwise          = Node e izq (insert l der)

更可能是意想不到的方面

  • insert xs EmptyNode总是产生一棵树，其中每个节点只有一个（或没有，对于最低的）非空子树，即构造的树基本上是一个列表。

  • 定义的最后一个等式中的子句强烈建议树应该是二叉搜索树，但定义不维护该属性。例如

    insert [1,10] (Node 3 (Node 2 E E) (Node 7 E E))
~> Node 3 (insert [1,10] (Node 2 E E)) (Node 7 E E)
~> Node 3 (Node 2 (insert [1,10] E) E) (Node 7 E E)
~> Node 3 (Node 2 (insert [10] (Node 1 E E)) E) (Node 7 E E)
~> Node 3 (Node 2 (Node 1 E (Node 10 E E)) E) (Node 7 E E)

                       3
                      / \
                     /   \
                    2     7
                   /
                  /
                 1
                  \
                   \
                    10

解决这些问题的最好方法是，作为OJ。之前建议，将单个元素插入树中的情况分开

insertOne :: Ord a => a -> ArbolBinario a -> ArbolBinario a
insertOne x EmptyNode = Node x EmptyNode EmptyNode
insertOne x t@(Node e izq der)
    | x == e    = t
    | x < e     = Node e (insertOne x izq) der
    | otherwise = Node e izq (insertOne x der)

并使用它来插入列表中的每个元素，从顶部找到它的位置：

insertList :: Ord a => [a] -> ArbolBinario a -> ArbolBinario a
insertList []     t = t
insertList (x:xs) t = insertList xs (insertOne x t)
-- Alternative way:
-- insertList (x:xs) t = insertOne x (insertList xs t)

这些计算模式非常普遍，以至于它们已在以下定义的函数中被捕获Prelude：

insertList xs t = foldl (flip insertOne) t xs
-- or, for the alternative way:
-- insertList xs t = foldr insertOne t xs

正如你所看到的insertOne，对于左折叠的自然参数顺序，我们需要应用flip组合子来交换它的参数顺序，这暗示了列表的自然折叠操作是右折叠的事实foldr。

然而，由于insertOne在它可以做任何事情之前需要知道它的树参数，所以它不是一个为右折叠而量身定制的函数，在左折叠中使用它可能更有效（但实际上要获得效率增益，人们会必须使用严格的左折叠foldl'，可从Data.List和更严格的版本insertOne)。

于 2012-09-22T13:41:43.753 回答
2

为了解决这个问题，我使用了另一个函数

data Tree a = Node a (Tree a) (Tree a) | EmptyNode deriving(Show)

insert :: Ord a => a -> Tree a -> Tree a
insert x EmptyNode = Node x EmptyNode EmptyNode
insert x (Node y left right)
    | x == y = (Node y left right)
    | x <  y = (Node y (insert x left) right)
    | x >  y = (Node y left (insert x right))

buildtree :: Ord a => [a] -> Tree a
buildtree []     = EmptyNode
buildtree (x:xs) = insert x (buildtree xs)

tree :: Ord a => [a] -> Tree a
tree xs = buildtree (reverse xs)

并且要构造二叉树，您需要调用buildtree函数。问题是您需要先反转列表。所以，tree会做好工作。

*Main> insert 5 (insert 12 (insert 2 (insert 10 EmptyNode)))
Node 10 (Node 2 EmptyNode (Node 5 EmptyNode EmptyNode)) (Node 12 EmptyNode EmptyNode)

*Main> tree [10,2,12,5]
Node 10 (Node 2 EmptyNode (Node 5 EmptyNode EmptyNode)) (Node 12 EmptyNode EmptyNode)

*Main> buildtree [5,12,2,10]
Node 10 (Node 2 EmptyNode (Node 5 EmptyNode EmptyNode)) (Node 12 EmptyNode EmptyNode)

更新

你可以避免使用另一个函数，这样：

insert2 :: Ord a => [a] -> Tree a -> Tree a
insert2 []     t = t
insert2 (x:xs) EmptyNode = insert2 xs (Node x EmptyNode EmptyNode)
insert2 (x:xs) (Node y left right)
            | x == y = insert2 xs (Node y left right)
            | x <  y = insert2 xs (Node y (insert2 [x] left) right)
            | x >  y = insert2 xs (Node y left (insert2 [x] right))

但是，它不如使用 foldl 或其他方式高效，唯一的好处是只使用一个函数来完成所有操作，不需要反向。

*Main> insert2 [10,2,12,5] EmptyNode
Node 10 (Node 2 EmptyNode (Node 5 EmptyNode EmptyNode)) (Node 12 EmptyNode EmptyNode)
于 2012-09-22T03:32:23.883 回答