Solved

Inorder traversal in a BST

Posted on 2010-11-07
7
942 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…

756 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