Link to home
Start Free TrialLog in
Avatar of Lee25D
Lee25D

asked on

Inorder traversal in a BST

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!
Avatar of rachel83
rachel83

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.
Avatar of Lee25D

ASKER

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.
Avatar of Lee25D

ASKER

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!
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)
Avatar of Lee25D

ASKER

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)."
Avatar of Lee25D

ASKER

I'm done with this, but thanks for your help!
ASKER CERTIFIED SOLUTION
Avatar of rachel83
rachel83

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial