CS 112 Lab 7

We will see how to optimally bulk insert an input array of integers into a Binary Search Tree (BST).

We will see how to display a BST using graphics primitives.

package lab07;
 
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import java.util.*;
 
import sun.security.action.GetLongAction;
 
class BSTNode {
    int nodeValue;
    int nodeDepth;
    BSTNode parent, leftChild, rightChild;
    
    // Used to store the position of this node in its levelOrder depth.
    int levelOrderPosition;
    
    // Used to store the in-order sequence number of this node
    int inOrderSequence;
    BSTNode( int nodeValue, int nodeDepth ){
        this.nodeValue = nodeValue;
        this.nodeDepth = nodeDepth;
        parent = leftChild = rightChild = null;
    }
    void setLeftChild( BSTNode leftChild ){ 
        this.leftChild = leftChild;
        if( leftChild != null ) leftChild.parent = this;
    }
    void setRightChild( BSTNode rightChild ){
        this.rightChild = rightChild; 
        if( rightChild != null ) rightChild.parent = this;
    }
    void setLevelOrderPosition( int levelOrderPosition ){ 
        this.levelOrderPosition = levelOrderPosition; 
    }
    void setInOrderSequence(int inOrderSequence){ 
        this.inOrderSequence = inOrderSequence; 
    }
    int getNodeValue(){ return nodeValue; }
    int getNodeDepth(){ return nodeDepth; }
    int getLevelOrderPosition(){ return levelOrderPosition; }
    int getInOrderSequence(){ return inOrderSequence; }
    BSTNode getParent(){ return parent; }
    BSTNode getLeftChild(){ return leftChild; }
    BSTNode getRightChild(){ return rightChild; }
}
 
public class BST {
    BSTNode rootNode;
    int inOrderCounter; // will be useful to assign inOrderSequence numbers
    int [] dataArray; // stores the bulk insert data array
    BST(){ rootNode = null; }
    
    void bulkInsertOptimal( int [] dataArray ){
        quicksort(dataArray, 0, dataArray.length - 1);
        dataArray = removeDuplicates(dataArray);
        rootNode = createSubTree(0, dataArray, 0, dataArray.length - 1);
        this.dataArray = dataArray;
    }
    
    BSTNode createSubTree(int subTreeDepth, int [] dataArray, 
                            int startIndex, int endIndex){
        // base case for recursion
        if( startIndex > endIndex )
            return null;
        
        // TASK: fill in the ??? for the following lines
        int midIndex = (startIndex + endIndex)/2;
        BSTNode subTreeRoot = /*???*/; // Create a new BSTNode with nodeValue from
                                       // dataArray at midIndex and with correct depth
        
        BSTNode leftSubTree = /*???*/; // Right hand side is recursive call to createSubTree
                                       // to create the left-sub-tree of subTreeRoot 
                                       // specify correct arguments for:
                                       // depth, start & end index 
        
        BSTNode rightSubTree = /*???*/; // Right hand side is recursive call to createSubTree
                                        // to create the right-sub-tree of subTreeRoot 
                                        // specify correct arguments for:
                                        // depth, start & end index
        
        subTreeRoot.setLeftChild(leftSubTree);
        subTreeRoot.setRightChild(rightSubTree);
        
        return subTreeRoot;
    }
    public void addGraphicsLabVersion(Graphics g, int window_w, int window_h){
        LinkedList<BSTNode> levelOrderQueue = new LinkedList<BSTNode>();
        
        int curDepth = -1;
        int levelOrderPosition = 0;
        levelOrderQueue.add(rootNode);
        while( !levelOrderQueue.isEmpty() ){
            // Get current node from the queue
            BSTNode curNode = levelOrderQueue.remove();
            if( curNode.getNodeDepth() != curDepth ){
                levelOrderPosition = 0;
                curDepth = curNode.getNodeDepth();
            }
            curNode.setLevelOrderPosition(levelOrderPosition);
            
            // TASK: fill in the ??? for the following lines 
            int curNode_x = /*???*/; // Use getNodeX with getLevelOrderPosition
                                     // for curNode 
            int curNode_y = /*???*/; // Use getNodeY with getNodeDepth for curNode
            
            // Display current node at coordinates (curNode_x, curNode_y) 
            drawNumberCircle(g, curNode.getNodeValue(), curNode_x, curNode_y);
            
            if( curDepth != 0 ){
                // Following code is to draw line connecting currentNode and its
                // parent node
                BSTNode parentNode = curNode.getParent();
                // TASK: fill in the ??? for the following lines
                int parentNode_x = /*???*/; // Use getNodeX with getLevelOrderPosition
                                             // for parentNode  
                int parentNode_y = /*???*/; // Use getNodeY with getNodeDepth 
                                            // for parentNode
                // Draw the connecting line.
                drawLine(g, curNode_x, curNode_y, parentNode_x, parentNode_y);
            }
            
            levelOrderPosition++;
            if( curNode.getLeftChild() != null )
                levelOrderQueue.add(curNode.getLeftChild());
            if( curNode.getRightChild() != null )
                levelOrderQueue.add(curNode.getRightChild());
        }
    }
 
