从列表定义函数到二叉树和一元树 [英] Defining a function from lists to binary and unary trees

问题描述

请考虑以下类型所定义的二进制和一元树，以及一个函数flatten，该函数将二进制和一元树转换为列表(例如，flatten (Node (Leaf 10) 11 (Leaf 20))为[10,11,20]):

Consider binary and unary trees, as defined by the following type, and a function flatten, which converts binary and unary trees to lists (e.g, flatten (Node (Leaf 10) 11 (Leaf 20)) is [10,11,20]):

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，该函数将列表转换为二叉树和一元树，特别是按照以下模式的方式，该函数适用于长度为< =的列表7.我可以从示例中看到模式如何进行，但看不到如何创建递归函数:

I am trying to define a recursive function, reverseflatten, which converts lists to binary and unary trees, specifically in the manner of the following pattern, which works for lists of length <= 7. I can see how the pattern would go on, but not how to create a recursive function from my example:

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,z,x'] = Node (Leaf x) y (UNode z (Leaf x') )
reverseflatten [x,y,z,x',y'] = Node (Leaf x) y ( Node (Leaf x') z (Leaf y'))
reverseflatten [x,y,z,x',y',z'] =  Node (Leaf x) y ( Node (Leaf x') z ( UNode y' (Leaf z')))
reverseflatten [x,y,z,x',y',z',x''] =  Node (Leaf x) y ( Node (Leaf x') z ( Node (Leaf z') y' (Leaf x'')))

我将如何创建这样的递归函数，以便对任何有限列表形成上面定义的那种二叉树?下面的答案不会执行此操作，因为它没有遵循上面的模式.

How would I create such a recursive function, that for any finite list, forms a binary tree of the kind defined above? The answer below does not do this, since it does not follow the pattern above.

对于偶数列表> 2，我遵循的过程应该是相当透明的(将树对应于奇数列表，然后添加一元节点). 我遵循的从奇数列表构造树的一般过程是这样. reverse flatten[x,y,z]是Node (Leaf x) y (Leaf z).然后对于下一个奇数编号的列表[x, y, z, x', y']，我想在reverseflatten [x,y,z]的情况下将z保留在其先前位置(其中z是最后右下角的叶子)，因此位置z与Node (Leaf x') z (Leaf y')中的第二位一样，因此这种情况下的树与reverseflatten [x,y,z]的树一样，只是我们在右下角的叶子z周围添加了节点.然后，我希望x'和y'以它们在列表中出现的顺序包围z，因此是Node(Leaf x')z(Leaf y'). 然后对于下一个奇数列表reverseflatten [x,y,z,x',y',z',x'']，我有一个类似的想法.我希望y'保留在reverseflatten [x,y,z,x',y']和reverseflatten [x,y,z,x',y',z', x'']中的位置，并以z'和x''包围y'的方式构造它们，并按照它们在列表中出现的顺序排列.

The procedure I followed for even lists > 2, should be fairly transparent (you take the tree corresponding to an odd list and then you add a unary node). The general procedure I followed for constructing a tree from an odd-numbered list was this. reverse flatten[x,y,z] is Node (Leaf x) y (Leaf z). Then for the next odd-numbered list up, [x, y, z, x', y'], I wanted to preserve z in its previous position in the case for reverseflatten [x,y,z] (in which z was the final bottom right leaf), and so position z as in Node (Leaf x') z (Leaf y'), in the second place, so that the tree for this case is just like the tree for reverseflatten [x,y,z], except that we add nodes surrounding the bottom right leaf, z. I then wanted x' and y' to surround z, in the order in which they are present in the list, hence Node (Leaf x') z (Leaf y'). Then for the next odd-numbered list reverseflatten [x,y,z,x',y',z',x''] , I had a similar idea in mind. I wanted y' to remain in its place in reverseflatten [x,y,z,x',y'] and reverseflatten [x,y,z,x',y',z', x'']) to be constructed by surrounding y' by z' and x'', in the order in which they are present in the list.

推荐答案

我试图更改代码以捕获您要的模式.我的实现效率不是很高，但是目前还没有想到. 我希望我能正确理解模式.

I tried to change the code to capture the pattern you were asking for. My implementation is not very efficient, but could not think of any at the moment. I hope that I understood the pattern correctly.

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)))

这篇关于从列表定义函数到二叉树和一元树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！