垂直和水平遞歸在樹上

我在Haskell樹數據結構：垂直和水平遞歸在樹上

data MultTree b = DataNode b | IndexNode Int Int [MultTree b] deriving (Show)

的任務是，返回hightest多家分公司存在於樹（所以最長列表的基數的IndexNode）。

爲了實現這個目標我已經寫了一個功能：

grad :: MultTree t -> Int 
grad DataNode _  = 0 
grad IndexNode _ _ [] = 0 
grad IndexNode _ _ (x:xs) 
       | isIndexNodeCheck x = max ((countList (x:xs)) (grad x))

問：我怎樣才能實現這一功能並不僅僅下潛更深樹平，而且還檢查的xs下一個元素？如果編寫另一個守衛，代碼將不會運行，因爲Haskell總是採用匹配的第一個模式。

因此，目前該功能應該適用於垂直遞歸，但我想知道如何水平執行此操作。

這裏是我的完整代碼：

data MultTree b = DataNode b | IndexNode Int Int [MultTree b] deriving (Show) 

t2 :: MultTree Int 
t2 = IndexNode 3 42 [IndexNode 7 8 [DataNode 3, DataNode 5, DataNode 7], DataNode 6, IndexNode 10 23 [DataNode 99, DataNode 78, DataNode 24]] 

countList :: [a] -> Int 
countList [] = 0 
countList (x:xs) = 1 + countList xs 

isIndexNodeCheck :: MultTree a -> Bool 
isIndexNodeCheck (DataNode _) = False 
isIndexNodeCheck (IndexNode _ _ _) = True 

grad :: MultTree t -> Int 
grad DataNode _  = 0 
grad IndexNode _ _ [] = 0 
grad IndexNode _ _ (x:xs) 
       | isIndexNodeCheck x = max ((countList (x:xs)) (grad x))

來源

2017-02-03 jublikon

閱讀關於DFS和BFS。 –

這個有用的建議如何？我們不是在搜索任何東西，而是在遍歷，而我們是否在廣度優先或者深度優先的情況下做這些並不能改變正確性。 – amalloy

@amalloy DFS =「垂直遞歸」。 BFS = 「水平」。所以至少有正確的術語是有幫助的。而BFS是我認爲OP實際上正在尋找的東西。 –

下面是獲得最大的分支因子的解決方案：

grad :: MultTree a -> Int 
grad (DataNode _) = 0 
grad (IndexNode _ _ subtrees) = 
    -- take the maximum of this tree and of the 
    -- maximum branching factor of all subtrees 
    maximum (length subtrees : map grad subtrees)

的關鍵是，我得到使用map每個子樹的grad。

來源

2017-02-03 22:24:47 adamse

垂直和水平遞歸在樹上

回答

相關問題