Помощь в работе с бинарными деревьями в SML - PullRequest
Новая
       62

Помощь в работе с бинарными деревьями в SML

0 голосов
/ 22 октября 2019

Я новичок в SML и хотел бы получить некоторую помощь в использовании следующей реализации двоичного дерева. 

datatype tree = NODE of int * tree * tree | LEAF of int;

Я вижу, что дерево определяется либо узлами, имеющими два поддерева, либоLEAF с целым числом.

Как я могу получить доступ к поддеревьям, чтобы я мог определить максимум, минимум и наличие элемента в дереве?

Каков процессдоступ к левому и правому поддеревьям?

1 Ответ

0 голосов
/ 22 октября 2019

Как происходит доступ к левому и правому поддеревьям?

Используется сопоставление с образцом: 

fun goLeft (NODE (_, l, _)) = l
  | goLeft LEAF = raise Fail "Cannot go left here!"

fun goRight (NODE (_, _, r)) = r
  | goRight LEAF = raise Fail "Cannot go right here!"

Как я могу [...] определить максимум, минимум и, если элемент присутствует в дереве?

Вы строите рекурсивные функции, которые соответствуют шаблону на поддеревьях.

Например, в двоичном дереве нет инварианта, который говорит о том, что минимальный элемент имеет фиксированное, известное местоположение в дереве. Но этот инвариант присутствует в двоичном дереве search , в котором все элементы в каждом левом поддереве (включая корень) должны быть уверены, что они меньше или равны всем элементам их правого поддерева. деревья.

Дерево 

    5
   / \
  3   8
 /   / \
2   7   9

квалифицируется как двоичное дерево поиска, потому что этот инвариант имеет место.

Найти минимальный элемент в таком дереве означает рекурсию таким образомчто вы всегда выбираете левое поддерево, пока не останется левое поддерево, и в этом случае вы нашли минимум. Как вы знаете, когда остановить рекурсию? 

fun goLeeeft (NODE (_, l, _)) = goLeeeft l
  | goLeeeft LEAF = "I've gone all the way left, but I have nothing to show for it."

fun minimum (NODE (x, l, r)) = (* is this the last non-leaf node? *)
  | minimum LEAF = raise Empty (* whoops, we recursed too far! *)

Когда вы соответствуете шаблону на глубину на один уровень, то есть на NODE (x, l, r), вы знаете только, что это не листовой узел, но вы нене знаю точного значения, расположенного в узле, x, и вы ничего не знаете о подструктуре левого и правого поддеревьев этого узла.

Здесь можно пойти двумя путями:создайте вспомогательную функцию, которая сообщит вам, когда прекратить повторение, или сопоставьте шаблон на один уровень глубже с l. Вот два примера этого;они выполняют одно и то же: 

(* Using a helper function *)
fun isLeaf (NODE (_, _, _)) = false
  | isLeaf LEAF = true

fun minimum (NODE (x, l, _)) =
      if isLeaf l
      then x
      else minimum l
  | minimum LEAF = raise Empty

(* Using direct pattern matching *)
fun minimum (NODE (x, LEAF, _)) = x
  | minimum (NODE (x, l, _)) = minimum l
  | minimum LEAF = raise Empty

Теперь maximum пишет сам.

В качестве любопытства вы можете определить общие схемы рекурсии, такие как свертывание на деревьях: Sml сворачиваниедерево

...