Java RSS Java RSS

Help implementing a binary search tree in Java

Reply

•
•
Join Date: Jul 2007
Posts: 34
Reputation: baltazar is an unknown quantity at this point 
Solved Threads: 0
baltazar baltazar is offline Offline
Light Poster

Help implementing a binary search tree in Java

 
0
  #1
Jul 15th, 2007
I need to implement a Binary search tree in Java (only insert and find) and then should be able to display the tree.
This is the code I've come up with so far. But I get the nullpointer exception. I am getting this because the two pointers in my node, leftChild and rightChild are set to null and don't point anywhere. But I don't know how to fix this. How do I make it so that they point to the correct nodes?

Java Syntax (Toggle Plain Text) 
  1. import java.util.*;
  2.  
  3. public class RBTTree
  4. {
  5.  
  6. 	RBTNode root = null; //Root node of the tree
  7. 	RBTNode currentNode = null;
  8.  
  9. //Checks to see if tree is empty. Prints out message if it is.
  10. 	void IsEmpty()
  11. 	{
  12. 		if(root == null)
  13. 			System.out.println("Tree is Empty");
  14. 	}//End of IsEmpty
  15.  
  16. 	RBTNode create(int number)
  17. 	{
  18. 		RBTNode node = new RBTNode();
  19. 		node.number = number;
  20. 		node.parent = null;
  21. 		node.leftChild = null;
  22. 		node.rightChild = null;
  23. 		//System.out.println("Node.data is: " +node.data);
  24. 		return node;
  25. 	}
  26.  
  27. //Method to insert a number into the tree.
  28. 	public void insert(int number)
  29. 	{
  30. 		IsEmpty();
  31.  
  32. 		root = insert (root,number);
  33.  
  34. 		System.out.println("Node just inserted: " + root.number);
  35. 		System.out.println("Node's left child: " + root.leftChild);
  36. 		System.out.println("Node's right child: " + root.rightChild);
  37. 	}
  38.  
  39. 	RBTNode insert(RBTNode node, int number)
  40. 	{
  41. 		if(node == null)// create a new node.
  42. 		{
  43. 			node = create(number);
  44. 		}
  45. 		else if(number < node.number)// if the number is less than the node, go to the left child.
  46. 		{
  47. 			node.leftChild = insert(node.leftChild,number);
  48. 		}
  49. 		else if(number > node.number)// if the number is greater than the node, go to the right child
  50. 		{
  51. 			node.rightChild = insert(node.rightChild,number);
  52. 		}
  53. 		else if(number == node.number) //if the number already exists in the the tree, place it in the right child.
  54. 		{
  55. 			node.rightChild = insert(node.rightChild, number);
  56. 		}
  57.  
  58. 		return node;
  59. 	}// end BSTNode insert
  60.  
  61.  
  62. 	public void find(int number)
  63. 	{
  64. 		IsEmpty();
  65.  
  66. 		currentNode = find(root, number);
  67.  
  68. 		System.out.println("Search returned Node: " + currentNode.number);
  69. 		System.out.println("Node's left child: " + currentNode.leftChild);
  70. 		System.out.println("Node's right child: " + currentNode.rightChild);
  71.  
  72. 	}//End of find
  73.  
  74. 	RBTNode find(RBTNode currentNode, int number)
  75. 	{
  76. 		//currentNode = root; //sets the root node to the current node for searching purposes
  77.  
  78. 		while(currentNode.number != number && currentNode != null)
  79. 		{
  80. 			if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
  81. 			{
  82. 				currentNode = currentNode.leftChild;
  83. 			}
  84. 			else if(number > currentNode.number)//if number we are searching for is greater than the node search right sub tree
  85. 			{
  86. 				currentNode = currentNode.rightChild;
  87. 			}
  88. 			else	//if number we are searching for is equal to the node search right sub tree
  89. 			{
  90. 				currentNode = currentNode.rightChild;
  91. 			}
  92. 		}
  93.  
  94. 		return currentNode;
  95.  
  96. 	}//End of RBTNode find
  97.  
  98.  
  99. //Print all items.
  100.     public void printTree( )
  101.     {
  102.         display(root);
  103.     }
  104.  
  105. 	private void display(RBTNode currentNode)
  106. 	{
  107. 		if(root == null)
  108. 			System.out.println("Empty Tree. Nothing to display");
  109.  
  110.         else
  111.         {
  112.             display(currentNode.leftChild);
  113.             System.out.println(currentNode.number);
  114.             display(currentNode.rightChild);
  115.         }
  116.  
  117.  
  118. 	}//End of display
  119.  
  120. 	public static void main(String[] args)
  121. 	{
  122. 		RBTTree RBT = new RBTTree();
  123.  
  124. 		Scanner console = new Scanner(System.in);
  125.  
  126. 		System.out.println("How many numbers would you like to enter into the Red Black Tree?");
  127. 		int k = console.nextInt();
  128.  
  129. 		int inputarray[] = new int[k];
  130.  
  131. 		for(int i=0; i< k; i++)
  132. 		{
  133.  
  134. 			System.out.println("Please enter the " + (i+1)+ " number: ");
  135. 			inputarray[i]= console.nextInt();
  136. 		}
  137.  
  138. 		for(int i=0; i<k; i++)
  139. 		{
  140. 			RBT.insert(inputarray[i]);
  141. 		}
  142. 	}
  143.  
  144.  
  145. }//end of class RBTTree

