Binary Tree Help

[TheJVM_1970]

Hi, how do i create a Binary Tree using nodes and stacks? I've created a stack interface, and a full and empty exception class but i'm now creating the TreeStack class to create the tree. It uses 3 complete levels, therfore 7 nodes and 7 stacks. Each stack limit is going to be set to maximum 10. I've created the methods and the arrays i think i'll need but i'm not sure how to create the tree itself. Here's the code i have done:

Stack.java:

public interface Stack {
  // accessor methods
  public int size(); //# return the number of elements stored in the stack
  public boolean isEmpty(); //# test whether the stack is empty
  public Object top() //# return the top elemet
     throws StackEmptyException; //# thrown if called on an empty stack
  // update methods
  public void push (Object element); //# insert an element onto the stack
  public Object pop() //# return and remove the top element of the stack
     throws StackEmptyException; //# thrown if called on an empty stack
}

StackEmptyException.java:

public class StackEmptyException extends RuntimeException {
  public StackEmptyException(String err) {
    super(err);
  }
}

StackFullException.java:

public class StackFullException extends RuntimeException {  
  public StackFullException(String err) {
    super(err);
  }
}

TreeStack.java

public class TreeStack{

	// Create Arrays

	// Max nodes needed is 7 (3 complete levels)
	BinaryTreeNodes[] bn = new BinaryTreeNodes[7];

	// Max stacks needed is 7 (3 complete levels)
	BinaryTreeStack[] bs = new BinaryTreeStack[7];

	// At each node a stack is created as required
	// i.e. the data structure is a tree of stacks.
	// Each stack only need to have a maximum capacity of 10.

	// Create Binary Tree
	BinaryTree[] b = new BinaryTree();

	public void input(){

	// Get user input


	public void printLevelOrder(){
	}

	public void printPopLevelOrder(){
	}

	public void printPopInorder(){
	}

	public void printPopPrerder(){
	}

	public void printPopRoot(){
	}

When attempting to run the program i want it to run by entering input like this:

java TreeStack
1 3 2 printLevelOrder printPopRoot
CONTROL-D (i.e. end of file)

Any help is much appreciated or if anyone knows where i can read up on this topic.

Thanks.

[evlich]

What exactly are you expecting for this program do do with the input that you show? Usually people use stacks and queues to traverse binary trees, but don't actually store the binary tree as a stack or queue, for instance, breadth first traversals are implemented using queues and depth-first traversals are implemented using stacks.

[Code_Nerd]

I have created a Binary Tree Node class.. It doesnt use stacks at each node, but I suppose you could alter it to do so...

public class BTNode 
{
    private Object data;
    private BTNode left, right;
    public BTNode(Object initialData, BTNode initialLeft, BTNode initialRight)
        { 
            data = initialData;
            left = initialLeft;
            right = initialRight;
        }
    public BTNode()
            { this(null, null, null); }
    
    public BTNode(Object newdata)
            { this(newdata, null, null); }
    
    //NODE methods
    public Object getData()                     //return and set data in node
            {return data;}
    
    public void setData(Object data)
            {this.data = data; }
    
    public BTNode getLeft()                 //return and set left child
            {return left; }
    
    public void setLeft(BTNode left)
            {this.left = left; }
    
    public BTNode getRight()                //return and set right child
            {return right; }
    
    public void setRight(BTNode right)
            {this.right = right; }
    
    public boolean isLeaf()                 //return true if this is leaf node
            {return (left == null)&&(right == null); }
 
// TREE Methods - for tree starting at this node
// get specific data from a tree
    
        public Object getLeftmostData()
        { if(left == null)
               return data;
          else 
              return left.getLeftmostData(); }
        
        public Object getRightmostData()
              { if(right == null)
               return data;
          else 
              return right.getRightmostData(); }
// print data in a tree
        public void inorderPrint()
                {
                    if (left != null)
                        left.inorderPrint( );
                    System.out.print(data+"\t");
                    if (right != null)
                        right.inorderPrint( ); }
        
        public void preorderPrint()
                {
                    System.out.print(data+"\t");
                    if (left != null)
                        left.preorderPrint( );
                    if (right != null)
                        right.preorderPrint( ); }
        
        public void postorderPrint()
                {
                    if (left != null)
                        left.postorderPrint( );
                    if (right != null)
                        right.postorderPrint( );
                    System.out.print(data+"\t"); }
        
// pretty print a tree
        //public void print(int depth);
 
//Interface for Nodes in Binary Tree (3)
//removing nodes from a tree
//returns reference to tree after removal of node
        public BTNode removeLeftmost()
              {
                    if (left == null)                               // we are as deep as we can get
                        return right;                               // remove this node by returning right subt ree
                    else
                        {                                           // keep going down recursively
                            left = left.removeLeftmost( );
                                                                    // when done, return node that act ivated this
                                                                    // method as root of t ree
                            return this; }}
        
        public BTNode removeRightmost()
        {
                    if (right == null)                               // we are as deep as we can get
                        return left;                               // remove this node by returning left subt ree
                    else
                        {                                           // keep going down recursively
                            right = right.removeRightmost( );
                                                                    // when done, return node that activated this
                                                                    // method as root of tree
                            return this; }}
//returns number of nodes in tree
        public static long treeHeight(BTNode root)
              {
                    if (root == null)
                        return -1;
                    else
                        return 1 + Math.max(treeHeight(root.left),
                                treeHeight(root.right)); 
              }
        
        public static long treeSize(BTNode root)
            {
                if (root == null)
                    return 0;
                else
                    return 1 + treeSize(root.left) + treeSize(root.right); 
            }
//copying a tree: returns reference to root of copy
        
       // public BTNode treeCopy(BTNode root);
        
    public static BTNode insertNode(BTNode root, int key){
            if (root == null) // null tree, so create node at root
                return new BTNode(new Integer(key));
            Integer data_element = (Integer) root.data;
            if (key <= data_element.intValue())
                root.setLeft(insertNode(root.left, key));
            else root.setRight(insertNode(root.right, key));
                return root; }
    
    public static BTNode findNode(BTNode root,int key){
            if (root == null)
                return null; // null tree
            Integer data_element = (Integer) root.data;
            if (key == data_element.intValue())
                return root;
            else
            if (key <= data_element.intValue())
                return findNode(root.left, key);
            else return findNode(root.right, key); }
    
    public static BTNode removeNode(BTNode root, int key){
            if (root == null) return null;
                Integer data_element = (Integer) root.data;
            if (key < data_element.intValue())
                root.setLeft(removeNode(root.left, key));
            else if (key > data_element.intValue())
                root.setRight(removeNode(root.right,key));
            else { // found it
            if (root.right == null) root = root.left;
                else if (root.left == null) root = root.right;
                    else {                                         //two children
                            Integer temp = (Integer)
                            root.left.getRightmostData();
                            root.setData(temp);
                            root.setLeft(root.left.removeRightmost()); 
                         }
                    }
            return root; }
    
    public static BTNode copyTree(BTNode bt){
            if (bt==null) return null;
                BTNode left=copyTree(bt.left);
            BTNode right=copyTree(bt.right);
                return new BTNode(bt.data,left,right); } 
    
    }