Haskell中的水平順序

我有一棵樹的結構，我想按級別打印樹。Haskell中的水平順序

data Tree a = Nd a [Tree a] deriving Show 
type Nd = String 
tree = Nd "a" [Nd "b" [Nd "c" [], 
         Nd "g" [Nd "h" [], 
           Nd "i" [], 
           Nd "j" [], 
           Nd "k" []]], 
       Nd "d" [Nd "f" []], 
       Nd "e" [Nd "l" [Nd "n" [Nd "o" []]], 
         Nd "m" []]] 
preorder (Nd x ts) = x : concatMap preorder ts 
postorder (Nd x ts) = (concatMap postorder ts) ++ [x]

但如何通過級別來做到這一點？「水平樹」應該打印[「a」，「bde」，「cgflm」，「hijkn」，「o」]。我認爲「迭代」將是合適的功能，但我不能想出如何使用它的解決方案。你能幫我嗎？

來源

2010-04-28 brain_damage

你不需要'type Nd = String'。它不會在你的代碼中做任何事情，因爲你永遠不會使用類型Nd（你使用類型樹的數據構造函數Nd，但這完全不相關）。 – sepp2k 2010-04-28 18:56:57

我不認爲你想要的結果顯示在表格中：它連接來自相鄰節點的數據的方式，a）如果a不是列表類型，並且b）丟失關於遍歷的信息，則不起作用。考慮這個樹：Nd「a」[Nd「bde」[Nd「cgflm」[Nd「hijkn」[Nd「o」[]]]]] - 它會帶來與您所要求的結果相同的結果。爲了不陷入這個陷阱，使用字符（'a'）或數字作爲示例樹中的節點值。這將保持你的解決方案很好的一般性。 – MtnViewMark 2010-04-28 21:44:46

你只需要計算水平對所有的子樹和根後壓縮它們放在一起：

levels :: Tree [a] -> [[a]] 
levels (Nd a bs) = a : foldr (zipWith' (++)) [] (map levels bs)

可悲的是，zipWith沒有做正確的事情，所以我們可以改用：

zipWith' f xs [] = xs 
zipWith' f [] xs = xs 
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

更新：有一些問題（我同意），你最初問的是有點奇怪，因爲它不是一個通用的廣度優先樹來列出轉換器。你可能真的想要的是Concat的結果：

levels' (Nd a bs) = [a] : foldr (zipWith' (++)) [] (map levels' bs)

來源

2010-04-28 19:09:58 sigfpe

不錯的解決方案。我想Haskell沒有你的變種zipWith，它並不停留在較小的列表中，它只適用於a-> a-> a類型的f。你可以用zipWith寫成它，如'levels（Nd a bs）= a：foldr（zipWith（++））（repeat []）（map levels bs）'並使用'takeWhile（not.null）$級樹'，但這可能只是愚蠢的。 :-) – ShreevatsaR 2010-04-28 19:45:39

你可以編寫一個'zipWith''版本，它可以通過將一對參數用作填充來處理不同的類型。 – sigfpe 2010-04-28 19:53:45

此解決方案不適用於完整抽象類型「樹a」 - 而zipWith的變體有點奇怪。 – MtnViewMark 2010-04-28 21:41:04

levels :: (Tree a) -> [[a]] 
levels (Nd x ts) = [[x]] ++ levelshelper ts 

level2 = (map concat).levels 

levelshelper :: [Tree a] -> [[a]] 
levelshelper [] = [] 
levelshelper xs = (map (\(Nd x ts) -> x) xs) : (levelshelper (extractl xs)) 

--get the next level's Nd's 
extractl :: [Tree a] -> [Tree a] 
extractl [] = [] 
extractl ((Nd x ts):xs) = ts ++ (extractl xs)

我的做法被證明是更有點笨拙的不是我想要的。但是，如果我錯了，請糾正我，因爲字符串是字符列表，但是您使用的是多態類型，是否真的很直接地將結果打印出來，就像問題中指定的一樣？此代碼生成字符串列表的列表。 ***道具克里斯在他更優雅的回答提醒我關於使用concat !!

來源

2010-04-28 19:41:13 thegravian

這是另一個版本，可以應用於Tree a而不是Tree [a]。

levelorder :: Tree a -> [[a]] 
levelorder (Nd x ts) = [x]:(ziplist (map levelorder ts)) 

ziplist :: [[[a]]] -> [[a]] 
ziplist l = if null ls then [] else (concat heads):(ziplist tails) 
    where 
     ls = filter (not.null) l 
     heads = map head ls 
     tails = map tail ls

如果你想連接在最後的字符串你可以使用：

levelorder2 :: Tree [a] -> [[a]] 
levelorder2 = (map concat).levelorder

來源

2010-04-28 19:45:00 Kru

我猜這是功課。假設它是，那麼這裏有一些關於如何思考可能會導致你回答的問題的想法：

在preorder中，首先將當前項目「報告」，然後對所有該節點的尾部遞歸。在postorder這兩個步驟是相反的。在這兩種情況下，遞歸都是「本地」的，因爲它只需要一次處理一個節點。這是否適用於levelorder？或者以另一種方式提出，levelorder遞歸時，執行遞歸的結果還是不相交？如果是這樣的話，遞歸的「單位」是什麼，如果不是一個Tree？

瞭解levelorder的遞歸（或迭代..?）的性質將使您找到一個非常簡單和優雅的解決方案。我的版本只有三行！

順便說一句，這可能是不錯的這些實用功能，使代碼，甚至在一些地方更清晰：

element :: Tree a -> a 
element (Nd x _) = x 
subtrees :: Tree a -> [Tree a] 
subtrees (Nd _ s) = s

或者，如果你熟悉哈斯克爾記錄語法，就可以實現準確這種通過改變你原來的Tree定義：

data Tree a = Nd { element :: a, subtrees :: [Tree a] } 
    deriving Show

完整的解決方案：

關鍵是認識到levelorder需要遞歸在Tree的列表上。在每一步從每個Tree元素被提取，並且下一步驟是在所述子樹的級聯：

levelorder :: Tree a -> [a] 
levelorder t = step [t] 
    where step [] = [] 
      step ts = map element ts ++ step (concatMap subtrees ts)

這產生在單一的元件的，扁平的列表，很像preorder和postorder做的，是廣度優先遍歷的通常定義。

相反，如果你真的想通過水平分組的元素，將++運營商到:一個變化將產生版本：

bylevel :: Tree a -> [[a]] 
bylevel t = step [t] 
    where step [] = [] 
      step ts = map element ts : step (concatMap subtrees ts)

注：我已經給定類型簽名所有頂級功能。這是一個非常好的習慣，並且可以節省您相當多的時間進行調試。

來源

2010-04-28 19:58:39 MtnViewMark

Haskell中的水平順序

回答

相關問題