Binary Tree Help

[ezkonekgal]

Hello every one.
Basically i am trying to construct a binary tree. but there's a problem. When i run the program, there is an error. somewhere in the treeInsert method(). I am having difficulty because the root is not node, it is an integer value. then the left and right subtree is a binary tree. before, i used nodes to construct binary trees.. i can't root.left. if sumone could just look and see what is the problem.

package assignments;


public class BinaryTree {

	
	int root;
	BinaryTree leftSubTree;
	BinaryTree rightSubTree;
	static BinaryTree myTree;

	
	BinaryTree(){
		root = 0;
		leftSubTree = null;
		rightSubTree = null;

	}

	BinaryTree(Integer n){
		root = n;
	}

	BinaryTree(Integer n, BinaryTree left, BinaryTree right){
		root = n;
		leftSubTree = left;
		rightSubTree = right;
	}

	
	public int getRoot(){
		return(root);
	}

	public BinaryTree getLeftChild(){
		return(leftSubTree);
	}

	public BinaryTree getRightChild(){
		return (rightSubTree);
	}

	
	public int getHeight(){

		    int left = -1;
		    int right = -1;
		    if( leftSubTree != null ){
		        left = leftSubTree.getHeight();
		    }
		    if( rightSubTree != null ){
		        right = rightSubTree.getHeight();
		    }
		     if( left > right ){
		        return left + 1;
		     }return right + 1;
		}



	public boolean isEmpty(){
		boolean ai = false;
		if(root == 0){
			return true;
		}return ai;
	}

	public int countNodes(){
		int count = 1;
		if (this.getLeftChild() != null){
			count += this.getLeftChild().countNodes();
		}
		if (this.getRightChild() != null){
		        count += this.getRightChild().countNodes();
		}return count;
	}

	public int countLeaves(BinaryTree t){
		int count = 0;
		if(root == 0){
			countLeaves(leftSubTree);
			if(leftSubTree.root != 0 && rightSubTree.root != 0){
				count++;
			}
			countLeaves(rightSubTree);
		}return count;
	}


	public void destroy(){

	}

	public void preorderTraversal(){
		if (root != 0) {
			System.out.println(root);
			new BinaryTree(leftSubTree.root).preorderTraversal();
			new BinaryTree(rightSubTree.root).preorderTraversal();
		}
	}

	public void inorderTraversal(){
		if (root != 0) {
			new BinaryTree(leftSubTree.root).inorderTraversal();
			System.out.println(root);
			new BinaryTree(rightSubTree.root).inorderTraversal();
		}
	}

	public void postorderTraversal(){
		if (root != 0) {
			new BinaryTree(leftSubTree.root).postorderTraversal();
			new BinaryTree(rightSubTree.root).postorderTraversal();
			System.out.println(root);
		}
	}

	public void levelorderTraversal(){

	}

	public void treeInsert(BinaryTree t, int newItem) {
	              // Add the item to the binary sort tree to which the parameter
	              // "root" refers.  Note that root is passed by reference since
	              // its value can change in the case where the tree is empty.
	          if ( t.root == 0 ) {
	                 // The tree is empty.  Set root to point to a new node containing
	                 // the new item.  This becomes the only node in the tree.
	             t = new BinaryTree(newItem);
	                     // NOTE:  The left and right subtrees of root
	                     // are automatically set to NULL by the constructor.
	                     // This is important!
	             return;
	          } else if ( newItem < t.root) {
	        	 treeInsert( leftSubTree, newItem );
	          }else {
	        	  treeInsert(rightSubTree, newItem );
	          }
	}


	public static void main(String args[]){

		myTree = new BinaryTree();
		myTree.insert();
		System.out.println("Height of tree is: "+ myTree.getHeight());
		System.out.println("Number of nodes: "+ myTree.countNodes());
		System.out.println("Number of leaves: "+ myTree.countLeaves(myTree));
		System.out.println("Preorder: ");
		myTree.preorderTraversal();
		System.out.println("Inorder: ");
		myTree.inorderTraversal();
		System.out.println("PostOrder: ");
		myTree.postorderTraversal();
		System.out.println("LevelOrder: ");
		myTree.levelorderTraversal();
	}

	public void insert(){
		int arrNum[] = {50,17,76,9,23,54,14,19,72,12,67};

		for(int i=0; i<=10; i++){
			treeInsert(arrNum[i]);
		}

	}


}

[JamesCherrill]

treeInsert(BinaryTree t, int newItem) is a method that requires two parameters

[I]treeInsert(arrNum); is a method call that has only one parameter.

Error!

Plus: this doesn't do anything

