f# - 最小の深さの葉を取得するにはどうすればよいですか？

Question

たとえば、私はそのような構造を持つ木を持っています

let tr = Node(1,[Node(2,[Leaf(5)]);Node(3,[Leaf(6);Leaf(7)]);Leaf(4)])

最小の深さの葉を取得するにはどうすればよいですか？

Answer 1

この問題に対する 1 つのアプローチは、幅優先探索アルゴリズムを実装することです。このアルゴリズムは、ツリーを「レベル」でたどって、ルート、ルートのすべての子、それらの子のすべての子などを返します。これは、シーケンスを返す 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

このソリューションは、より便利な関数を実装し、それを使用して特定の問題を 3 行で解決するため、優れていると思います。

Answer 2

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