Binary Tree

[MuslimCoder]

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

//  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

/**
 * @(#)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.!!! :)

[xcallmejudasx]

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.

[MuslimCoder]

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.

[aaroncarpet]

Here is the code for a working binary tree CLASS

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

[aaroncarpet]

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

[xcallmejudasx]

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.

[JosAH]

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

[xcallmejudasx]

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?

[JosAH]

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