My RBTNode is here
Java Syntax (Toggle Plain Text) 
  1.  
  2.  
  3. class RBTNode
  4. {
  5. 	int number;
  6. 	RBTNode parent;
  7. 	RBTNode leftChild;
  8. 	RBTNode rightChild;
  9.  
  10. }
Last edited by baltazar; Jul 15th, 2007 at 11:41 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 102
Reputation: TheGathering is an unknown quantity at this point 
Solved Threads: 10
TheGathering's Avatar
TheGathering TheGathering is offline Offline
Junior Poster

Re: Help implementing a binary search tree in Java

 
0
  #2
Jul 16th, 2007
Java Syntax (Toggle Plain Text) 
  1. import java.util.*;
  2.  
  3. public class RBTTree
  4. {
  5.  
  6. 	public RBTNode root = null; //Root node of the tree
  7. 	RBTNode currentNode = root;
  8.  
  9. //Checks to see if tree is empty. Prints out message if it is.
  10. 	public boolean IsEmpty()
  11. 	{
  12. 		if(root == null)
  13. 			return true;
  14. 		return false;
  15. 	}//End of IsEmpty
  16.  
  17. 	RBTNode create(int number)
  18. 	{
  19. 		RBTNode node = new RBTNode();
  20. 		node.number = number;
  21. 		node.parent = null;
  22. 		node.leftChild = null;
  23. 		node.rightChild = null;
  24. 		//System.out.println("Node.data is: " +node.data);
  25. 		return node;
  26. 	}
  27.  
  28. //Method to insert a number into the tree.
  29. 	public void insert(int number)
  30. 	{	
  31.  
  32.  
  33. 		currentNode = add (root,number);
  34. 		if(IsEmpty() == true && currentNode != null)
  35. 		root = currentNode;
  36. 		currentNode = root;
  37. 	}
  38.  
  39. 	RBTNode add(RBTNode node, int number)
  40. 	{
  41. 		if(node == null)// create a new node.
  42. 		{
  43. 			node = create(number);
  44. 			return node;
  45.  
  46. 		}
  47. 		else if(number < node.number)// if the number is less than the node, go to the left child.
  48. 		{
  49. 			if(node.leftChild != null)
  50. 			add(node.leftChild,number);
  51. 			else
  52. 			node.leftChild = create(number);
  53.  
  54. 		}
  55. 		else if(number >= node.number)// if the number is greater than the node, go to the right child
  56. 		{
  57. 			if(node.rightChild != null)
  58. 			 add(node.rightChild,number);
  59. 			else
  60. 			node.rightChild = create(number);
  61.  
  62. 		}
  63.  
  64. 		 return null;
  65.  
  66. 	}// end BSTNode insert
  67.  
  68.  
  69. 	public void find(int number)
  70. 	{
  71. 		IsEmpty();
  72.  
  73. 		currentNode = find(root, number);
  74.  
  75. 		System.out.println("Search returned Node: " + currentNode.number);
  76. 		System.out.println("Node's left child: " + currentNode.leftChild);
  77. 		System.out.println("Node's right child: " + currentNode.rightChild);
  78.  
  79. 	}//End of find
  80.  
  81. 	RBTNode find(RBTNode currentNode, int number)
  82. 	{
  83. 		//currentNode = root; //sets the root node to the current node for searching purposes
  84.  
  85. 		while(currentNode.number != number && currentNode != null)
  86. 		{
  87. 			if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
  88. 			{
  89. 				currentNode = currentNode.leftChild;
  90. 			}
  91. 			else if(number > currentNode.number)//if number we are searching for is greater than the node search right sub tree
  92. 			{
  93. 				currentNode = currentNode.rightChild;
  94. 			}
  95. 			else	//if number we are searching for is equal to the node search right sub tree
  96. 			{
  97. 				currentNode = currentNode.rightChild;
  98. 			}
  99. 		}
  100.  
  101. 		return currentNode;
  102.  
  103. 	}//End of RBTNode find
  104.  
  105.     public RBTNode getRoot()
  106.     {return root;}
  107.  
  108. 	private void display(RBTNode input)
  109. 	{
  110.  
  111. 		if(input == null)
  112. 		{
  113. 		return;
  114. 		}
  115.  
  116. 		display(input.leftChild);
  117. 		System.out.println(input.number);
  118. 		display(input.rightChild);
  119.  
  120.  
  121. 	}//End of display
  122.  
  123. 	public static void main(String[] args)
  124. 	{
  125. 		RBTTree RBT = new RBTTree();
  126.  
  127. 		Scanner console = new Scanner(System.in);
  128.  
  129. 		System.out.println("How many numbers would you like to enter into the Red Black Tree?");
  130. 		int k = console.nextInt();
  131.  
  132. 		int inputarray[] = new int[k];
  133.  
  134. 		for(int i=0; i< k; i++)
  135. 		{
  136.  
  137. 			System.out.println("Please enter the " + (i+1)+ " number: ");
  138. 			inputarray[i]= console.nextInt();
  139. 		}
  140.  
  141. 		System.out.println("\n\n****Display Start****");
  142. 		for(int i=0; i<k; i++)
  143. 		{
  144. 			RBT.insert(inputarray[i]);
  145. 		}
  146. 		RBT.display(RBT.getRoot());
  147. 	}
  148.  
  149.  
  150. }//end of class RBTTree
