0 people like it.
Like the snippet!
Lab3
Lab3
Найти лист наименьшей глубины. *
Используем поиск в ширину. *
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
|
type 't tree = Leaf of 't | Node of 't*('t tree list)
let upper_leaf tree =
(* Шаг 1: поиском в глубину приписываем каждому узлу метку с его уровнем *)
let rec nodes_with_level tree level = match tree with
| Leaf(x) -> Leaf((x, level))
| Node(x, children) -> Node((x, level), (List.map (fun child -> nodes_with_level child (level+1)) children))
(* Шаг 2: поиском в ширину идем до самого "высокого" листа. *)
let rec bfs node_queue = match node_queue with
| h::t -> match h with
| Leaf((x, level)) -> (x, level); (* Нашли лист. Возвращаем tuple (значение, уровень) *)
| Node((x, level), children) -> bfs (t@children) (* Фигачим детей в конец листа, идем дальше *)
(* Запуск *)
bfs [(nodes_with_level tree 0)]
(* Samples *)
upper_leaf (Leaf(1))
upper_leaf (Node(1,
[Node(2,
[Node(3,
[Leaf(4)])
]);
Leaf(5)
])
)
upper_leaf (Node(1,
[Node(2,
[Node(3,
[Leaf(4)])]);
Node(5,
[Node(6,
[Leaf(7)])])
])
)
|
union case tree.Leaf: 't -> 't tree
union case tree.Node: 't * 't tree list -> 't tree
type 't tree =
| Leaf of 't
| Node of 't * 't tree list
Full name: Script.tree<_>
type 'T list = List<'T>
Full name: Microsoft.FSharp.Collections.list<_>
val upper_leaf : tree:'a tree -> 'a * int
Full name: Script.upper_leaf
Multiple items
val tree : 'a tree
--------------------
type 't tree =
| Leaf of 't
| Node of 't * 't tree list
Full name: Script.tree<_>
val nodes_with_level : ('b tree -> int -> ('b * int) tree)
Multiple items
val tree : 'b tree
--------------------
type 't tree =
| Leaf of 't
| Node of 't * 't tree list
Full name: Script.tree<_>
val level : int
val x : 'b
val children : 'b tree list
Multiple items
module List
from Microsoft.FSharp.Collections
--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member Head : 'T
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list
Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list
Full name: Microsoft.FSharp.Collections.List.map
val child : 'b tree
val bfs : (('b * 'c) tree list -> 'b * 'c)
val node_queue : ('b * 'c) tree list
val h : ('b * 'c) tree
val t : ('b * 'c) tree list
val level : 'c
val children : ('b * 'c) tree list
More information