haskell - haskell 中定义类型的树

Question

我正在尝试通过前/后遍历构建一棵树。我的树类型如下:

        data Tree = Emptytree | Node Integer [Tree]

我是函数式编程的新手。因此，我在构建基本情况和递归时遇到了一些困难。我的函数将是这样的:

           ListToTree :: [Integer] -> [Integer] -> Tree

我构造了一些算法，但无法使其满足语言要求。 我的算法非常简单:我获取第一个列表(前序遍历列表)的每个元素，然后检查它在第二个列表中的位置。我举个例子:

                1                       
             /     \    
          2          5
         /  \
       3      4

此树遍历的预序如您所知 [1,2,3,4,5]

此树遍历的后序如您所知 [3,4,2,5,1]

首先，我查看第一个列表的第一个元素，它是 1，然后我查看它将它放置在第二个列表中，它是最后一个，所以我将其添加到我的树中。然后我检查树的下一个元素，它是第二个列表中的 2，它位于 1 的左侧，这意味着它是它的子元素。然后 3 在 2 的左边(在第二个列表中)，这意味着它也是 2 的儿子然后我查看 4 它在 2 的左边，它是 2 的儿子，最后 5 它在 2 的左边1 它是 1 的子级(因为它位于 2 的右侧，所以不是 2 的子级)。

我尝试去实现它。我编写了辅助函数来确定 Node 是否有子节点。我在我的函数中也使用了计数器所以实际上我的函数是这样的:

           ListToTree :: Integer -> [Integer] -> [Integer] -> Tree
           {-First Stands for counter ,2nd preorder, 3rd postorder-}

我的基本条件是:

                 1. is about if list are Emptytree return Emptytree
                 2. is about if counter== length-1 return Node element [Emptytree]

我的主要问题部分是在我的递归部分:

  ListToTree counter a b  
    | hasChild b counter == 1 = Node ( Element ) [ListToTree (1+counter) a b]
    | hasChild b counter == 0 = Node ( Element ) [Emptytree]
        {-My problematic part if node has no Child what I must change here-}
        {-Or what are your suggestions-}

我需要帮助来改进我的算法。任何类型的帮助或评论将不胜感激。

Answer 1

haskell 的美妙之处在于你通常不需要计数器。通常只进行模式匹配就足够了。

我将给出[Tree]的解决方案，因为这需要较少的情况。如果您想要单个Tree的解决方案，您可以在包装函数中引入一些情况。

listToTree :: [Integer] -> [Integer] -> [Tree]
listToTree [] [] = []
listToTree (x:xs) ys = go where
    fstSubTreePost = takeWhile (/=x) ys -- all the elems of 1. subtree except x
    fstSubTreeLength = length fstSubTreePost
    fstSubTreePre = take fstSubTreeLength xs
    -- this will recursively compute the first subtree
    fstTree = Node x (listToTree fstSubTreePre fstSubTreePost)
    -- the next line will recursively compute the rest of the subtrees
    rest = listToTree (drop fstSubTreeLength xs) (drop (fstSubTreeLength+1) ys)
    go = fstTree : rest