Semester 2 Week 2 Binary Trees

  1. Consider the Hope implementation of binary trees. Implement binary trees in Java.

    data binaryTree(alpha) == emptyTree ++ consbinaryTree(alpha # binaryTree(alpha) # binaryTree(alpha));
    root:binaryTree(alpha) -> alpha; 
    root(consbinaryTree(x,y,z)) <= x;
    left:binaryTree(alpha) -> binaryTree(alpha); 
    left(consbinaryTree(x,y,z)) <= y;
    right:binaryTree(alpha) -> binaryTree(alpha); 
    right(consbinaryTree(x,y,z)) <= z;
    isEmpty:binaryTree(alpha) ->bool; 
    isEmpty(emptyTree) <= true;
    isEmpty(consbinaryTree(x,y,z)) <= false;
    max:num # num -> num;
    max(x,y) <= if x>y then x else y;
    depth:binaryTree(alpha) -> num; 
    depth(emptyTree) <= 0;
    depth(consbinaryTree(x,y,z)) <= 1 + max(depth(y),depth(z));

  2. (Easy Assignment) Below is a Hope function make for converting a list of numbers into a binary search tree of numbers. Implement this as a static method in Java and write some Java to test your method.

    insert: num # binaryTree(num) -> binaryTree(num);
    insert (n, emptyTree) <= consbinaryTree(n,emptyTree,emptyTree);
    insert (n,consbinaryTree(roo,lef,rig)) <= if n < roo 
    					  then consbinaryTree(roo, insert(n,lef),rig)
                                              else consbinaryTree(roo, lef, insert(n,rig));
    Main-Class: hangmanGUI3
    make :list(num) -> binaryTree(num);
    make(nil) <= emptyTree;
    make(x::m) <=  insert(x,make(m));

  3. (Hard Assignment) A balanced binary tree is either empty or a tree where the number of nodes in the left and right subtrees differs by at most one and the left and right subtrees are balanced.

    Write a method in Java which takes a list of numbers and produces a balanced binary search tree containing exactly those numbers.
Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2015-09-04