3 Replies - 1517 Views - Last Post: 07 December 2012 - 10:53 AM Rate Topic: -----

#1 infiniteuse  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 24-February 11

Building a Binary Search Tree Non-Recursively

Posted 06 December 2012 - 06:52 PM

Hello guys/girls,

I'm trying to provide a public method that builds a Binary Search Tree based on an input file of an unknown number of positive integers, one per line. The problem is, from my little knowledge/experience, I cannot utilize recursion because it is required to prompt the user for an input file within the method. This must also be the only method created.

This is the TreeNode class:

public static class TreeNode
{
   TreeNode LeftLink;
   int      Content;
   TreeNode RightLink;
}
// end class TreeNode


And here is the code I have so far:

public static TreeNode BuildSearchTree() throws IOException
{
   TreeNode T = new TreeNode();
   
 //Prompt User for FileName
   System.out.println("Enter file name:");
   
   Scanner   Scan = new Scanner(System.in);
   String    FileName = Scan.next();
   Scanner   InFile = new Scanner (new File(FileName));
   int       Key = 0;

   //Create Binary Search Tree
   while(InFile.hasNext())
   {
	   Key = InFile.nextInt();
	   
	   if (Key < T.Content)
		   
		   if (T.LeftLink != null) 
		   {
			   T = T.LeftLink; 
		   }
	   	   //end if
	   
		   else
		   {
			 //System.out.println("  Inserted " + Key + " to left of Node " + T.Content);
			   T.LeftLink = new TreeNode();
			   T.LeftLink.Content = Key;
		   } 
	   	   //end if
	   
	   else if (Key > T.Content)
		   
		   if (T.RightLink != null) 
		   {
			   T = T.RightLink;
		   }
	   	   //end if
	   
		   else
		   {
			 //System.out.println("  Inserted " + Key + " to right of Node " + T.Content);
			   T.RightLink = new TreeNode();
			   T.RightLink.Content = Key;
		   }
	   	   //end else if
   }
   //end while
   return T;
}
// end method BuildSearchTree


I can see the problem is I'm not adding additional "Nodes" to the Tree. I'm a little stumped as to how to do this, any help in the right direction would be greatly appreciated!

Is This A Good Question/Topic? 0
  • +

Replies To: Building a Binary Search Tree Non-Recursively

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Building a Binary Search Tree Non-Recursively

Posted 07 December 2012 - 06:25 AM

You should really have an insert() method which handles inserting a certain element. You can handle it recursively or iteratively.

For an iterative solution, you would check if the newValue is less than or greater than the value of the current node. If less, go to the left child. If greater than, go to the right child. If that particular child is null, that's where you insert the element.
Was This Post Helpful? 1
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5932
  • View blog
  • Posts: 12,854
  • Joined: 16-October 07

Re: Building a Binary Search Tree Non-Recursively

Posted 07 December 2012 - 09:18 AM

You need a while, to loop through all the nodes of the tree for the insert. Also, you need two nodes. One is your root, the other is the node you're using to walk the tree. The root should start out null and be filled with the first value. Put a constructor on that node. Get rid of all the static.

Also, I agree, you really want a tree class. e.g:
class Tree {
	private class Node { // no one but the tree should have access to the node
		public int data;
		public Node left, right;
		public Node(int data) { this.data = data; }
	}
	Node root;
	public void insert(int data) { /* your code here */ }
}


Was This Post Helpful? 2
  • +
  • -

#4 infiniteuse  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 24-February 11

Re: Building a Binary Search Tree Non-Recursively

Posted 07 December 2012 - 10:53 AM

Excellent, thanks for the help guys. Got it working.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1