haskell - 以特定方式展平二叉树

Question

考虑以下二叉树和一元树的定义，一个函数flatten，它将二叉树和一元树转换为列表（例如，flatten (Node (Leaf 10) 11 (Leaf 20))is [10,11,20]）和一个函数，reverseflatten将列表转换为二叉树（以此处描述的特定方式（Defining a function from lists到二叉树和一元树），如下图所示）：

data Tree a = Leaf a | Node (Tree a) a (Tree a) | UNode a (Tree a) deriving (Show)
flatten :: Tree a -> [a]
flatten (Leaf x) = [x] 
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
flatten (UNode l x) = [l] ++ flatten x

reverseflatten :: [a] -> Tree a
reverseflatten [x] = (Leaf x)
reverseflatten [x,y] = UNode x (Leaf y)
reverseflatten [x,y,z] = Node (Leaf x) y (Leaf z)
reverseflatten (x:y:xs) = revflat2 (x:y:xs)

revflat2 :: [a] -> Tree a
revflat2 [x] = (Leaf x)
revflat2 [x,y] = UNode y (Leaf x)
revflat2 [x,y,z] = Node (Leaf x) y (Leaf z)
revflat2 (x:y:xs) = Node (Leaf x) y (revflat2 ([head $ tail xs] ++ [head xs] ++ tail (tail xs)))

reverseflatten [1..5]是Node (Leaf 1) 2 (Node (Leaf 4) 3 (Leaf 5)，但(reverseflatten(flatten(reverseflatten [1..5])))不返回与 相同的值reverseflatten [1..5]。如何flatten修改，使其reverseflatten x: xs与 相同(reverseflatten(flatten(reverseflatten x:xs)))？

reverseflatten形成下图中的一系列树。例如，reverseflatten [x,y,z]在图片中形成树 2、reverseflatten [x,y,z, x']形成树 3、reverseflatten [x,y,z, x', y']形成树 4、reverseflatten [x,y,z, x', y', z']形成树 5、reverseflatten [x,y,z, x', y', z', x'']形成树 6，等等。

我想要的是reverseflatten x: xs和(reverseflatten(flatten(reverseflatten x:xs))). 所以我需要设计flatten让它有这样的效果。

我做了以下尝试（flatten Node l x r应该将案例分为r叶子的情况和不是叶子的情况）：

flatten :: Tree a -> [a]
flatten (Leaf x) = [x] 
flatten (UNode l x) = [l] ++ flatten x 
flatten (Node l x r)
    | r == Leaf y   = [l, x, r]  
    | otherwise = flatten (Node l x (revflat2 ([head $ tail r] ++ [head r]     ++ tail (tail r)))

但这会产生：

experiment.hs:585:1: error:
    parse error (possibly incorrect indentation or mismatched brackets)
    |
585 | flatten (UNode l x) = [l] ++ flatten x 
    | ^

标签： haskellrecursiontreebinary-tree

Answer 1

我认为您的问题是树的第一个节点与其他节点的模式不同，就像如果您查看 Tree1 它转到 [x,y,z] ，而 Tree4 转到 [x,y,[x '，z，y']]。

您可以看到子节点的顺序与第一个节点的顺序不同，这就是为什么有些人注意到它感觉不自然的原因。要修复它，您可以将 reverseFlatning 的定义更改为具有恒定模式的定义，我假设您不想要，或者更改您的 flatten 以考虑这种奇怪的模式：

data Tree a = Leaf a | Node (Tree a) a (Tree a) | UNode a (Tree a) deriving (Show)

reverseFlatten :: [a] -> Tree a
reverseFlatten [x] = (Leaf x)
reverseFlatten [x,y] = UNode y (Leaf x)
reverseFlatten [x,y,z] = Node (Leaf x) y (Leaf z)
reverseFlatten (x:y:xs) = Node (Leaf x) y (reverseFlatten ((xs !! 1) : (head xs) : (drop 2 xs)))

flatten :: Tree a -> [a]
flatten (Leaf x)            = [x]
flatten (UNode l (Leaf x))  = [l,x]
flatten (Node (Leaf l) x r) = l : x : flattenRest r

flattenRest :: Tree a -> [a]
flattenRest (Leaf x)            = [x]
flattenRest (UNode l (Leaf x))  = [l,x]
flattenRest (Node (Leaf l) x r) = x : l : flattenRest r

请注意，我扩展了您的 UNode 和左节点的模式匹配，因为您已经知道它将是一个左侧树，因此如果您已经知道结果将是什么，则无需调用您的函数。