Binary Search Tree inorder tree traversal
Hi I'm very new to Java and I'm trying to write some code to create a Binary Search Tree with the goal of outputting a list of integers using the inorder tree traversal method.
I've got as far as this:
Code :
public class BinarySearchTree {
public class Node {
private int value;
private Node right;
private Node left;
//construct node
//set current left and right vertices of root to null
public Node(int value){
this.value = value;
left = null;
right = null;
}
public Node leftNode() {
return left;
}
public Node rightNode() {
return right;
}
public int getNodeValue(){
return value;
}
private Node root;
//construct binary search tree
public void BinarySearchTree() {
root = null;
}
//Establish that if the tree is empty, then the value of the root is null
public boolean ifEmpty()
{
if (root == null) {
return true;
}
else { return false;
}
}
//Develop ability to add values into the binary search tree
public boolean insert(int value)
{ if (root == null) {
root = new Node(value);
return true;
}
else { if (value == this.value)
{ return false; }
else if (value <this.value) {
if (left == null) {
left = new Node(value);
return true;
} else {
return left.insert(value);
}
} else if (value > this.value) {
if (right == null) {
right = new Node(value);
return true;
} else {
return right.insert(value);
}
}
return false;
}
}
public void sortedList(){
sortedList(root);
}
private void sortedList(Node root){
if (root == null)
return;
sortedList( root.leftNode() );
System.out.println(root.value + " ");
sortedList ( root.rightNode() );
}
}
public static void main(final String[] args){
}
}
I've been following a tutorial and have been looking at some code on the internet, I'm not quite sure how I'm supposed to know if the sortedList method is sufficient to output, in order, a list of integers that has been put into the tree. Specifically the sortedList method I wrote with help of someone elses BST code and so I don't if it is written correctly in relation to the tree I have and the fields/objects that I have defined.
Also how would I go about entering some numbers into the code to see the tree in action? Sorry If I'm coming across as quite dense but I've only been working with Java for the past couple of weeks.
Re: Binary Search Tree inorder tree traversal
Quote:
how would I go about entering some numbers into the code to see the tree in action?
Create an instance of the class in the main() method and call some of its methods.
It looks like the definitions of the Node class and the BST class are mixed together. The Node class shouldn't have classes for doing BST things like insert. The Node class should hold the pointer(s) and the data and provide access to them.
The BST class looks at what is in the tree and controls adding/deleting Nodes from the tree.
Re: Binary Search Tree inorder tree traversal
Quote:
Originally Posted by
Norm
Create an instance of the class in the main() method and call some of its methods.
I have tried writing this:
Code :
public static void main(final String[] args){
int[] anArray = { 7, 3, 1, 6, 9, 0, 4, 5, 2, 8};
value = anArray[0];
Node firstnode = new Node(value);
firstnode.insert(value);
}
However I get a "non-static variable cannot be referenced from a static context" for lines 2-4, is there any obvious reason why this is occurring?
Quote:
It looks like the definitions of the Node class and the BST class are mixed together.
So should my Node class be in a separate file that the Binary Search File then calls methods from? Is this a cosmetic issue or will it end in complications in the final code?
Thanks for the help, it's much appreciated! :)
Re: Binary Search Tree inorder tree traversal
The Node class can be an inner class in the BST class or it could be outside the BST class. It would not have to be in a separate file(unless you want it to be public).
Quote:
"non-static variable cannot be referenced from a static context"
Please post the full text of the error messages that show the source lines where the error happens.
The main() method should NOT be trying to access any variables in the BST class. It should use BST methods to access anything.
Re: Binary Search Tree inorder tree traversal
Quote:
BinarySearchTree.java:96: error: non-static variable value cannot be referenced
from a static context
value = anArray[0];
^
BinarySearchTree.java:97: error: non-static variable value cannot be referenced
from a static context
Node firstnode = new Node(value);
^
BinarySearchTree.java:98: error: non-static variable value cannot be referenced
from a static context
firstnode.insert(value);
That's what I get from the cmd window.
Re: Binary Search Tree inorder tree traversal
value should be a local variable in the main() method
main() should NOT be creating Node objects. That should be done in the BST class's insert() method.
In post#2 I said:
Create an instance of the BST class in the main() method and call some of its methods.
Re: Binary Search Tree inorder tree traversal
Okay right, I understand that more clearly now. I also see the problem with the node class interfering with insert. However when I define the Node class as an inner class it looks like the fields defined in the Node class (root, left, right etc.) no longer know where to point to when they're used in the insert method?
Re: Binary Search Tree inorder tree traversal
The Node class is passive. It holds the pointers and value.
BST class has the logic for maintaining the tree and accessing the Node objects for chaining the nodes together and traversing the tree.
root should be in BST not in Node
Re: Binary Search Tree inorder tree traversal
Okay I understand what you're saying, I currently have this code:
Code :
public class BinarySearchTree {
public static class Node {
private int value;
private Node right;
private Node left;
//construct node
//set current left and right vertices of root to null
public Node(int value){
this.value = value;
left = null;
right = null;
}
public Node leftNode() {
return left;
}
public Node rightNode() {
return right;
}
public int getNodeValue(){
return value;
}
private Node root;
}
//construct binary search tree
public void BinarySearchTree() {
root = null;
}
//Establish that if the tree is empty, then the value of the root is null
public boolean ifEmpty()
{
if (root == null) {
return true;
}
else { return false;
}
}
//Develop ability to add values into the binary search tree
public boolean insert(int value)
{ if (root == null) {
root = new Node(value);
return true;
}
else { if (value == this.value)
{ return false; }
else if (value <this.value) {
if (left == null) {
left = new Node(value);
return true;
} else {
return left.insert(value);
}
} else if (value > this.value) {
if (right == null) {
right = new Node(value);
return true;
} else {
return right.insert(value);
}
}
return false;
}
}
public void sortedList(){
sortedList(root);
}
private void sortedList(Node root){
if (root == null)
return;
sortedList( root.leftNode() );
System.out.println(root.value + " ");
sortedList ( root.rightNode() );
}
public static void main(final String[] args, int value){
int[] anArray = { 7, 3, 1, 6, 9, 0, 4, 5, 2, 8};
value = anArray[0];
BinarySearchTree bst = new BinarySearchTree();
boolean aVal = bst.insert(value);
}
}
When I implement it I get the following 14 errors:
Quote:
BinarySearchTree.java:41: error: cannot find symbol
root = null;
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:46: error: cannot find symbol
if (root == null) {
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:54: error: cannot find symbol
{ if (root == null) {
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:55: error: cannot find symbol
root = new Node(value);
^
symbol: variable root
location: class BinarySearchTree
BinarySearchTree.java:58: error: cannot find symbol
else { if (value == this.value)
^
symbol: variable value
BinarySearchTree.java:60: error: cannot find symbol
else if (value <this.value) {
^
symbol: variable value
BinarySearchTree.java:61: error: cannot find symbol
if (left == null) {
^
symbol: variable left
location: class BinarySearchTree
BinarySearchTree.java:62: error: cannot find symbol
left = new Node(value);
^
symbol: variable left
location: class BinarySearchTree
BinarySearchTree.java:65: error: cannot find symbol
return left.insert(value);
^
symbol: variable left
location: class BinarySearchTree
BinarySearchTree.java:67: error: cannot find symbol
} else if (value > this.value) {
^
symbol: variable value
BinarySearchTree.java:68: error: cannot find symbol
if (right == null) {
^
symbol: variable right
location: class BinarySearchTree
BinarySearchTree.java:69: error: cannot find symbol
right = new Node(value);
^
symbol: variable right
location: class BinarySearchTree
BinarySearchTree.java:72: error: cannot find symbol
return right.insert(value);
^
symbol: variable right
location: class BinarySearchTree
BinarySearchTree.java:81: error: cannot find symbol
sortedList(root);
^
symbol: variable root
location: class BinarySearchTree
14 errors
At the risk of you wasting too much of your own time, and also so I can learn Java better myself, are there any hints you could give as to how I could implement the logic required in the BST class so that the fields recognise that they originate from the Node class?
Thanks
Re: Binary Search Tree inorder tree traversal
Did you see this in post#8
root should be in BST not in Node
Where is the constructor for the BST class. Hint: constructors don't return void.
Most of the errors for "cannnot find symbol" are because all those variables are in the Node class not in the BST class.
You need to use a reference to a class to access its variables. For example root is a reference to a Node class. Then root.value gets the value of the root node.
Re: Binary Search Tree inorder tree traversal
I'm not sure how I can solve the problem I now have, I've tried replacing the left and right in the insert method with Node.left/Node.right but I now get an error saying that they can't be referenced from a static context.
Re: Binary Search Tree inorder tree traversal
Use a reference to a node to get to the values in a node. For example: root.value would access value in the instance of Node referred to by toot.
Node.left is how it would be coded if left was static.
Re: Binary Search Tree inorder tree traversal
I've changed my code quite substantially, and now I have seem to have got a working bit of code, however now when I run it in the command window I get the following error which I can't seem to make sense of:
Exception in thread "main" java.lang.NoClassDefFoundError: BinarySearchTree (wro
ng name: binary/search/tree/BinarySearchTree)
at java.lang.ClassLoader.defineClass1(Native Method)
at java.lang.ClassLoader.defineClass(ClassLoader.java :791)
at java.security.SecureClassLoader.defineClass(Secure ClassLoader.java:14
2)
at java.net.URLClassLoader.defineClass(URLClassLoader .java:449)
at java.net.URLClassLoader.access$100(URLClassLoader. java:71)
at java.net.URLClassLoader$1.run(URLClassLoader.java: 361)
at java.net.URLClassLoader$1.run(URLClassLoader.java: 355)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.j ava:354)
at java.lang.ClassLoader.loadClass(ClassLoader.java:4 23)
at sun.misc.Launcher$AppClassLoader.loadClass(Launche r.java:308)
at java.lang.ClassLoader.loadClass(ClassLoader.java:3 56)
at sun.launcher.LauncherHelper.checkAndLoadMain(Launc herHelper.java:482)
My code now looks like:
Code :
public class BinarySearchTree {
//set up node with fields
//determining the node's
//placement in the tree
//relative to the nodes around it
public class Node {
public Node parent;
public Node left;
public Node right;
private int value;
public Node(int value){
this.parent = null;
this.left = null;
this.right = null;
this.value = value;
}
public int getValue(){
return this.value;
}
public void setValue(int value){
this.value = value;
}
}
private Node root;
//Construct the Binary Search Tree with current root = null
public BinarySearchTree(){
this.root = null;
}
public Node returnRoot(){
return root;
}
public void insertNode(int id)
{
Node newNode = new Node(id);
newNode.value = id;
if (root == null){
root = newNode;
}
else {
Node current = root;
Node parent;
while(true)
{
parent = current;
if(id < current.value)
{
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}
else {
if(current==null){
parent.right = newNode;
return;
}
}
}
}
}
public void sortedList(Node node){
if (root != null) {
sortedList( node.left );
System.out.println(node.value + " ");
sortedList( node.right );
}
}
public static void main(final String[] args)
{
int value;
BinarySearchTree tree1 = new BinarySearchTree();
tree1.insertNode(7);
tree1.insertNode(1);
tree1.insertNode(0);
tree1.insertNode(9);
tree1.insertNode(3);
tree1.insertNode(6);
tree1.insertNode(2);
tree1.insertNode(4);
tree1.insertNode(5);
tree1.insertNode(8);
System.out.println("Sorted list of integers from tree: ");
tree1.sortedList(tree1.returnRoot());
}
}
and when I have it written in Netbeans it doesn't flag up any errors.
Thanks for the help.
Re: Binary Search Tree inorder tree traversal
Quote:
Exception in thread "main" java.lang.NoClassDefFoundError: BinarySearchTree (wro
ng name: binary/search/tree/BinarySearchTree)
That long name is for the case where the class is in the package: binary.search.tree
The full package.classname must be specified with the java command when trying to execute the class.
The IDE hides all that.
Re: Binary Search Tree inorder tree traversal
When I try to run it in Netbeans, it just seems to run forever, I left it going for over 20 mins and it didn't complete the running process?
Re: Binary Search Tree inorder tree traversal
Sounds like an infinite loop. Add some printlns to show where the code is executing and what the values of the variables are as they are used. The print out will show you where the loop is.
Re: Binary Search Tree inorder tree traversal
I've narrowed it down to the while section in my code I've tried implementing a count system so that it acts while the count is below a certain number.
Code :
public static int count = 1;
.
.
.
while(count < 10)
{
parent = current;
if(id < current.value)
{
current = current.left;
if(current==null){
parent.left = newNode;
count++;
return;
}
}
else {
if(current==null){
parent.right = newNode;
count++;
return;
}
}
}
I'm entering 10 numbers into the tree so I assumed if I started the count at 1 and said for count < 10 it would have to stop. However it still seems to be an infinite loop and no matter how low I make the while expression it doesn't stop running. If I take away the while statement it runs the iteration once and stops.
--- Update ---
Update: for count < 3 it works but only produces the first three integers from my main method. For any more it seems to become infinite
--- Update ---
Update: I've finally managed to get it to work but for some reason I need to set the count to be less than an arbitrarily high number. Right now 100 suffices, but is there any way I could set the count to be less than a number that would work for any number of integers added?
Re: Binary Search Tree inorder tree traversal
Quote:
I need to set the count
What is the count? Is it used when debugging the code to keep the output down to a reasonable size?
Once the bug is fixed the debug count can be commented out of the source.