That's the way I've always implemented it and it works fine for me. Obviously format it the way you want to. Right now it's displaying with an In-Order traversal.


Example run of the program:
Java Syntax (Toggle Plain Text) 
  1. How many numbers would you like to enter into the Red Black Tre
  2. 10
  3. Please enter the 1 number:
  4. 7
  5. Please enter the 2 number:
  6. 10
  7. Please enter the 3 number:
  8. 2
  9. Please enter the 4 number:
  10. 14
  11. Please enter the 5 number:
  12. 3
  13. Please enter the 6 number:
  14. 1
  15. Please enter the 7 number:
  16. 2
  17. Please enter the 8 number:
  18. 20
  19. Please enter the 9 number:
  20. 14
  21. Please enter the 10 number:
  22. 9
  23.  
  24.  
  25. ****Display Start****
  26. 1
  27. 2
  28. 2
  29. 3
  30. 7
  31. 9
  32. 10
  33. 14
  34. 14
  35. 20
  36. Press any key to continue...



Note: There are probably leaner ways of coding it, but I went with that implementation for ease of traceability and understanding.


Okay, in truth I forgot what my own display method did and used that implementation because I was trying to work around false logic errors >.> <.<

:p
Last edited by TheGathering; Jul 16th, 2007 at 11:28 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 34
Reputation: baltazar is an unknown quantity at this point 
Solved Threads: 0
baltazar baltazar is offline Offline
Light Poster

