tyweed420
asked on
I cannot get my binary search tree to grow when i call my insert method
I have three classes BSTNode,BinarySearchTree, and BinaryTreeTester
all i have to do is implement the insert(int x,BSTNode t) and i'm good. However this has become a nightmare! I have traced through all my code and can see what is going wrong, however i have been unable to fix the problem. I'm desperate and am going to put this thread at 500 points. So big guys objects cehj we have discussed this many times please help!! Ok here are the two importantr classes ill post vbinary search tree first and then below this i'll post the tester with the output to the side . In a nutshel when i call insert the first time it sets root up just fine. but all following calls cause unexpected results look at binary test to see.
========================== ========== ===
public void insert(int x)
{
root = insert(x,root);
System.out.println("insert (int x)");
}
public BSTNode insert(int x, BSTNode t)
{
if(t == null)
{
System.out.println("root") ;
return root = new BSTNode(x,null,null);
}
else if(x < t.getData())
{
if(t.leftChild == null)
{
t.leftChild = new BSTNode(x,null,null);
System.out.println("left child null");
printTree();
}
else
{
t.leftChild = insert(x,t.leftChild);
System.out.println("left") ;
}
}
else if( x > t.getData() )
{
if(t.rightChild == null)
{
System.out.println("right child null");
t.rightChild = new BSTNode(x,null,null);
printTree();
}
else
{
t.rightChild = insert(x,t.rightChild);
System.out.println("right" );
}
}
else
; //do nothing
System.out.println("return ing t");
return t;
}
========================== ========== ==
class BinaryTreeTester
{
public static void main(String [] args)
{
BinarySearchTree tree = new BinarySearchTree();
tree.insert(5); calls insert(int k)
System.out.println(tree.he ight() + " height test"); height of 1
System.out.println(tree.ro ot.getData () + "data"); data is 5
System.out.println(tree.ro ot); //is not null good.............
System.out.println("");
tree.insert(4); calls insert(int k) this calls insert(x,root) it goes into the second insert method and ends up in the if(t.leftChild == null) statement and places it ok i print the tree within the binary search tree class i get 5 4 it worked however in the tester class tree.root.leftchild is null? why?
System.out.println(tree.he ight() + " height test");
System.out.println(tree.ro ot.getData () + "data");
System.out.println(tree.ro ot.leftChi ld + "left child"); this is null
System.out.println("");
tree.insert(66); this does same thing is called by insert(int k) then called by insert(int x,bstnode t) then goes into the if (t.rightycild == null) and if i call print tree in the binary search tree class i get 5 root, 66 rightchild ........... 4 is gone?
System.out.println(tree.he ight() + " height test");
System.out.println(tree.ro ot.getData () + "data");
System.out.println(tree.ro ot.rightCh ild + "right child"); once again now in the tester class rightchild is null?
System.out.println("");
tree.insert(3); //allthe same i get 5 3 for tree if calle in the binarysearch tree with a printtree method but in the tester nothing
System.out.println(tree.he ight() + " height test");
System.out.println(tree.ro ot.getData () + "data");
System.out.println("====== ==PRINT TREE============");
tree.printTree(); then i call print tree in the tester i get 5 ??
}//end main
}//end
It must be with the childs == null statements and somehow assignments are lost when i call from another class i just cant get this.
500 POINTS AND A BIG HUG & KISS TO ANY WHO CAN HELP ME PLEASE
all i have to do is implement the insert(int x,BSTNode t) and i'm good. However this has become a nightmare! I have traced through all my code and can see what is going wrong, however i have been unable to fix the problem. I'm desperate and am going to put this thread at 500 points. So big guys objects cehj we have discussed this many times please help!! Ok here are the two importantr classes ill post vbinary search tree first and then below this i'll post the tester with the output to the side . In a nutshel when i call insert the first time it sets root up just fine. but all following calls cause unexpected results look at binary test to see.
==========================
public void insert(int x)
{
root = insert(x,root);
System.out.println("insert
}
public BSTNode insert(int x, BSTNode t)
{
if(t == null)
{
System.out.println("root")
return root = new BSTNode(x,null,null);
}
else if(x < t.getData())
{
if(t.leftChild == null)
{
t.leftChild = new BSTNode(x,null,null);
System.out.println("left child null");
printTree();
}
else
{
t.leftChild = insert(x,t.leftChild);
System.out.println("left")
}
}
else if( x > t.getData() )
{
if(t.rightChild == null)
{
System.out.println("right child null");
t.rightChild = new BSTNode(x,null,null);
printTree();
}
else
{
t.rightChild = insert(x,t.rightChild);
System.out.println("right"
}
}
else
; //do nothing
System.out.println("return
return t;
}
==========================
class BinaryTreeTester
{
public static void main(String [] args)
{
BinarySearchTree tree = new BinarySearchTree();
tree.insert(5); calls insert(int k)
System.out.println(tree.he
System.out.println(tree.ro
System.out.println(tree.ro
System.out.println("");
tree.insert(4); calls insert(int k) this calls insert(x,root) it goes into the second insert method and ends up in the if(t.leftChild == null) statement and places it ok i print the tree within the binary search tree class i get 5 4 it worked however in the tester class tree.root.leftchild is null? why?
System.out.println(tree.he
System.out.println(tree.ro
System.out.println(tree.ro
System.out.println("");
tree.insert(66); this does same thing is called by insert(int k) then called by insert(int x,bstnode t) then goes into the if (t.rightycild == null) and if i call print tree in the binary search tree class i get 5 root, 66 rightchild ........... 4 is gone?
System.out.println(tree.he
System.out.println(tree.ro
System.out.println(tree.ro
System.out.println("");
tree.insert(3); //allthe same i get 5 3 for tree if calle in the binarysearch tree with a printtree method but in the tester nothing
System.out.println(tree.he
System.out.println(tree.ro
System.out.println("======
tree.printTree(); then i call print tree in the tester i get 5 ??
}//end main
}//end
It must be with the childs == null statements and somehow assignments are lost when i call from another class i just cant get this.
500 POINTS AND A BIG HUG & KISS TO ANY WHO CAN HELP ME PLEASE
Hi tyweed420,
Try the following:
public BSTNode insert(int x, BSTNode t)
{
if(t == null)
{
System.out.println("root") ;
return root = new BSTNode(x,null,null);
}
else if(x < t.getData())
{
if(t.leftChild == null)
{
t.leftChild = new BSTNode(x,null,null);
System.out.println("left child null");
printTree();
}
else
{
t.leftChild.insert(x, t.leftChild);
System.out.println("left") ;
}
}
else if( x > t.getData() )
{
if(t.rightChild == null)
{
System.out.println("right child null");
t.rightChild = new BSTNode(x,null,null);
printTree();
}
else
{
t.rightChild.insert(x, t.rightChild);
System.out.println("right" );
}
}
else
; //do nothing
System.out.println("return ing t");
return t;
}
Cheers!
\\t
Try the following:
public BSTNode insert(int x, BSTNode t)
{
if(t == null)
{
System.out.println("root")
return root = new BSTNode(x,null,null);
}
else if(x < t.getData())
{
if(t.leftChild == null)
{
t.leftChild = new BSTNode(x,null,null);
System.out.println("left child null");
printTree();
}
else
{
t.leftChild.insert(x, t.leftChild);
System.out.println("left")
}
}
else if( x > t.getData() )
{
if(t.rightChild == null)
{
System.out.println("right child null");
t.rightChild = new BSTNode(x,null,null);
printTree();
}
else
{
t.rightChild.insert(x, t.rightChild);
System.out.println("right"
}
}
else
; //do nothing
System.out.println("return
return t;
}
Cheers!
\\t
>> Orangehead
I don't think you can do
t.leftChild.insert(x, t.leftChild);
since this insert() function isn't defined on a BSTNode but on the BinarySearchTree
>>tyweed420
Even, why should insert(int x, BSTNode t) return something?
I think that's not necessary. The insert function just has to insert a new node into the tree.
This is the most easiest form I believe:
public void insert(int x) {
insert(x,root);
System.out.println("insert (int x)");
}
public void insert(int x, BSTNode t) {
if(t == null)
return root = new BSTNode(x,null,null); // here the inital root is set (once)
else if(x < t.getData()) {
if(t.leftChild == null)
t.leftChild = new BSTNode(x,null,null);
else
insert(x,t.leftChild);
return;
}
else if( x > t.getData() ) {
if(t.rightChild == null)
t.rightChild = new BSTNode(x,null,null);
else
insert(x,t.rightChild);
return;
}
else
; //do nothing // <<<<<<<<< What about double values????
return;
}
I don't think you can do
t.leftChild.insert(x, t.leftChild);
since this insert() function isn't defined on a BSTNode but on the BinarySearchTree
>>tyweed420
Even, why should insert(int x, BSTNode t) return something?
I think that's not necessary. The insert function just has to insert a new node into the tree.
This is the most easiest form I believe:
public void insert(int x) {
insert(x,root);
System.out.println("insert
}
public void insert(int x, BSTNode t) {
if(t == null)
return root = new BSTNode(x,null,null); // here the inital root is set (once)
else if(x < t.getData()) {
if(t.leftChild == null)
t.leftChild = new BSTNode(x,null,null);
else
insert(x,t.leftChild);
return;
}
else if( x > t.getData() ) {
if(t.rightChild == null)
t.rightChild = new BSTNode(x,null,null);
else
insert(x,t.rightChild);
return;
}
else
; //do nothing // <<<<<<<<< What about double values????
return;
}
Correction (forgot to change):
if (t == null) {
root = new BSTNode(x,null,null);
return;
}
if (t == null) {
root = new BSTNode(x,null,null);
return;
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
try something like this:
public void insert(int x)
{
insert(x, root);
}
private void insert(int x, BSTNode t)
{
if (t==null)
{
root = new BSTNode(x, null, null);
}
else if (x<t.getData())
{
if (t.leftChild==null)
{
t.leftChild = new BSTNode(x, null, null);
}
else
{
insert(x, t.leftChild);
}
}
else
{
if (t.rightChild==null)
{
t.rightChild = new BSTNode(x, null, null);
}
else
{
insert(x, t.rightChild);
}
}
}
public void insert(int x)
{
insert(x, root);
}
private void insert(int x, BSTNode t)
{
if (t==null)
{
root = new BSTNode(x, null, null);
}
else if (x<t.getData())
{
if (t.leftChild==null)
{
t.leftChild = new BSTNode(x, null, null);
}
else
{
insert(x, t.leftChild);
}
}
else
{
if (t.rightChild==null)
{
t.rightChild = new BSTNode(x, null, null);
}
else
{
insert(x, t.rightChild);
}
}
}
8-)
Then I think it should be:
public void insert(int x) {
insert(x,root); // <<<<<<<< not root =
System.out.println("insert
}
public BSTNode insert(int x, BSTNode t) {
if(t == null) {
System.out.println("root")
return root = new BSTNode(x,null,null); // here the inital root is set (once)
}
else if(x < t.getData())
{
if(t.leftChild == null)
{
t.leftChild = new BSTNode(x,null,null);
System.out.println("left child null");
printTree();
// <<<<<<<<<<<< here I would return t.leftChild;
}
else
{
System.out.println("left")
t.leftChild = insert(x,t.leftChild); // <<<<<<<<<<<< shouldn't this be return insert(x,t.leftChild);
}
}
else if( x > t.getData() )
{
if(t.rightChild == null)
{
System.out.println("right child null");
t.rightChild = new BSTNode(x,null,null);
printTree();
// <<<<<<<<<<< here I would return t.rightChild
}
else
{
System.out.println("right"
t.rightChild = insert(x,t.rightChild); // <<<<< shouldn't this be return insert(x,t.rightChild);
}
}
else
; //do nothing // <<<<<<<<< What about double values????
System.out.println("return
return t;
}