Solved

Inorder traversal in a BST

Posted on 2010-11-07
7
931 Views
Last Modified: 2012-08-13
I have some trouble with creating large binary trees that reads input from the user, and routines to print out binary trees in human-readable format(Using two methods, one a text-based method and the second, a graphical method that draws the trees using lines and circles on a canvas)
I start from a Binary Tree implementation and augment this class to support bulk insertion of integer values. Insertions will be specified in the form of a text string in JSON.
This is what I have for this part:
public class BST {
    class BinaryNode
	{
		int element;       // The data in the node
		BinaryNode left;   // Left child
		BinaryNode right;  // Right child
		int inorderseq; //inorder sequence x
		int height; //height y

		// Constructors
		BinaryNode(int theElement){
			this(theElement, null, null,0);
		}

		BinaryNode(int theElement, BinaryNode lt, BinaryNode rt, int seq )
		{
			element  = theElement;
			left     = lt;
			right    = rt;
			inorderseq	= seq;
		}
	}

	/*
	* Implements an unbalanced binary search tree.
	*/


	public class BinarySearchTree 
	{
		/** The tree root. */
		public BinaryNode root;
		
	                // create an array to stores the bulk insert data 
		int [] arr;

		/**
		 * Construct the tree.
		 */
		public BinarySearchTree( )
		{
			root = null;
		}

		public void insert(int x)
		{
			root = insert( x, root );
		}


		/**
		 * Internal method to insert into a subtree.
		 */
		public BinaryNode insert(int x, BinaryNode t)
		{
			if( t == null )
				return new BinaryNode( x, null, null, 0 );
			if(x < t.element)
				t.left = insert( x, t.left );
			else if(x > t.element)
				t.right = insert( x, t.right );
			else
				;  // Duplicate; do nothing
			return t;
		}
		
		//implementation of the function BulkInsert 
		void BulkInsert(String s){
	    	System.out.println("Enter a s string: " + s);
	    	s = s.substring(1, s.length() - 2);
	    	Scanner sc = new Scanner(s).useDelimiter(", ");
	    	while(sc.hasNextInt() ){
	    		System.out.println( "" + sc.nextInt()); 
	    		insert(sc.nextInt());
	    	}
	    }		
	}

Open in new window

I'm not sure if my BulkInsert function is right. Can someone take a look at it?

This class has to support textual printing of the values in the trees. I have to logically assign an (x, y) coordinate to each tree node. It is appropriate for the x-coordinate of the node to be proportional to the inorder traversal number of the node in the tree, and for the y-coordinate of the node to be proportional to the the depth of the node in the tree.Therefore, I will need member variables to store, and routines to compute the inorder traversal number and depth of each node in the tree. Then write a member routine void PrintText() that prints a binary tree to screen.
For example, printing the binary search tree resulting from the bulk insertion ”[12, 15, 76, 23, 99]” should look something like:
12
   15
      76
    23 99
-So I think I have to create a recursive inorder traversal function. The height y increases by 1 when I visit the left/ right node. At the right node, the inorder sequence x increases by 1 as well. So this is what I have:
 
void inOrderTraversal(BinaryNode bNode){
                               if (bNode ==null) return;	    	
	    	bNode.height += 1;
	    	inOrderTraversal (bNode.left);    	
	    	System.out.println(bNode.element);
	    	bNode.height += 1;
	    	inOrderTraversal (bNode.right);     
}

Open in new window

I'm not sure how to apply x and y in the function PrintText though. Any hints?


I'd appreciate any feedback!
0
Comment
Question by:Lee25D
  • 4
  • 3
7 Comments
 
LVL 2

Expert Comment

by:rachel83
ID: 34092079
Hello!

Is there a reason why BinaryNode and BinarySearchTree are sub-classes? Shouldn't they be classes on their own? I think it would be simpler.

Your BulkInsert method is a bit confusing. I am not sure why you pass a String parameter to this method when actually the String is meant to be taken from the command line user input. I think you should get rid of this parameter and just use a local variable instead.

Please let me know if I have understood correctly.
0
 

Author Comment

by:Lee25D
ID: 34097853
Thanks for responding! Because the assignment requires to submit 2 java files only, so the first file is BinarySearchTree.java and the second one contains the main method. The assignment also requires to pass a String parameter to the function BulkInsert.
0
 

Author Comment

by:Lee25D
ID: 34097963
Now that you've mentioned it, I think it should be:
public class BST {
    class BinaryNode
      {
            int element;       // The data in the node
            BinaryNode left;   // Left child
            BinaryNode right;  // Right child
            int inorderseq; //inorder sequence x
            int height; //height y

            // Constructors
            BinaryNode(int theElement){
                  this(theElement, null, null,0);
            }

            BinaryNode(int theElement, BinaryNode lt, BinaryNode rt, int seq )
            {
                  element  = theElement;
                  left     = lt;
                  right    = rt;
                  inorderseq      = seq;
            }
      }

      /*
      * Implements an unbalanced binary search tree.
      */

            /** The tree root. */
            public BinaryNode root;
            
                      // create an array to stores the bulk insert data
            int [] arr;

            /**
             * Construct the tree.
             */
            public BST( )
            {
                  root = null;
            }

I'm sorry for the confusion!
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 2

Expert Comment

by:rachel83
ID: 34098101
Ok, I see. I think it would be better to have the two separate files as:

BinaryNode.java
BinarySearchTree.java

and have your main method in the BinarySearchTree class. Otherwise, it seems like a waste of a class simply having a main method in it. Remember, your main method can go in any class, it doesn't need to be on its own. As you are only allowed 2x .java files, I should think you are only meant to use 2x classes (i.e. not use extra subclasses). But it's up to you!

If you are required to pass a String to the bulkInsert method then what made you think you had to get user input from the command line? (i.e. with the Scanner object you used)
0
 

Author Comment

by:Lee25D
ID: 34098276
The assignment also specifies to submit BST.java and driver.java. So my guess is one file contains the BST and the other one contains the main method. After I implement the PrintText function, I also have to implement a function called PrintCanvas that prints a tree on a graphical canvas. But let's talk about that later.
About the BulkInsert function, I think the assignment requires that. It says "Insertions will be specified in the form of a text string in JSON (JavaScript Object Notation). The JSON string ”[12, 15, 76, 23, 99]” should result in an insertion of 12, followed by an insertion of 15,etc. Implement this as a member function void BulkInsert(String s)."
0
 

Author Comment

by:Lee25D
ID: 34099273
I'm done with this, but thanks for your help!
0
 
LVL 2

Accepted Solution

by:
rachel83 earned 500 total points
ID: 34100453
Ah I understand. Ok, that sounds fine.

From that description, I would say you don't need the Scanner object. Instead, the JSON String will be passed to the BulkInsert method as a parameter.

Does this answer all of your questions?
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now