# Thread: Binary Tree

1. Senior Member
Join Date
Jan 2009
Posts
119
Rep Power
0

## 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. 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.

3. Senior Member
Join Date
Jan 2009
Posts
119
Rep Power
0
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. 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 06:59 AM. Reason: explaining use of recursion bucause of lack of pointers

5. 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 07:01 AM. Reason: binary tree is a legacy type and if coded wrong can be fatal

6. 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.

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

8. 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?

9. 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•