Add to Favorites    Make Home Page 5614 Online  
 Language Categories  
 Our Services  

Java Data Structures - Contents


Reading and Writing Trees (Serialization)...

A D V E R T I S E M E N T

Search Projects & Source Codes:

    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




Google Groups Subscribe to SourceCodesWorld - Techies Talk
Email:

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

 Advertisements  

Google Search

Google

Source Codes World.com is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions | Important Websites
Copyright ©2003-2024 SourceCodesWorld.com, All Rights Reserved.
Page URL: http://www.sourcecodesworld.com/articles/java/java-data-structures/Reading_and_Writing_Trees.asp


Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review