# Binary Tree

• 11-17-2009, 10:07 PM
MuslimCoder
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
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
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.!!! :)
• 11-17-2009, 10:13 PM
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.
• 11-19-2009, 01:59 AM
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.
• 11-19-2009, 04:02 AM
aaroncarpet
Here is the code for a working binary tree CLASS

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
• 11-19-2009, 05:46 AM
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
• 11-19-2009, 05:09 PM
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.
• 11-19-2009, 05:39 PM
JosAH
Quote:

Originally Posted by aaroncarpet
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
• 11-19-2009, 05:46 PM
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?
• 11-19-2009, 05:57 PM
JosAH
Quote:

Originally Posted by 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?

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