在列表中打印每层的二叉树 [英] Printing Binary Tree per Layer in a List
问题描述
该函数应该将图层中的参数树的标记作为图层列表打印出来。每层中的节点和叶子标记从左到右列出,即该层的最左边节点,列表的第一个元素,最右边的节点是列表的最后一个元素。 Ord类型的参数指示层是按照从最小层到最大层(TopDown)的升序还是从最大层到最小层(BottomUp)的降序来发布
data Tree = Leaf Integer |节点整数树树
类型Layer = [Integer]
data Ord = BottomUp | TopDown
wLayer :: Tree - > Ord - > [Layer]
示例1:我们使用参数调用函数wLayer
wLayer (节点1(节点2(叶21)(叶22))(节点3(叶31)(叶32)))TopDown
结果:[[1],[2,3],[ (节点2(叶21)(叶22))(节点3(叶节点2(叶21)(叶节点22))节点3(叶节点2 31)(Leaf 32)))BottomUp
结果:[[21,22,31,32],[2,3],[1]]
编辑
数据树=叶整数
|节点整数树树
类型层= [整数]
数据Ord = BottomUp | TopDown
writeLayer :: Tree - > Ord - > [Layer]
writeLayer Leaf x = [x]
writeLayer(Node x lt rt)BottomUp =(writeLayer rt BottomUp)++ [x] ++(writeLayer lt BottomUp)
writeLayer节点x lt rt)TopDown = [x] ++(writeLayer lt TopDown)++(writeLayer rt TopDown)
这是一个简单的方法完成这个。它将所有节点都放在一个级别上,并从中提取整数值,然后在这些相同节点的所有子节点上递归。之后,您在 Ord
上进行匹配,以确定您是否需要将列表颠倒过来。
writeLayer to =
case $ of
BottomUp - >反向$ makeLayer [t]
TopDown - > makeLayer [t]
where
extract(Node i __)= i
extract(Leaf i)= i
children(Node _ab)= [a,b]
children _ = []
makeLayer [] = []
makeLayer ts =地图提取ts:(makeLayer $ concat $ map children ts)
The function should print the markings of the argument tree in layers as a list of layers. The node and leaf markings in each layer are listed from left to right, that is, which is the most left node of the layer, the first element of the list, the right-most node is the last element of the list. The argument of type Ord indicates whether the layers in ascending order from the smallest to the largest layer (TopDown) or in descending order from largest to smallest layer (BottomUp) are to be issued
data Tree = Leaf Integer | Node Integer Tree Tree
type Layer = [Integer]
data Ord = BottomUp | TopDown
wLayer :: Tree -> Ord -> [Layer]
Example 1: We call the function wLayer with arguments
wLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) TopDown
the result : [[1],[2,3],[21,22,31,32]]
Example 2: wLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) BottomUp the result: [[21,22,31,32],[2,3],[1]]
how can i implement this one ?
Edit
data Tree = Leaf Integer
| Node Integer Tree Tree
type Layer = [Integer]
data Ord = BottomUp | TopDown
writeLayer :: Tree -> Ord -> [Layer]
writeLayer Leaf x = [x]
writeLayer (Node x lt rt) BottomUp = (writeLayer rt BottomUp) ++ [x] ++ (writeLayer lt BottomUp)
writeLayer (Node x lt rt) TopDown = [x] ++ (writeLayer lt TopDown) ++ (writeLayer rt TopDown)
this is my program but it isn't work how can i fix it ?
Here is a simple way of accomplishing this. It takes all of the nodes at a level and extracts the integer value from them, and then recurses on all of the children of these same nodes. After that, you match on Ord
to determine if you need to reverse the list.
writeLayer t o =
case o of
BottomUp -> reverse $ makeLayer [t]
TopDown -> makeLayer [t]
where
extract (Node i _ _) = i
extract (Leaf i) = i
children (Node _ a b) = [a, b]
children _ = []
makeLayer [] = []
makeLayer ts = map extract ts : (makeLayer $ concat $ map children ts)
这篇关于在列表中打印每层的二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!