University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677: Design and Analysis of Algorithms
Programming Problem: File Representation of a Binary Tree
Revised October 16, 2005.
A binary tree can be represented as a file of data in
preorder together with a guide string.
A guide string is a string of 2n+1 bits, where n
is the number of nodes in the tree. If the binary tree is empty,
the guide string is 0. Otherwise, the guide string
is 1 followed by the guide string of
the left subtree followed by the guide string of the right subtree.
-
Write a program that has a binary tree data type, where each item
is a string of length 3.
-
Your program should be able to input a binary tree from two files,
one holding the data, the other the guide string.
-
Your program should be able to write two files representing a
binary tree.
-
It is possible to interleave the guide string with the data in
a single file. In this case, the initial symbol
of the guide string is omitted.
-
Here is a run of my program.
Here are the data file and
guide string written by my program.
These were not simply copied from the input files.
The input files were used to build a binary tree, which was then
used to write the output files.
For those of you who are taking, or who have taken, CS 456 or
the equivalent, the language of guide strings has the following
unambiguous context-free grammar whose start symbol is T:
-
T -> 0
-
T -> 1TT
If you draw the parse tree for a guide string using this grammar,
and also draw the binary tree whose shape it encodes,
you will see how it works. In fact, the guide string is its own
leftmost derivation!