2017-08-14 259 views
1

大家好,这是我的第一个问题,我是Haskell的新手,我需要做一个Haskell函数,它需要一个树并返回其节点中的元素列表中的一个预先遍历但我无法让它工作。树与Haskell遍历

我的树定义如下:

data Tree a = Node a [Tree a] deriving Show 

和预购功能是:

preorderTree :: Tree a -> [a] 
preorderTree Empty = [] 
preorderTree (Node a l r) = a : (preorderTree l) ++ (preorderTree r) 

在事先非常感谢你的帮助:)

+5

嗯,你已经写了'Node'采取只有两个参数,但在这三种模式匹配。 –

+0

你有玫瑰树的数据定义,但似乎期望二叉树的函数。如果你想'preorderTree'为你的'Tree'数据类型工作,请看'concatMap'。 – Alec

+2

这实际上不是你的第一个问题,因为你实际上没有问任何问题。您还没有发布任何错误消息。鉴于遍历和数据声明不匹配,有两种可能的修复方法。哪个修正是正确的不清楚,所以我投票结束。随意编辑问题。 –

回答

2

在Haskell,类型是一组 s。所以我们都有类型构造函数和值构造函数。

所以编写一个haskell函数。我们需要正确定义类型Tree)。在相应的类型中处理每个Empty,Node ...)。

Tree a类型。它的值是Empty或一群孩子。因此,我们有

data Tree a = Empty 
      | Node a [Tree a] 

所以,当我们写一个函数preorderTree :: Tree a -> [a]。我们正在处理类型Tree a,所以我们必须处理值EmptyNode a [Tree a]。因此,我们有

preorderTree :: Tree a -> [a] 
preorderTree Empty = [] 
preorderTree (Node a children) = a : concatMap preorderTree children 

这是一个玫瑰树,如果你只是想一个二叉树,我们需要改变Tree a类型的值构造,因为[Tree a]实在太多了二叉树。因此,我们有

data Tree a = Empty 
      | Node a (Tree a) (Tree a) 

preorderTree :: Tree a -> [a] 
preorderTree Empty = [] 
preorderTree (Node a left right) = a : preorderTree left ++ preorderTree right 

  1. https://wiki.haskell.org/Constructor
+0

非常感谢您的帮助,这真的帮助我,也开始真正喜欢Haskell :) – Deindery