    void inOrderTraversal( BSTNode treeNode ){
        // NOTE: Complete this method for homework version of BST display.
        
        // Perform in-order traversal of the tree to assign inOrderSequence 
        // numbers for all nodes in the tree. 
    }
    public void addGraphicsHWVersion(Graphics g, int window_w, int window_h){
        // NOTE: Complete this method for homework version of BST display.
        
        // First invoke inOrderTraversal to assign inOrderSequence numbers for
        // all nodes in the BST.
        
        // Use code similar to addGraphicsLabVersion but with levelOrderPosition
        // replaced with inOrderSequence to determine node_x values
    }
    
    // The following are graphics helper methods, no change is needed
    static int node_diameter = 40;
    public void displayDataArray(Graphics g, int window_w, int window_h){
        
        int y_offset = node_diameter;
        int x_offset = (window_w - node_diameter * dataArray.length)/2;
        for( int i = 0; i < dataArray.length; i++ )
        {
            g.setColor(Color.ORANGE);
            g.drawRect(x_offset, y_offset , node_diameter , node_diameter );
            g.setColor(Color.RED);
            g.setFont(new Font("Verdana",Font.BOLD,15));
            int x = x_offset + node_diameter/2 - 12;
            int y = y_offset + node_diameter/2 + 5;
            g.drawString(""+dataArray[i], x , y);
            g.setColor(Color.BLUE);
            g.drawString(""+i, x, y + node_diameter);
            x_offset += node_diameter;
        }
    }
    int getNodeX(int xPosition){
        return (int)(1.2 * node_diameter * xPosition) + node_diameter;
    }
    int getNodeY(int nodeDepth){
        return 2 * node_diameter * nodeDepth + (int)(3.5 * node_diameter);
    }
    // Draws a circle at coordinates (node_x, node_y) with the node_value inside 
    void drawNumberCircle(Graphics g, int node_value, int node_x, int node_y)
    {
        g.setColor(Color.ORANGE);
        g.fillOval( node_x, node_y, node_diameter, node_diameter );
        g.setColor(Color.RED);
        g.setFont(new Font("Verdana",Font.BOLD,15));
        g.drawString( ""+node_value, node_x + node_diameter/2 - 12, node_y + node_diameter/2 +5 );
    }
 
    // Draws a line between node1 coordinates (node1_x, node1_y) 
    // and node2 coordinates (node2_x, node2_y)
    void drawLine( Graphics g, int node1_x, int node1_y, int node2_x, int node2_y)
    {
        int radius = node_diameter / 2;
        int x1 = node1_x + radius;
        int y1 = node1_y + radius;
        int x2 = node2_x + radius;
        int y2 = node2_y + radius;
        double dist = Math.sqrt(Math.pow((x1 - x2), 2)+Math.pow((y1 - y2), 2));
        double alpha1 = radius / dist;
        double alpha2 = (dist - radius) / dist;
        int xn1 = (int)(alpha1 * x1 + (1 - alpha1) * x2);
        int yn1 = (int)(alpha1 * y1 + (1 - alpha1) * y2);
        int xn2 = (int)(alpha2 * x1 + (1 - alpha2) * x2);
        int yn2 = (int)(alpha2 * y1 + (1 - alpha2) * y2);
        
        g.setColor(Color.GRAY);
        g.drawLine(xn1, yn1, xn2, yn2);
    }
    
