CODEWITHSUNDEEP
sml
user461316
user461316

Reputation: 913

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 smaller than root and right bigger). Just values from a list inserted at each node in a binary tree.

Upvotes: 1

Views: 1484

Answers (3)

Jesper.Reenberg
Jesper.Reenberg

Reputation: 5944

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

Upvotes: 1

Sebastian Paaske Tørholm
Sebastian Paaske Tørholm

Reputation: 50948

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))

Upvotes: 4

VoronoiPotato
VoronoiPotato

Reputation: 3183

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

Upvotes: -2

Related Questions