Re: Help implementing a binary search tree in Java

 
0
  #3
Jul 17th, 2007
Thanks for your help, but I managed to figure out what was wrong.
What I am now getting stuck at is finding a node in the tree. My find method doesn't do what I want it to do. Basically, I want my find method to find the node I pass it, display the node's left and right children and print out an error if it cant find the node.
Can someone suggest what I should add/ change in my find method.
Java Syntax (Toggle Plain Text) 
  1. /*--------------------------------------------------
  2. Binary Tree Code
  3. ---------------------------------------------------*/
  4. import java.util.*;
  5.  
  6. public class RBTTree
  7. {
  8.  
  9. 	protected RBTNode root = null; //Root node of the tree
  10. 	protected RBTNode currentNode = null;
  11.  
  12. //Checks to see if tree is empty. Prints out message if it is.
  13. 	void IsEmpty()
  14. 	{
  15. 		if(root == null)
  16. 			System.out.println("Tree is Empty");
  17. 	}//End of IsEmpty
  18.  
  19. 	RBTNode create(int number)
  20. 	{
  21. 		RBTNode node = new RBTNode();
  22. 		node.number = number;
  23. 		node.leftChild = null;
  24. 		node.rightChild = null;
  25. 		return node;
  26. 	}
  27.  
  28. //Method to insert a number into the tree.
  29. 	public void insert(int number)
  30. 	{
  31. 		IsEmpty();
  32.  
  33. 		root = insert (root,number);
  34.  
  35. 		System.out.println("Node just inserted: " + root.number);
  36. 		System.out.println("Node's left child: " + root.leftChild);
  37. 		System.out.println("Node's right child: " + root.rightChild);
  38. 	}
  39.  
  40. 	RBTNode insert(RBTNode node, int number)
  41. 	{
  42. 		if(node == null)// create a new node.
  43. 		{
  44. 			node = create(number);
  45. 		}
  46. 		else if(number < node.number)// if the number is less than the node, go to the left child.
  47. 		{
  48. 			node.leftChild = insert(node.leftChild,number);
  49. 		}
  50. 		else if(number > node.number)// if the number is greater than the node, go to the right child
  51. 		{
  52. 			node.rightChild = insert(node.rightChild,number);
  53. 		}
  54. 		else if(number == node.number) //if the number already exists in the the tree, place it in the right child.
  55. 		{
  56. 			node.rightChild = insert(node.rightChild, number);
  57. 		}
  58.  
  59. 		return node;
  60. 	}// end BSTNode insert
  61.  
  62.  
  63. 	public void find(int number)
  64. 	{
  65. 		IsEmpty();
  66.  
  67. 		currentNode = find(root, number);
  68.  
  69. 		if (currentNode == null)
  70. 		{
  71. 			System.out.println("The number you are searching for does not exist in this tree");
  72. 		}
  73. 		else
  74. 		{
  75. 			System.out.println("Search returned Node: " + currentNode.number);
  76. 			System.out.println("Node's left child: " + currentNode.leftChild);
  77. 			System.out.println("Node's right child: " + currentNode.rightChild);
  78. 		}
  79.  
  80. 	}//End of find
  81.  
  82. 	RBTNode find(RBTNode currentNode, int number)
  83. 	{
  84. 		//currentNode = root; //sets the root node to the current node for searching purposes
  85.  
  86. 		while(currentNode.number != number && currentNode != null)
  87. 		{
  88. 			if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
  89. 			{
  90. 				currentNode = currentNode.leftChild;
  91. 			}
  92. 			else//if number we are searching for is greater than or equal to the node search right sub tree
  93. 			{
  94. 				currentNode = currentNode.rightChild;
  95. 			}
  96. 		}
  97.  
  98. 		return currentNode;
  99.  
  100. 	}//End of RBTNode find
  101.  
  102.  
  103. //Print all items.
  104.     public void printTree( )
  105.     {
  106.         IsEmpty();
  107.         display(root);
  108.     }
  109. //Displays tree via in-order traversal. i.e. displays the left child then the root and then the right child
  110. 	private void display(RBTNode currentNode)
  111. 	{
  112. 		if(currentNode == null)
  113. 			System.out.println(" ");
  114.  
  115.         else
  116.         {
  117.             display(currentNode.leftChild);
  118.             System.out.println(currentNode.number);
  119.             display(currentNode.rightChild);
  120.         }
  121.  
  122.  
  123. 	}//End of display
  124.  
  125. 	public static void main(String[] args)
  126. 	{
  127. 		RBTTree RBT = new RBTTree();
  128.  
  129.  
  130. 		Scanner console = new Scanner(System.in);
  131.  
  132. 		System.out.println("How many numbers would you like to enter into the Red Black Tree?");
  133. 		int k = console.nextInt();
  134. 		int input;
  135.  
  136. 		int inputarray[] = new int[k];
  137.  
  138. 		for(int i=0; i< k; i++)
  139. 		{
  140.  
  141. 			System.out.println("Please enter the " + (i+1)+ " number: ");
  142. 			inputarray[i]= console.nextInt();
  143. 		}
  144.  
  145. 		for(int i=0; i<k; i++)
  146. 		{
  147. 			RBT.insert(inputarray[i]);
  148. 		}
  149.  
  150. 		RBT.printTree();
  151.  
  152. 		do
  153. 		{
  154. 			System.out.println("Please enter the number you want to search for");
  155. 			int f = console.nextInt();
  156.  
  157. 			RBT.find(f);
  158.  
  159. 			System.out.println("Would you like to search for another number? (enter: 0= Yes/1 = No)");
  160. 			input = console.nextInt();
  161.  
  162. 		}while(input == 0);
  163.  
  164.  
  165. 	}
  166.  
  167.  
  168. }//end of class RBTTree