    int [] removeDuplicates( int [] sortedArray ){
        int [] uniquesArray = null;
        int uniqueCount = 0;
        for( int pass = 1; pass <= 2; pass++ ){
            if( pass == 2 )
                uniquesArray = new int[uniqueCount];
            int i = 0, j = 0;
            while( i < sortedArray.length ){
                if( pass == 1 )
                    uniqueCount++;
                else
                    uniquesArray[j++] = sortedArray[i];
                i++;
                while( i < sortedArray.length && sortedArray[i] == sortedArray[i-1] )
                    i++;
            }
        }
        return uniquesArray;
    }
    // Quicksort elements of the array A between a and b inclusive
    void quicksort (int [] A, int a, int b) {
 
        if (a < b)  
        {   
           int pivot = A[b];        // or choose one element at random, swap into index b
           int l = a; 
           int r = b-1;
 
           // Keep pivoting until the l and r indices cross over.
           while (l <= r) {
 
               while (l <= r && A[l] <= pivot)    // slide l right until it points to an
               l++;                           //  element larger than pivot
 
               while (l <= r && A[r] >= pivot)    // slide r left until it points to an
               r--;                           //  element smaller than pivot
 
               if (l < r){                         // swap out-of-order pairs 
                   int temp = A[l]; A[l] = A[r]; A[r] = temp; 
               }
           }
           //  Re-position the pivot into its correct slot
           int temp = A[l]; A[l] = A[b]; A[b] = temp;
 
           quicksort (A, a, l-1);
           quicksort (A, l + 1, b);
        }
    }
}

package lab07;
 
import java.awt.*;
import javax.swing.*;
import java.util.*;
import java.awt.event.*;
 
public class BSTClient extends javax.swing.JFrame implements MouseListener
{
    BST bst;
    public BSTClient()
    {
        Random rand = new Random(12345);
        int [] dataArray = new int[20];
        for( int i = 0; i < dataArray.length; i++ )
            dataArray[i] = rand.nextInt(90) + 10;
            
        bst = new BST();
        bst.bulkInsertOptimal(dataArray);
        
        setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
        setSize(1021, 521);
        setTitle("Binary Search Tree display");
        addMouseListener(this);
    }
    public void paint(Graphics g)
    {               
        super.paint(g);
        bst.displayDataArray(g, this.getWidth(), this.getHeight());
        
        bst.addGraphicsLabVersion(g, this.getWidth(), this.getHeight());
        setTitle("Binary Search Tree display -- LAB Version");
        
        //< Uncomment following lines after completing code for HW version > 
        // Also comment the previous pair of lines corresponding to the lab version.  
        
        // bst.addGraphicsHWVersion(g, this.getWidth(), this.getHeight());
        // setTitle("Binary Search Tree display -- HOME WORK version");
    }
    public void mouseClicked(MouseEvent arg0) {
        String JSON_str = JOptionPane.showInputDialog(null, 
                                "Enter JSON string : ",
                                "Enter JSON string", 1);
        bst.bulkInsert(JSON_str);
        repaint();
    }
    public static void main(String[] args)
    {
        java.awt.EventQueue.invokeLater(new Runnable()
        {
            public void run()
            {
                new BSTClient().setVisible(true);
            }
        });    
    }
    
    // Other mouse listener event handlers blank methods
    public void mouseEntered(MouseEvent arg0) {    }
    public void mouseExited(MouseEvent arg0) { }
    public void mousePressed(MouseEvent arg0) { }
    public void mouseReleased(MouseEvent arg0) { }   
}

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab07.html