Results 1 to 9 of 9

Thread: Binary Tree

  1. #1
    MuslimCoder is offline Senior Member
    Join Date
    Jan 2009
    Posts
    119
    Rep Power
    0

    Default Binary Tree

    Hello,

    we were taught some binary tree, I am thinking of creating my own...
    though I am not sure if I am getting it right...


    Node.java
    Java Code:
    //  This is a node class that should be used in a binary tree
    
    public class Node
    {
     
      
      Object data; //stores the data in the node
      Node parent; //stores the predecessor 
      Node left; // Left node
      Node right; //right node
      
      public Node()
      {
        data = null;
      }
      public Node(Object d)
      {
        setData(d);
      }
      public Node(Node l, Node p, Object d, Node r )
      {
            
        setLeft(l);
        setRight(r);
        setData(d);
        setParent(p);
      }
      
      //sets the left node
      public void setLeft(Node l)
      {
        left = l;
      }
      //returns the left node
      public Node getLeft()
      {
        return left;
      }
      //sets the right node 
      public void setRight(Node r)
      {
        right = r;
      }
      //returns the right node
      public Node getRight()
      {
        return right;
      }
      //sets the parent of the current node
      public void setParent(Node p)
      {
        parent = p;
      }
      //returns the parent node
      public Node getParent()
      {
      
        return parent;
      }
      //sets the content of the node
     public void setData(Object d)
     {
       data= d;
       
     }
     //returns the content of the node
     public Object getData()
     {
       return data;
     }
     //retuns true on false depending on whether the node has a left child
     public boolean hasLeftChild()
     {
     	if (left == null)
     		return false;
     	else
     		return true;
     		
     }
     //returns true or false depending on whether the node has a right child
     public boolean hasRightChild()
     {
     	if(right == null)
     		return false;
     	else
     		return true;
     	
     }
     	
    //returns true or false depending on whether the node has a child
     public boolean hasChild()
     {
     	//if there is atleast one child, then it is ok
     	if(hasLeftChild() || hasRightChild() == true)
     		return true;
     	else
     		return false;
     	
     	
     }
     //returns true if the node has parent, else it returns false
     public boolean hasParent()
     {
     	
     		if(parent == null)
     			return false;
     		else
     			return true;
     }
     //adds a left child
     public void addLeft(Node l)
     {
     	left = l;
     		
     }
     //adds a right child
     public void addRight(Node r)
     {
     	right = r;
     }
     //adds a child to the tree, left by deafault
     public void addChild(Node n)
     {
     	//if the node already has a left child then add to the right else add to the left node
     	if(hasLeftChild())
     	{
     		addRight(n); 
     	}else
     	{
     		addLeft(n);
     	}
     }
     //returns the node information 
     public String toString()
     {
     
       return  String.format("* Node Data: %s", getData());
    
     }
      
      //Testing
     public static void main(String args[])
     {
       Node me = new Node("Hello");
       Node m = new Node("m");
       Node e = new Node("e");
       System.out.println(me.toString());
       System.out.println(me.hasLeftChild());
       me.addChild(m);
       me.addChild(e);
       System.out.println("me has a left child: "+ me.hasLeftChild());
       System.out.println("me has a right child: " + me.hasRightChild());
       if(me.hasLeftChild())
       {
       		System.out.println(me.getLeft().toString());
       }
       if(me.hasRightChild())
       {
       		System.out.println(me.getRight().toString());
       }
     
     }
    }
    BinaryTree.java
    Java Code:
    /**
     * @(#)BinaryTree.java
     *
     *
     * @author 
     * @version 1.00 2009/11/18
     */
    import java.util.Vector;
    
    public class BinaryTree<T> {
    
    	Vector<T> tree = new Vector<T>();
    	Node root; // The root node
    	Node parent;//parent of the current node
    	Node current; //current node
    	//Constructor
        public BinaryTree(BinaryTree<T> preset) 
       	{
    
       			setTree(preset);
        }
        //using vector
        public BinaryTree(Vector<T> vals)
        {
        	tree = vals;
        }
        
       
        //setting the tree
        public void setTree(BinaryTree<T> t)
        {
        	tree = t.tree;	
    
        }
        //returns the current node
        public Node getCurrentNode()
        {
        	
        	return current;
        }
        //moves to the next Node, This starts with the left child if it is a parent node
        public void next()
        {
        	if(isEmpty())
        	{
        		
    		    	if (current == null) //if there is no current node
    		    	{
    		    			// start with parent node
    		    			current = root;
    		    	}else
    		    	{
    		    			if(current.hasChild()) // if there is a child, move to child
    		    			{
    		    				current = current.getLeft(); //pick left node
    		    			}else if(current.hasRightChild()) //else move to the right node
    		    			{
    		    				current = current.getRight();
    		    			}else//else if it has no child nor a right node move up
    		    			{
    		    				current = current.getParent();
    		    			}
    		    			
    		    	}
        	}else
        	{
        		System.out.println("Tree is EMPTY");
        	}	
        }
        //returns true if the tree is empty
        public boolean isEmpty()
        {
        	
        	if(root == null)
        		return true;
        	else
        		return false;
        	
        }
        
        //Moves to the right child of the current node
        public void moveRight()
        {
        	if(current.hasRightChild())	
        	{
        		current = current.getRight();
        	}
        	
        }
        //Moves to the Left Child of the current node
        public void MoveLeft()
        {
        	if(current.hasLeftChild())
        	{
        		current = current.getLeft();
        	}
        		
        }
        //move to the parent node
        public void moveUp()
        {
        	if(current.hasParent())
        	{
        		current = current.getParent();
        	}
        }
        	
        
        //searches for a node in the tree
        public void searchNodes( BinaryTree<T> t, Node n )	
        {
        		
        }
        //adds a node to the tree
        public void addNode(BinaryTree<T> t, Node n)
        {
        	
        	
        }
        //deletes a node from the tree
        public void deleteNode(BinaryTree<T> t, Node n)
        {
        	
        }
        
        //TESTING
        public static void main(String args[])
        {
        	
        	
        }
        
        
    }

    Thanks for the help..in Advance.!!! :)

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    Where do you think you're messing up?

    Not sure if this is really an issue or just me nit picking but on your default node constructor you should set parent,left,right to null also.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  3. #3
    MuslimCoder is offline Senior Member
    Join Date
    Jan 2009
    Posts
    119
    Rep Power
    0

    Default

    hmmm...i think that's right. though I wouldnt need it for the one with preset.

    I think I am messing up more particularly in the binary tree, like in the next() method.

  4. #4
    aaroncarpet's Avatar
    aaroncarpet is offline Senior Member
    Join Date
    Nov 2009
    Location
    California
    Posts
    147
    Rep Power
    0

    Default

    Here is the code for a working binary tree CLASS

    Java Code:
    DEVELOPING GAME IN JAVA 
    
    Caracteristiques
    
    Editeur : NEW RIDERS 
    Auteur : BRACKEEN 
    Parution : 09 2003 
    Pages : 972 
    Isbn : 1-59273-005-1 
    Reliure : Paperback 
    Disponibilite : Disponible a la librairie 
    */
    
    public class BinaryTreeTest {
    
      public static void main(String[] args) {
        new BinaryTreeTest().run();
      }
    
      static class Node {
        Node left;  // declares instance of itself
    
        Node right;// declares instance of itself these are your pointers
    
        int value;  //the stored value
    
        public Node(int value) {//an overided constructor that stores the value for the node 
          this.value = value;
        }
      }
    
      public void run() {
        // build the simple tree from chapter 11.
        Node root = new Node(5); //the top node is 5 an arbitrary value by programmer
        System.out.println("Binary Tree Example");
        System.out.println("Building tree with root value " + root.value); //some output for user
        insert(root, 1); // inserting second number "root" being the initial node
       /*scroll down to the insert method now */
        insert(root, 8);
        insert(root, 6);
        insert(root, 3);
        insert(root, 9);
        System.out.println("Traversing tree in order");
        printInOrder(root);
        System.out.println("Traversing tree front-to-back from location 7");
        printFrontToBack(root, 7);
      }
    
      public void insert(Node node, int value) {
        if (value < node.value) { //first insert root = 5  and 1 is <5 so this is true
          if (node.left != null) { // if the left node isn't filled which it isn't 
            insert(node.left, value); //move to the left and try again recursion method calls itself
          } else {
            System.out.println("  Inserted " + value + " to left of "
                + node.value);
            node.left = new Node(value); //otherwise stick it here
          }
        } else if (value > node.value) {
          if (node.right != null) {
            insert(node.right, value);
          } else {
            System.out.println("  Inserted " + value + " to right of "
                + node.value);
            node.right = new Node(value);
          }
        }
      }
    
      public void printInOrder(Node node) {
        if (node != null) {
          printInOrder(node.left);
          System.out.println("  Traversed " + node.value);
          printInOrder(node.right);
        }
      }
    
      /**
       * uses in-order traversal when the origin is less than the node's value
       * 
       * uses reverse-order traversal when the origin is greater than the node's
       * order
       */
      public void printFrontToBack(Node node, int camera) {
        if (node == null)
          return;
        if (node.value > camera) {
          // print in order
          printFrontToBack(node.left, camera);
          System.out.println("  Traversed " + node.value);
          printFrontToBack(node.right, camera);
        } else if (node.value < camera) {
          // print reverse order
          printFrontToBack(node.right, camera);
          System.out.println("  Traversed " + node.value);
          printFrontToBack(node.left, camera);
        } else {
          // order doesn't matter
          printFrontToBack(node.left, camera);
          printFrontToBack(node.right, camera);
        }
      }
    
    }

    study that...remembr...you always pass the new data to the root and if your methods are built right the data will climb to its limb
    Last edited by aaroncarpet; 11-19-2009 at 05:59 AM. Reason: explaining use of recursion bucause of lack of pointers

  5. #5
    aaroncarpet's Avatar
    aaroncarpet is offline Senior Member
    Join Date
    Nov 2009
    Location
    California
    Posts
    147
    Rep Power
    0

    Default

    Unlike C++ java doesn't have pointers..........so your node has to call new instances of it self like the example I showed
    I am recommenting the above code to show the necessary recursion for the tree to work propely
    Last edited by aaroncarpet; 11-19-2009 at 06:01 AM. Reason: binary tree is a legacy type and if coded wrong can be fatal

  6. #6
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    I think you meant if(!isEmpty()). the logic behind it right now states if your tree is empty do work otherwise if it's not empty return that it is.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by aaroncarpet View Post
    Unlike C++ java doesn't have pointers..........
    That is definitely not true; unlike C and C++ Java doesn't have pointer arithmetic but all your non-primitive variables can be considered pointers but they are called 'references' which I find confusing at best.

    kind regards,

    Jos

  8. #8
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    6

    Default

    I think "java doesn't have pointers" in the same sense it doesn't have global variables. With Java all the pointing is done in the backend and you don't really have to touch it. Java doesn't officially have global variables but a static variable defined in a class and outside your method does the exact same thing amirite?
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by xcallmejudasx View Post
    I think "java doesn't have pointers" in the same sense it doesn't have global variables. With Java all the pointing is done in the backend and you don't really have to touch it. Java doesn't officially have global variables but a static variable defined in a class and outside your method does the exact same thing amirite?
    Every time you use the dot operator '.' you're using pointers. Global variables are an entirely different cup of tea; public static variables are global variables within a scope; Java doesn't have scopeless globals. w.r.t. those pointers, think of the NullPointerException. Those pointers clearly clarify all the fonfusion that comes up periodically on the 'pass by reference' issue (something Java doesn't have).

    kind regards,

    Jos

Similar Threads

  1. code for binary tree in jsp
    By ajay kumar in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 11-17-2009, 06:45 AM
  2. Binary Search Tree
    By anmadie in forum New To Java
    Replies: 5
    Last Post: 11-17-2009, 02:39 AM
  3. Binary Search Tree
    By Goo in forum New To Java
    Replies: 0
    Last Post: 03-06-2009, 04:46 PM
  4. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 02:03 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
  •