Solved

Inorder traversal in a BST

Posted on 2010-11-07
7
943 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
Industry Leaders: 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: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering 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

Title # Comments Views Activity
How do I remove an object from a 3 60
Convert from a json string array to a Java object 3 80
What browser will run Java? 7 171
passing enum to a method 4 48
Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses

739 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