垂直和水平递归在树上

我在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

垂直和水平递归在树上

回答

相关问题