Java Data Structures - Contents
A D V E R T I S E M E N T
Reading and writing binary trees to/from files is
not as simple as reading and writing arrays. They're not linear, and require some
algorithm to accomplish the task.
One simple approach would be to convert the tree to
a node-pool one, and simply save the node-pool, and the first node (or something along
those lines). That's the approach taken by lots of programs in saving trees. Actually,
most programs implement the tree as a node-pool from the start, so, the whole thing is
much simpler.
But what do you do when you're not using node-pools,
but would still like to save the tree (and it's structure)? You can use a technique known
as serialization.
There are many ways of serializing a binary tree,
and incidentally, I've lost the "formal algorithm," so, I'll re-derive
it again, maybe in a little bit different form. The basic idea is to first write the size
of data inside the node, and then the data itself. If there is no data you write zero, and
return (without writing the data). If you've written any data, you then recursively write
the left and right children of that node. There can be many variations of this; the most
obvious is switching the order of left and right child.
The reading process has to know the way in which the
tree was written. It has to first read the size of the data, if the size is zero, it sets
the pointer to null, and returns. If the size is not zero, it allocates a new node in the
tree, and reads the data into that node. Then, it recursively, reads the left and then the
right children for that node.
This simple algorithm is very effective, and can be
used to read and write data of different sizes (i.e.: character strings). The explanation
of it may not be too clear at first; that's why I've written some source to clear up the
confusion. The source that follows creates a binary tree holding strings, saves the tree
to a file, and later reads that file.
import java.lang.*;
import java.io.*;
public class pBinTreeStringWR{
public pBinTreeStringWR left,right;
public String data;
public static String[] strings = {"one","two",
"three","four","five","six","seven","eight",
"nine","ten","zero","computer","mouse","screen",
"laptop","book","decimal","binary","quake"};
public static pBinTreeStringWR tree_AddString(
pBinTreeStringWR r,String s){
if(r == null){
r = new pBinTreeStringWR();
r.left = r.right = null;
r.data = s;
}else if(r.data.compareTo(s) < 0)
r.right = tree_AddString(r.right,s);
else
r.left = tree_AddString(r.left,s);
return r;
}
public static void tree_InOrderPrint(
pBinTreeStringWR r){
if(r != null){
tree_InOrderPrint(r.left);
System.out.print(" "+r.data);
tree_InOrderPrint(r.right);
}
}
public static void tree_FileWrite(
pBinTreeStringWR r,
DataOutputStream output) throws IOException{
if(r != null){
byte[] tmp = r.data.getBytes();
output.writeInt(tmp.length);
output.write(tmp);
tree_FileWrite(r.left,output);
tree_FileWrite(r.right,output);
}else
output.writeInt(0);
}
public static pBinTreeStringWR tree_FileRead(
pBinTreeStringWR r,
DataInputStream input) throws IOException{
int n = input.readInt();
if(n != 0){
byte[] tmp = new byte[n];
input.read(tmp);
r = new pBinTreeStringWR();
r.data = new String(tmp);
r.left = tree_FileRead(r.left,input);
r.right = tree_FileRead(r.right,input);
}else
r = null;
return r;
}
public static boolean tree_Compare(
pBinTreeStringWR a,pBinTreeStringWR b){
if(a != null && b != null){
return a.data.compareTo(b.data) == 0 &&
tree_Compare(a.left,b.left) &&
tree_Compare(a.right,b.right);
}else if(a == null && b == null)
return true;
else
return false;
}
public static void main(String[] args){
File file = new File("pBinTreeStringWR.dat");
pBinTreeStringWR read_tree = null,tree = null;
System.out.print("inserting: ");
for(int i=0;i<strings.length;i++){
String s = new String(strings[i]);
System.out.print(" "+s);
tree = tree_AddString(tree,s);
}
System.out.print("\ntree: ");
tree_InOrderPrint(tree);
System.out.println("\nwriting to "+file);
try{
tree_FileWrite(tree,
new DataOutputStream(
new FileOutputStream(file)));
}catch(IOException e){
System.out.println(e);
}
System.out.println("reading from "+file);
try{
read_tree = tree_FileRead(read_tree,
new DataInputStream(
new FileInputStream(file)));
}catch(IOException e){
System.out.println(e);
}
System.out.print("read tree: ");
tree_InOrderPrint(read_tree);
if(tree_Compare(tree,read_tree))
System.out.println(
"\nThe two trees are identical.");
else
System.out.println(
"\nThe two trees are different.");
System.out.println("done ;-)");
}
}
The program both illustrates the algorithm and tests
it. pBinTreeStringWR class is itself a node. These nodes are manipulated
using static methods. I did it this way to reduce the number of needed
classes (combining the program class with the node class).
In the program, we start out by creating a File
object with the file we're about to write and read. We then declare two trees, one named tree,
the other named read_tree. We then loop to add static strings to
the tree. The add function adds them in a binary search tree fashion; it is
using the Comparable interface to do the comparisons.
Then we open a file, create a DataOutputStream
object to that file, and write the tree to that file using tree_FileWrite()
function. This tree_FileWrite() closely matches the algorithm described
earlier. If the node is not null, it writes the length of the String,
and then the String itself (converted to bytes). It then
recursively writes the left and right children of that node. If
the node is initially null, the function simply writes a zero for the length,
and returns.
The program continues by reading that file it has
just written. It stores the read tree in read_tree variable. The writing
process, tree_FileRead() also closely matches the algorithm described
earlier. It is basically the opposite of writing algorithm. We first read the length
of the String, if it's zero, we set the node to null, and
continue on. If the length is not zero, we read that number of bytes,
and store them in that node's data String. We then continue
recursively by reading the left and right children of that tree.
The program then calls a compare function, which
compares the trees (including the tree structure). Tests indicate that the program is
working correctly, since the test function always returns that the tree written, and the
tree read are identical. In the middle of all this, there is an in-order print function,
but I don't think I need to describe it since I assume you know the basics of trees.
(Basically, go over the source and you'll understand the whole thing.) The output from the
program follows.
inserting: one two three four five six seven eight
nine ten zero computer mouse screen laptop book decimal binary quake
tree: binary book computer decimal eight five four laptop mouse
nine one quake screen seven six ten three two zero
writing to pBinTreeStringWR.dat
reading from pBinTreeStringWR.dat
read tree: binary book computer decimal eight five four laptop
mouse nine one quake screen seven six ten three two zero
The two trees are identical.
done ;-)
Another useful trick that you can use when you are
not reading or writing variable length data like strings is not to write the length,
but simply some marker. For example, lets say your tree holds integers, and you know all
integers are 32 bits. Thus, your length parameter can simply be
a boolean value of whether there exists a next node or not. The next example
illustrates this by storing a boolean value instead of the length
parameter.
import java.lang.*;
import java.io.*;
public class pBinTreeIntegerWR{
public pBinTreeIntegerWR left,right;
public Integer data;
public static pBinTreeIntegerWR tree_AddNumber(
pBinTreeIntegerWR r,Integer n){
if(r == null){
r = new pBinTreeIntegerWR();
r.left = r.right = null;
r.data = n;
}else if(r.data.compareTo(n) < 0)
r.right = tree_AddNumber(r.right,n);
else
r.left = tree_AddNumber(r.left,n);
return r;
}
public static void tree_InOrderPrint(
pBinTreeIntegerWR r){
if(r != null){
tree_InOrderPrint(r.left);
System.out.print(" "+r.data);
tree_InOrderPrint(r.right);
}
}
public static void tree_FileWrite(
pBinTreeIntegerWR r,
DataOutputStream output) throws IOException{
if(r != null){
output.writeBoolean(true);
output.writeInt(r.data.intValue());
tree_FileWrite(r.left,output);
tree_FileWrite(r.right,output);
}else
output.writeBoolean(false);
}
public static pBinTreeIntegerWR tree_FileRead(
pBinTreeIntegerWR r,
DataInputStream input) throws IOException{
if(input.readBoolean()){
r = new pBinTreeIntegerWR();
r.data = new Integer(input.readInt());
r.left = tree_FileRead(r.left,input);
r.right = tree_FileRead(r.right,input);
}else
r = null;
return r;
}
public static boolean tree_Compare(
pBinTreeIntegerWR a,pBinTreeIntegerWR b){
if(a != null && b != null){
return a.data.compareTo(b.data) == 0 &&
tree_Compare(a.left,b.left) &&
tree_Compare(a.right,b.right);
}else if(a == null && b == null)
return true;
else
return false;
}
public static void main(String[] args){
File file = new File("pBinTreeIntegerWR.dat");
pBinTreeIntegerWR read_tree = null,tree = null;
System.out.print("inserting: ");
for(int i=0;i<10;i++){
Integer n = new Integer((int)(Math.random()*100));
System.out.print(" "+n);
tree = tree_AddNumber(tree,n);
}
System.out.print("\ntree: ");
tree_InOrderPrint(tree);
System.out.println("\nwriting to "+file);
try{
tree_FileWrite(tree,
new DataOutputStream(
new FileOutputStream(file)));
}catch(IOException e){
System.out.println(e);
}
System.out.println("reading from "+file);
try{
read_tree = tree_FileRead(read_tree,
new DataInputStream(
new FileInputStream(file)));
}catch(IOException e){
System.out.println(e);
}
System.out.print("read tree: ");
tree_InOrderPrint(read_tree);
if(tree_Compare(tree,read_tree))
System.out.println(
"\nThe two trees are identical.");
else
System.out.println(
"\nThe two trees are different.");
System.out.println("done ;-)");
}
}
The program above is almost identical to the one
before, except it stores java.lang.Integer objects instead of java.lang.String
objects. Since both of these implement java.lang.Comparable interface,
the functions look pretty much the same. The only functions which look different are the
file reading and writing. You should quickly notice that no length parameter
is involved, but a simple boolean value telling us whether there exists a
next node. Output from the program above follows:
inserting: 29 59 25 16 32 43 68 32 8 43
tree: 8 16 25 29 32 32 43 43 59 68
writing to pBinTreeIntegerWR.dat
reading from pBinTreeIntegerWR.dat
read tree: 8 16 25 29 32 32 43 43 59 68
The two trees are identical.
done ;-)
The funny thing that I always save till the end is
that in practice, you'll probably never use any of these approaches yourself. Java
provides a fairly useful java.io.Serializable interface, which given a tree,
will nicely store it into a file. Anyway, it does pay to know how these kinds of things
are done...
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