Last edited by baltazar; Jul 17th, 2007 at 3:56 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 102
Reputation: TheGathering is an unknown quantity at this point 
Solved Threads: 10
TheGathering's Avatar
TheGathering TheGathering is offline Offline
Junior Poster

Re: Help implementing a binary search tree in Java

 
0
  #4
Jul 17th, 2007
Here's a find method that does what you want it to and works with the code I have:



Java Syntax (Toggle Plain Text) 
  1. 	public void find(int number)
  2. 	{
  3. 		IsEmpty();
  4.  
  5. 		currentNode = find(root, number);
  6.  
  7. 		if (currentNode == null)
  8. 		{
  9. 			System.out.println("The number you are searching for does not exist in this tree");
  10. 		}
  11. 		else
  12. 		{
  13. 			System.out.println("Search returned Node: " + currentNode.number);
  14. 			System.out.println("Node's left child: " + currentNode.leftChild);
  15. 			System.out.println("Node's right child: " + currentNode.rightChild);
  16. 		}
  17.  
  18. 	}//End of find
  19.  
  20. 	RBTNode find(RBTNode tempNode, int number)
  21. 	{
  22. 			if(tempNode.number == number)
  23. 				return tempNode;
  24. 			else if(tempNode.number < number && tempNode.rightChild !=null)
  25. 				return find(tempNode.rightChild, number);
  26. 			else if(tempNode.number > number && tempNode.leftChild != null)
  27. 				return find(tempNode.leftChild, number);
  28. 			else
  29. 			return null;
  30. 	}//End of RBTNode find


Enjoy!
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the Java Forum
Thread Tools Search this Thread



android api applet application apps array arrays automation awt bidirectional binary birt bluetooth businessintelligence busy_handler(null) card chat class classes client code collision columns component constructor crashcourse database designadrawingapplicationusingjavajslider draw eclipse error errors eventlistener exception expand fractal game givemetehcodez graphics gui guidancer html ide image inetaddress integer intellij j2me java javadoc javafx javamicroeditionuseofmotionsensor javaprojects jme jni jpanel jtree julia linux list loop machine map method methods mobile mobiledevelopmentcreatejar myaggfun netbeans newbie oracle plazmic print problem program programming project radio recursion scanner server set sharepoint smart sms smsspam sort sortedmaps sql string subclass support swing textfield threads tree unlimited utility webservices windows
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC