如何清理級別遍歷函數？

Question

我處理被定義爲一般的樹設置如下：

data Tree a = Node a [Tree a] deriving (Eq, Read, Show) 

有了這個設置，我創建了打印在樹的特定級別（根是0級，直接節點功能根的孩子是1級等）。這是函數：

level :: Int -> Tree a -> [a] 
level 0 (Node a _) = [a] 
level n (Node _ subtrees) = concatMap (level (n - 1)) subtrees 

使用此功能爲基礎，我創建了一個第二功能，levelorder，打印在水平序遍歷樹的所有節點的列表。該功能目前看起來是這樣的：

levelorder :: Tree a -> [a] 
levelorder tree = level 0 tree ++ level 1 tree ++ level 2 tree ++ level 3 tree 

雖然這對於目前與我，我想清理，哪裏會與任何大小的樹工作，工作樹的偉大工程。正如你所看到的，它目前只適用於4級（0到3）的樹。我將如何去實現這個目標，我仍然可以利用關卡功能作爲基礎？

Answer 1

如果你有一個功能depth :: Tree a -> Int是告訴你的樹有多深，這將是這麼簡單

levelorder tree = concatMap (\lvl -> level lvl tree) [0..depth tree] 

這不是一個特別快的實現，不過，你最終會遍歷樹多次。

Answer 2

您首先需要一個深度函數，以便您不需要修復連接級別的數量。

depth :: Tree a -> Int 
depth (Node _ [])  = 1 
depth (Node _ r@(x:xs)) = 1 + maximum (map depth r) 

然後，而不是固定的次數使用(++)， 您只需concat的的map荷蘭國際集團在其從列表[0..depth tree]繪製每個級別水平儀功能的結果。

levelorder' tree = concatMap (flip level tree) [0..depth tree]

Answer 3

，直到你用完節點可以succesively遍歷層次：

levelorder :: Tree a -> [a] 
levelorder t = concat $ takeWhile (not . null) $ map (`level` t) [0..]