Assignment #1: Binary tree representation of an ordered forest

Programming Part

We discussed in class the "natural correspondence" between binary trees and ordered forests. We can also represent binary trees (and hence ordered forests) as binary strings. The binary string is obtained by traversing a binary tree in preorder, recording a 1 for every node and a 0 for every empty subtree (null link).

In this assignment you will write a program that takes as input a binary string representing the binary tree representation of an ordered forest and produces the binary string that represents the binary tree that represents the ordered forest that one obtains by looking at the forest in a vertically aligned mirror. Hence we will call it the mirror of the ordered forest.

In the example below the original forest is on the left and the mirrored forest is on the right; the input string is 1101100011000, and the output string is 1100111001000.

o o o o
/ \ | | / \
o o o <==== o o o
| |
o o
Binary trees in this assignment will have nodes from the class BT, shown below.

class BT {
BT L; BT R;
BT( BT l, BT r ) { L = l; R = r; }
}
You will fill in the code into the template shown below.
preord produces the 0/1 string from the binary tree.
toString outputs, on two lines, the 0/1 string from tree and the 0/1 string from mirror.
clone clones a binary tree.
mirrorTree(t) creates the binary tree of the mirrored forest corresponding to t. It can do this by modifying the tree (hence the call to clone in the constructor). It should run in time linear in the number of nodes in the tree. It is possible to write this code in the classic binary tree style, with a single call to the left subtree, a single call to the right subtree, and no loops, just the recursion.
public class MirrorTree {

public BT tree, mirror; // A tree and its mirror

private char[] a; // 0/1 array for tree
private int k; // used by build()

MirrorTree( String s ) {
a = s.toCharArray();
k = -1;
tree = build();
mirror = mirrorTree( clone( tree ) );
}

BT build() { return( a[++k] == '0' ? null : new BT( build(), build() )); }

public String preord ( BT t ) { } // FILL IN THE CODE.

public String toString() {} // FILL IN THE CODE.

public BT clone( BT t ) {} // FILL IN THE CODE.

public BT mirrorTree( BT t ) {} // FILL IN THE CODE.

// YOU CAN OMIT MAIN OR NOT. USE IT FOR TESTING.
public static void main ( String[] args ) {
MirrorTree mt = new MirrorTree( args[0] );
System.out.println( mt+"\ntree and mirror" );
System.out.println( new MirrorTree( mt.preord( mt.mirror ) ) ); // sanity check
}
}
The "sanity check" takes the "mirror" string and mirrors again. The first and last strings should be the same in all cases. For an example of a run using the above code:
C:\Users\Frank\CSC 226java MirrorTree 11011000101101010000
1101100010110101000
1101010010111001000
tree and mirror
1101010010111001000
1101100010110101000
What to turn in: Submit a file MirrorTree.java. Do not include the class BT. Testing will be automated. You will receive zero marks if you code does not compile. You may assume that the input is valid. Your code will also be judged on its efficiency. If your algorithms run correctly in time linear in the number of nodes in the tree then you should receive full marks.

Written part:

How many rooted trees are there with 5 nodes? Draw them.
In the code for build given in above, as a function of nn, the number of 11s in the input string, (a) how many times is k incremented? (b) how many times is build() called in total (including the initial call)?
Exercise 1.5.4 from the book.
Exercise 1.5.9 from the book.
Draw a Huffman's tree for the frequencies 2,3,5,7,11,13,17,19,23,29,31,37,41. Compute for this tree the average number of bits used per character used in the encoding.