Filling a normal binary tree in ML with values

Where let's say:

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

How would I go about filling a binary tree (not a binary search tree where left is sma开发者_运维问答ller than root and right bigger). Just values from a list inserted at each node in a binary tree.

---

You use the value constructors you've declared.

If we assume for a moment that value is int instead, then we for instance have that the tree

     1
    / \
   2   4
  /
 3

is represented by:

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

Or, equivalently, on one line:

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

---

It's not really possible to help you, without knowing more about how you wan't your tree constructed from a given list. However here is an example that creates a balanced tree. It takes the first element and uses it as the node value, and then it splits the rest of the list into two sub lists of equal size (if possible), by taking all "even" element in the "left" list and all "odd" elements in the "right" list:

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

The result:

- 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

---

Here is an answer to the same question done in Java. This will probably help a good bit :).