0 people like it.

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
Raw view Test code New version

More information

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