Блог

Это проблема 65 в OCaml 99

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

Ось y узла проста, поскольку это просто номер уровня, начиная с 1.

X asix узла немного сложнее, но благодаря наблюдению, предполагая, что высота всего дерева равна h , тогда x узла — это максимальный размер левого дочернего элемента, как если бы это было полное дерево, т.Е., x = 2 ^ (h-y)-1

Однако существует особый случай, когда x самого левого узла всегда равно 1, который нам нужно обработать.

Вот мой код:

 type 'a btree = Empty | Node of 'a * 'a btree * 'a btree

type 'a pos_binary_tree =
  | E (* represents the empty tree *)
  | N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree

let rec height = function
  | Empty -> 0
  | Node (_,l,r) -> 1   max (height l) (height r)

let get_fullsize h level = (2. ** (Float.of_int (h 1-level)) |> Int.of_float) - 1

let layout_btree2_correct t = 
  let h = height t in
  let rec lay off y = function
    | Empty -> get_fullsize h y, E
    | Node (w, Empty, r) when off = 0 ->
      let wtr, newr = lay 1 (y 1) r in
      1 wtr, N (w, 1, y 1, E, newr)
    | Node (w, l, r) ->
      let wt1, newl = lay off (y 1) l in
      let wt2, newr = lay (off wt1 1) (y 1) r in
      wt1 wt2 1, N (w, off wt1 1, y, newl, newr)
  in 
  lay 0 1 t |> snd
 

Что я делаю, так это:

1. получить высоту всего дерева
2. всегда возвращайте всю ширину, которую он может занимать
3. x должно быть шириной левого узла 1
4. Для особого случая самого левого узла он возвращает ширину 1 справа в качестве ширины

По-моему, я должен сначала проехать по дереву один раз, чтобы определить высоту. Кто-нибудь может предложить лучшую реализацию, например, просто проехать по дереву один раз?

Вы запрашиваете разные алгоритмы для поиска в дереве? Или другие способы реализации этого алгоритма?

Раздел «Деревья и алгоритмы дерева» может быть вам полезен. http://interactivepython.org/runestone/static/pythonds/index.html