Solved

Inorder traversal in a BST

Posted on 2010-11-07
7
944 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
What Is Transaction Monitoring and who needs it?

Synthetic Transaction Monitoring that you need for the day to day, which ensures your business website keeps running optimally, and that there is no downtime to impact your customer experience.

 
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

Salesforce Made Easy to Use

On-screen guidance at the moment of need enables you & your employees to focus on the core, you can now boost your adoption rates swiftly and simply with one easy tool.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
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.

691 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