Putting Binary Search Tree into an array

[Angela Truce]

Hi all,

I've written this program that will search through a Binary Search Tree to put all nodes into an array. The problem is, it does it fine when I want to print it onto the dos window, but I need to print it to an applet and the statement

return done

is not matching the

system.out.println...

part which is the correct output. Can someone figure out how I can make return done match the output?

public int[] toSortedArray()
{
BSTree current = this;
 
return inOrder(current, current.root(),0);
 
}
 
public int[] inOrder(BSTree T, BTNode n, Integer i)
{
size = this.size(root);
int[] node = new int[size];
if (n!=null)
{
inOrder(T,n.getLeftChild(),i++);
node[i] = n.getElement();
System.out.println(node[i]+", ");
inOrder(T,n.getRightChild(),i++);
}
return node;
 
}

Thanks in advance!

[Henry Wong]

You are making an assumption that just because the debugging messages list the nodes in order, that you actually correctly put it into an array.

Take a look at your solution again. You will see that at no time have you completely built an array from the tree. The most you put into any array is one node.

Henry

[Angela Truce]

thanks, how do I put all of the items into the node array? I tried decalring a new array in the first method and then let the second method return an int so that it can be put into this array but it didnt seem to work.
Any suggestions?
thanks.

[Henry Wong]

Originally posted by Angela Truce:
thanks, how do I put all of the items into the node array? I tried decalring a new array in the first method and then let the second method return an int so that it can be put into this array but it didnt seem to work.
Any suggestions?
thanks.

Well, you could pass the array down recursively. Or you could work with a global array. Either is fine.

BTW, you may not notice it because it doesn't work yet, but the calculation of the index "i" is not completely correct.

Henry

[Angela Truce]

Hi,
I tried to implement a global array (i don't understand what you mean by calculation of i...is it wrong at the node[i]=n.getElement() bit???) but it gives me a null pointer exception:

private int newSize = this.newSize(root);
private int[] node = new int[newSize];
public int[] toSortedArray()
{
BSTree current = this;
return inOrder(current, current.root(),0);
}
 
public int[] inOrder(BSTree T, BTNode n, int i)
{
//size = this.size(root);
//int[] node = new int[size];
if (n!=null)
{
inOrder(T,n.getLeftChild(),i++);
node[i] = n.getElement();
System.out.println(node[i]+", ");
inOrder(T,n.getRightChild(),i++);
}
return node;
}

[Henry Wong]

Don't worry about the index i, you have other problems to worry about first.

As for the global variable, do you want to initialize it when you instantiate the class? or when the toSortedArray() method is called?

Henry

[Angela Truce]

I would like to declare before the class so that it can be used by all methods for that class.

[Angela Truce]

I think i figured out the "i" problem:

public int[] toSortedArray()
{
BSTree current = this;
return inOrder(current, current.root(),0);
}
 
public int[] inOrder(BSTree T, BTNode n, int i)
{
size = this.size(root);
int[] node = new int[size];
if (n!=null)
{
inOrder(T,n.getLeftChild(),i);
node[i++] = n.getElement();
System.out.println(node[i]+", ");
inOrder(T,n.getRightChild(),i);
}
return node;
}

[Henry Wong]

Originally posted by Angela Truce:
I would like to declare before the class so that it can be used by all methods for that class.

Okay... I guess we lost track of what we are doing. These are *not* supposed to be global variables. Remember, these happen to be global variables because you couldn't figure out how to pass a local variable in a recursive manner.

Anyway let's forget this whole mess. Let's do it the correct way -- you'll have to learn it anyway.


Go back to the original example. Declare an array in the toSortedArray() method, and then pass it recursively to the inOrder() method.

Henry

[Angela Truce]

It's giving me a repetition of the "num array" in dos but still incorrect in the "array" part as now it's all a row of root element.

public int[] toSortedArray()
{
BSTree current = this;
size = this.size(root);
int[] array = new int[size];
for(int i =0; i<size; i++)
{
array[i] = inOrder(current, current.root(),0);
}
return array;
}
 
public int inOrder(BSTree T, BTNode n, int i)
{
int num=0;
if (n!=null)
{
inOrder(T,n.getLeftChild(),i);
num = n.getElement();
System.out.println(num+", ");
inOrder(T,n.getRightChild(),i);
}
return num;
}

[Angela Truce]

Ok, now i got rid of the for loop so it only prints out the required amount. But the array is displaying the root and the rest zero's...?..hmmm

public int[] toSortedArray()
{
BSTree current = this;
size = this.size(root);
int[] array = new int[size];
 
int i = 0;
if (i<size)
{
array[i] = inOrder(current, current.root(),i);
i++;
}
return array;
}
 
public int inOrder(BSTree T, BTNode n, int i)
{
int num=0;
if (n!=null)
{
inOrder(T,n.getLeftChild(),i);
num = n.getElement();
System.out.println(num+", ");
inOrder(T,n.getRightChild(),i);
}
return num;
}

[Henry Wong]

Angela,

I seem to be at a lost. It seems that every iteration is worse than the previous one. And I believe the reason for this is that you are making the changes that I am requesting -- but you don't seem to understand why.

Don't do that. If you don't understand "why" with the hints that I am giving you, don't do it.





How do you pass an array around recursively? One way is to use parameters...

    public int inOrder(BSTree T, BTNode n, int [] array, int i)

Again, don't do it until you understand why...

Henry

[Angela Truce]

hmm...am i getting close?

public int[] toSortedArray()
{
size= this.size(root);
int[] result = new int[size];
inOrder(this.root(), result,0);
return result;
}
 
public void inOrder(BTNode n, int[] result,int i)
{
if (n!=null) {
inOrder(n.getLeftChild(), result,i);
result[i++]=n.getElement();
inOrder(n.getRightChild(),result,i);
}
}

[Henry Wong]

Originally posted by Angela Truce:
hmm...am i getting close?

YES!!! Much better...

The index is still wrong... to fix that you will have to debug it. Add a ton of println statements to see what is going on with the index.

Henry

[Angela Truce]

it's giving me zero everytime so i added a few guesses that it was reseting "i" everytime inOrder was called. Still can't see what's going on though...

public int[] toSortedArray()
{
size= this.size(root);
int[] result = new int[size];
inOrder(this.root(), result,0);
return result;
}
 
public void inOrder(BTNode n, int[] result,int i)
{
if (n!=null)
{
i++;
inOrder(n.getLeftChild(), result,i++);
result[i]=n.getElement();
System.out.print(result[i]+"with i= "+i+" \n");
inOrder(n.getRightChild(),result,i++);
}
for (int j =0; j<size; j++)
System.out.print("full array: "+result[j]+" \n");
}