2016-06-11 203 views
0

這是我的理念爲指導:打印出二叉樹

data BinTree α = Empty 
    | Node (BinTree α) α (BinTree α) 
    deriving (Eq, Show) 

現在我想創建一個函數:

levels :: BinTree a -> [[a]] 

這應該打印出二叉樹的名單,但每個級別的它自己的。例如:[[1],[2,3],[4,5,6,7]]

[1] 
[2,3] 
[4,5,6,7] 

...

我所定義的rootschilds

roots ts = [ a | Node _ a _ <- ts ] 
childs ts = [ t | Node l _ r <- ts, t <- [l, r] ] 

和橫動功能,其獲取子樹和其節點的列表。

traverse' :: [BinTree α] -> [α] 
traverse' [] = [] 
traverse' ts = roots ts ++ traverse' (childs ts) 

levels :: BinTree α -> [α] 
levels t = traverse [t] 

但那不是我真正想要的。有人有一個想法。

+0

嘗試編寫'f :: BinTree a - > [[a]]',它將二叉樹轉換爲列表列表,其中第一個列表包含根目錄,第二個列表包含子目錄,其次是孫子目錄等等。之後你幾乎完成了。 – ThreeFx

+0

否則看看[這](http://stackoverflow.com/questions/12556469/nicely-printing-showing-a-binary-tree-in-haskell?rq=1)的問題,它可能有助於設計功能。 – ThreeFx

+0

考慮如何以左右子節點的級別表示節點的級別。你有沒有被介紹過'zip'函數? – ErikR

回答

1

這工作得很好:

f Empty = [] 
f (Node l v r) = case (f l, f r) of 
        ((x:xs),(y:ys)) -> [[v],x++y] ++ (zipWith (++) xs ys) 
        ([],[])   -> [[v]] 
        ...... 

完成的模式。 (你可以用一棵完整的樹來測試它,以確保它是一個好的開始)。