Binary Tree Help


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Binary Tree Help

  1. #1
    Join Date
    Nov 2005
    Posts
    2

    Binary Tree Help

    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:
    Code:
    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:
    Code:
    public class StackEmptyException extends RuntimeException {
      public StackEmptyException(String err) {
        super(err);
      }
    }
    StackFullException.java:
    Code:
    public class StackFullException extends RuntimeException {  
      public StackFullException(String err) {
        super(err);
      }
    }
    TreeStack.java
    Code:
    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.

  2. #2
    Join Date
    Aug 2003
    Posts
    313
    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.
    ~evlich

  3. #3
    Join Date
    Aug 2005
    Location
    Melbourne...Australia
    Posts
    279
    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...
    Code:
    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); } 
        
        }

Similar Threads

  1. Changing targets in XML Tree
    By jdnyc in forum XML
    Replies: 0
    Last Post: 11-07-2005, 02:48 AM
  2. Directional help
    By Code_Nerd in forum Java
    Replies: 0
    Last Post: 10-18-2005, 04:46 AM
  3. Dynamic tree view control
    By anbaz in forum ASP.NET
    Replies: 2
    Last Post: 06-15-2005, 09:09 PM
  4. Serialization in Binary Tree
    By diva_thilak in forum Java
    Replies: 0
    Last Post: 02-21-2005, 03:47 AM
  5. Binary Search Tree implementation
    By Liza in forum Java
    Replies: 0
    Last Post: 10-23-2001, 11:21 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center