Заполнение нормального двоичного дерева в ML значениями

Question

Где скажем:

datatype bin_tree = Empty |
                    Node of value * bin_tree * bin_tree

Как бы я заполнил бинарное дерево (а не бинарное дерево поиска, где слева меньше корня, а справа больше). Просто значения из списка, вставленного в каждый узел двоичного дерева.

Answer 1

Вы используете объявленные вами конструкторы значений.

Если мы на мгновение предположим, что value равно int, то, например, у нас есть дерево

     1
    / \
   2   4
  /
 3

представляется как:

Node (1,
    Node (2,
        Node (3, Empty, Empty),
        Empty
    ),
    Node (4, Empty, Empty)
)

или, что то же самое, в одной строке:

Node (1, Node (2, Node (3, Empty, Empty), Empty), Node (4, Empty, Empty))

Answer 2

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

datatype 'a bin_tree = Empty
                  | Node of 'a * 'a bin_tree * 'a bin_tree

fun list_split xs =
    let
      fun loop [] (left, right) = (rev left, rev right)
        | loop (x::y::xs) (left, right) = loop xs (x :: left, y :: right)
        | loop (x :: xs) (left, right) = loop xs (x :: left, right)
    in
      loop xs ([], [])
    end

fun built_tree [] = Empty
  | built_tree (x :: xs)  =
    let
      val (left, right) = list_split xs
      val left_tree = built_tree left
      val right_tree = built_tree right
    in
      Node (x, left_tree, right_tree)
    end

Результат:

- built_tree [1,2,3,4,5,6,7,8,9];
val it =
  Node
    (1,Node (2,Node (4,Node (8,Empty,Empty),Empty),Node (6,Empty,Empty)),
     Node (3,Node (5,Node (9,Empty,Empty),Empty),Node (7,Empty,Empty)))
  : int bin_tree

Answer 3

Вот ответ на тот же вопрос, сделанный на Java. Это, вероятно, поможет немного :).