Нахождение самого левого узла в дереве в F # - PullRequest
Новая
       13

Нахождение самого левого узла в дереве в F #

0 голосов
/ 06 сентября 2018

Цель функции - найти и вернуть значение в крайнем левом узле дерева: 

type btree = Empty | Node of btree * int * btree

type finding = NotFound | Found of int

let s = Node (Node(Empty, 5, Empty), 3, Node (Empty, 6, Empty))
(*
     (3)
    /   \
  (5)    (6)
  / \    / \
 () () ()  ()

                *)

let rec leftmost t =
    match t with
    Node (t, _, _) -> leftmost t
    | _ -> failwith "Empty"


let n = leftmost s
printfn "Found %i" n

Вот так у меня сейчас есть мой код. Он каждый раз сталкивается с ошибкой пустого дерева. Я новичок в F #, и мне трудно понять, как реализовать случай, когда я нахожу самый левый узел. моя первоначальная мысль была 

   | (Empty, t, _) -> t

но я не нахожу успеха, любая помощь будет оценена. Спасибо.

1 Ответ

0 голосов
/ 06 сентября 2018

Вы почти у цели. Идея с охраной | (Empty, ) хороша. Если применяется в правильном положении, это работает: 

let rec leftmost t =
    match t with
    Node(Empty, n, _) -> n
    | Node (t, _, _) -> leftmost t
    | _ -> failwith "Empty"

Важной частью является то, что нам нужно остановиться на текущем узле t и вернуть его полезную нагрузку n, как только следующий левый потомок будет Empty.

Для полноты: я бы рекомендовал назвать левое поддерево иначе, чем текущий корень, и выровнять регистры: 

let rec leftmost t =
    match t with
    | Node(Empty, n, _) -> n
    | Node (l, _, _) -> leftmost l
    | _ -> failwith "Empty"

Также есть ярлык для let f x = match x with | P: let f = function | P, который избавляет от необходимости придумывать имя для параметра: 

let rec leftmost = function
    | Node(Empty, n, _) -> n
    | Node (l, _, _) -> leftmost l
    | _ -> failwith "Empty"
...