if ( t.root == 0 ) {
// The tree is empty. Set root to point to a new node containing
// the new item. This becomes the only node in the tree.
t = new BinaryTree(newItem);
// NOTE: The left and right subtrees of root
// are automatically set to NULL by the constructor.
// This is important!
return;

You create a new BinaryTree, make t ( a parameter - hence local) a reference to it, then exit. t goes out of scope, the new BinaryTree will be garbage collected. You may have made this mistake because earlier you commentedNote that root is passed by reference
Java does not support parameter passing by reference. All parameters are passed by value.

[ezkonekgal]

public void BTreeInsert(BinaryTree myTree, int newItem) {
		if ( myTree == null ) {
			myTree = new BinaryTree(newItem);
	    } else {
	    	if ( newItem < myTree.root) {
	    		BTreeInsert(leftSubTree,  newItem );
	    	}else {
	        	BTreeInsert(rightSubTree, newItem );
	         }
	    }
	}

and i change my main to this with additional methods

[codes=java]
public static void main(String args[]){
myTree = new BinaryTree();
myTree.insert();
myTree.display();
}

public void insert(){
int arrNum[] = {50,17,76,9,23,54,14,19,72,12,67};
for(int i=0; i<=10; i++){
BTreeInsert(myTree, arrNum[i]);
}

}

[/codes]

When i run it, because the task is to output the heigth, number of nodes, number of leaves, and the three traversals
height is 0
number of nodes is 0
No. of leaves is 0.
traversals ... none.

i don't know if i successfully inserted the numbers in the tree or not. some how, the BTreeInsert method is wrong. pls enlighten me.

[JamesCherrill]

System.out.println is your new best friend.
At each stage of your code, put in temporary System.out.println statements that print the values that you have just set/created. That way you can see:
1. Whether the code is being executed at all
2. Whether all the (local) values are being set as you expected.

When you see where it's going wrong you can add more temporary System.out.println's to narrow down the problem until it becomes obvious.

It's no good running the whole program then just looking at the results at the end. If it goes wrong you have no idea where or why.

ps Did you fix the error with new BinaryTree that I described before?

pps:

public boolean isEmpty(){
  boolean ai = false;
  if(root == 0){
    return true;
  }return ai;
}

is a very long way to say

public boolean isEmpty(){
    return root == 0;
}

[ezkonekgal]

System.out.println is your new best friend. At each stage of your code, put in temporary System.out.println statements that print the values that you have just set/created. That way you can see: 1. Whether the code is being executed at all 2. Whether all the (local) values are being set as you expected.

When you see where it's going wrong you can add more temporary System.out.println's to narrow down the problem until it becomes obvious.

It's no good running the whole program then just looking at the results at the end. If it goes wrong you have no idea where or why.

ps Did you fix the error with new BinaryTree that I described before?

}[/CODE]

I don't think i've fix it.

here's what i did

public void BTreeInsert(BinaryTree myTree, int newItem) {
		if ( myTree == null ) {
			myTree = new BinaryTree(newItem);
	    } else {
	    	if ( newItem < myTree.root) {
	    		BTreeInsert(leftSubTree,  newItem );
	    	}else {
	        	BTreeInsert(rightSubTree, newItem );
	         }
	    }
	}


	public static void main(String args[]){
		myTree = new BinaryTree();
		myTree.insert();
		myTree.display();
		}

	public void insert(){
		int arrNum[] = {50,17,76,9,23,54,14,19,72,12,67};
		for(int i=0; i<=10; i++){
			BTreeInsert(myTree, arrNum[i]);
		}

	}

	public void display(){
		System.out.println("Height of tree is: "+ getHeight(myTree));
		System.out.println("Number of nodes: "+ countNodes(myTree));
		System.out.println("Number of leaves: "+ countLeaves(myTree));
		System.out.println("Preorder: " + preorderTraversal(myTree) );
		System.out.println("Inorder: " + inorderTraversal(myTree));
		System.out.println("Postorder: " + postorderTraversal(myTree));
System.out.println("Levelorder: " + levelorderTraversal());


	}

ask what i've said, When i run it, because the task is to output the heigth, number of nodes, number of leaves, and the three traversals
height is 0
number of nodes is 0
No. of leaves is 0.
traversals ... none.

i don't know if i successfully inserted the numbers in the tree or not. some how, the BTreeInsert method is wrong..

i'll try to do the temporary sys.out thing you said

[JamesCherrill]

You still have the same problem with this code:

public void BTreeInsert(BinaryTree myTree, int newItem) {
  if ( myTree == null ) {
    myTree = new BinaryTree(newItem);
  } else ...

myTree is a parameter, a local variable, you cannot change the value of the myTree declared in main(...) by doing anything to the local myTree in BTreeInsert.
Because the only reference to your new BinaryTree is held in the local parameter, that reference will be lost when the method ends, and your new BinaryTree will be garbage collected.
I'm sure this isn'ty what you intended.

[ezkonekgal]

yes, i know. but i don't know how

[JamesCherrill]

.. but i don't know how

how to do what exactly? I confess that I've been dealing with specific Java syntax problems and not the overall design of your code because I can't really follow it. It looks like your BinaryTree class is really a Node class, and the the root variable is really the node data, and you don't really have a root node for the whole tree, but maybe that's just because I'm confused.

[ezkonekgal]

that's exactly why i'm confused too. In a node, there's a root for the info and a left and right link. and what i know is that a binary tree uses nodes.

In this exercise, this is what was given to us, and i have noticed that the binary tree class is somewhat like a node class.

in a binary tree with node class, you can do root.left or root.right. because root is a node.

in my class, i'm confused. i can't root.left or root.right because root is data (int). leftSubTree is a binarytree.

is my binary class the same as a node class? because i was thinking of extending a node class. but then i was looking at the constuctors, and now i'm confused.

[ezkonekgal]

...and you don't really have a root node for the whole tree...

do i have to have a root node? what am i going to do with this class?

[JamesCherrill]

It';s a long time since I did this stuff at the theoretical level, so I may get this wrong (maybe someone else can confirm? Please?).
A Tree is a collection of Nodes. Each Node contains some data, and links to child Nodes. There is one top-most ("root") Node, and each child has one parent (except the root node). If each Node has two children, it's a binary tree.
To represent it you'd expect a Node class - each instance is 1 node with its data and references to its child nodes. To represent the tree all you need is a reference to the topmost Node - everything else is found by traversing the tree starting from there. It makes sense to have a Tree class (1) to hold the ref to the topmost Node and (2) as a good place to put all the methods that work on the tree (add node, count nodes etc etc). A sub-tree is a tree that's part of another bigger tree, and needs no special classes or code; all you need is a reference to the topmost node of that sub-tree.

I suspect the reason that you're having difficulties with your program structure is that you have 1 class when you really need two.