如何获得最小深度的叶子?
问题描述:
例如,我有这样的结构树如何获得最小深度的叶子?
let tr = Node(1,[Node(2,[Leaf(5)]);Node(3,[Leaf(6);Leaf(7)]);Leaf(4)])
我怎样才能用最小深度叶?
答
let minDepthLeaf tree =
let rec aux (depth: int) = function
| Leaf(_) as l -> (l, depth)
| Node(_, children) -> children |> List.map (aux (depth+1)) |> List.minBy snd
aux 0 tree |> fst
答
解决此问题的一种方法是实施Breadth-First Search算法。该算法在“levels”中遍历一棵树,以便返回根,然后返回根的所有孩子,然后返回这些孩子的所有孩子,等等。你可以把它写成一个返回序列的F#函数:
/// Breadth-first search over a tree
/// Takes list of initial nodes as argument
let rec breadthFirstSearch nodes = seq {
// Return all nodes at the current level
yield! nodes
// Collect all children of current level
let children = nodes |> List.collect (function
| Leaf _ -> [] | Node(_, c) -> c)
// Walk over all the children (next level)
if children <> [] then
yield! breadthFirstSearch children }
这对于各种树处理任务是非常有用的算法,所以它是有用的。现在,为了获得最低Leaf
,你可以随便挑序列中的第一Leaf
节点:
breadthFirstSearch [tr]
|> Seq.filter (function Leaf _ -> true | _ -> false)
|> Seq.head
我觉得这个方案是好的,因为它实现了一个更有用的功能可按,然后就用它来对解决您的具体问题三条线。
你需要代码或算法吗? –