The binary tree assignment requires you to implement the BinaryTreeADT interface using a linked representation in terms of an abstract class and two extensions of this class. It further requires that you write two little programs which make use of the extensions.

ADT

/*
 * BinaryTreeADT.java
 */

package datatypes.binarytree;

public interface BinaryTreeADT {
    public boolean emptyp();
    public int height();
    public void preorder();
    public void inorder();
    public void postorder();
    public void add(Object object, String dir);
    public boolean memberp(String key);
    public void visit();
    public String key();
    public void sprout(Object o);
}

Abstract Class

/*
 * BinaryTree.java
 */

package datatypes.binarytree.linked;

import java.util.*;
import datatypes.binarytree.*;

abstract public class BinaryTree implements BinaryTreeADT
{
    protected Object data;
    protected BinaryTree lchild;
    protected BinaryTree rchild;
    
    public BinaryTree()
    {
        data = null;
    }
    
    public boolean emptyp()
    {
        return ( data == null );
    }
    
    public int height()
    {
        if ( emptyp() ) {
            return 0;
        } else {
            return 1 + max(lchild.height(),rchild.height());
        }
    }
    
    private int max(int a, int b)
    {
        if ( a > b ) { return a; } else { return b; }
    }
    
    public void preorder()
    {
        if ( ! emptyp() ) {
            visit();
            lchild.preorder();
            rchild.preorder();
        }
    }
    
    public void inorder()
    {
        if ( ! emptyp() ) {
            lchild.inorder();
            visit();
            rchild.inorder();
        }
    }
    
    public void postorder()
    {
        if ( ! emptyp() ) {
            lchild.postorder();
            rchild.postorder();
            visit();
        }
    }

    public boolean memberp(String key)
    {
        if ( emptyp() ) {
            return false;
        } else if ( key().equals(key) ) {
            return true;
        } else {
            return ( lchild.memberp(key) | rchild.memberp(key) );
        }
    }
    
    public void add(Object object, String dir)
    {
        if ( dir.equals("") ) {
            sprout(object);
        } else if ( dir.substring(0,1).equalsIgnoreCase("L") ) {
            lchild.add(object,dir.substring(1));
        } else if ( dir.substring(0,1).equalsIgnoreCase("R") ) {
            rchild.add(object,dir.substring(1));
        } else {
            System.out.println("Error in add of BinaryTree!");
            System.exit(-1);
        }
    }
    
    abstract public void sprout(Object o);
    abstract public void visit();
    abstract public String key();
    
}

String Extention

/*
 * StringBinaryTree.java
 */

package datatypes.binarytree.linked;

import datatypes.binarytree.*;

public class StringBinaryTree extends BinaryTree
{
    public StringBinaryTree()
    {
        super();
    }

    public void sprout(Object o)
    {
        data = (String)o;
        lchild = new StringBinaryTree();
        rchild = new StringBinaryTree();
    }
  
    public void visit()
    {
        System.out.println(data.toString());
    }

    public String key()
    {
        return (String)data;
    }

}

Object Extention

/*
 * ObjectBinaryTree.java
 */

package datatypes.binarytree.linked;

import datatypes.binarytree.*;

public class ObjectBinaryTree extends BinaryTree
{
    public ObjectBinaryTree()
    {
        super();
    }

    public void sprout(Object o)
    {
        data = o;
        lchild = new ObjectBinaryTree();
        rchild = new ObjectBinaryTree();
    }
  
    public void visit()
    {
        System.out.println(data.toString());
    }

    public String key()
    {
        return (String)data;
    }

}

String Binary Tree Test Program and Demo

/*
 * StringBinaryTreeTest.java
 */

package testers;

import datatypes.binarytree.linked.*;

public class StringBinaryTreeTest {
    
    static public void main(String args[])
    {
        System.out.println(">>> creating empty tree");
        StringBinaryTree t = new StringBinaryTree();
        System.out.println(">>> adding elements to the tree");
        t.add("lion","");
        t.add("shark","r");
        t.add("elephant","l");
        t.add("zebra","rr");
        t.add("alligator","ll");
        t.add("ardvaark","llr");
        t.add("tiger","rrl");
        t.add("giraffe","lr");
        t.add("bear","llrr");
        t.add("snake","rrll");
        System.out.println("\n>>> PREORDER");
        t.preorder();
        System.out.println("\n>>> INORDER");
        t.inorder();
        System.out.println("\n>>> POSTORDER");
        t.postorder();
        System.out.println("\n>>> HEIGHT = " + t.height());
    }
}

init:
deps-jar:
compile-single:
run-single:
>>> creating empty tree
>>> adding elements to the tree

>>> PREORDER
lion
elephant
alligator
ardvaark
bear
giraffe
shark
zebra
tiger
snake

>>> INORDER
alligator
ardvaark
bear
elephant
giraffe
lion
shark
snake
tiger
zebra

>>> POSTORDER
bear
ardvaark
alligator
giraffe
elephant
snake
tiger
zebra
shark
lion

>>> HEIGHT = 5
BUILD SUCCESSFUL (total time: 1 second)

Questions

1. What is an abstract class?