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

Raw view Test code New version

More information

Link:	http://fssnip.net/b2
Posted:	12 years ago
Author:	Mikhail Dubov
Tags:	lab3