Take the Following Code Below( 3 Seperate Java Files) and Complete these require

Question

Take the Following Code Below( 3 Seperate Java Files) and Complete these requirements.

Requirements:

1. Add a delete method to BST.java

2. Add a node numbering that keeps track of the subtree size. (You will need to go back and update the delete method.)

3. Add the k time test. Have k be a variable which is initially 3.

4. Add methods to find the min and max values in the tree.

Code:

File Name: BinarySearchTrees.java

===================================================================

public class BinarySearchTrees
{
  
   static BST m_objBST = new BST();
  
   public static void main(String[] args)
   {
      
   //Enter Function Name to launch the code
      
   }
  
}

===================================================================

File Name: BST.java

===================================================================

public class BST
{
   // This is the root node, which starts off as null
   //   when the BST is empty.
   BSTNode m_objRootNode;
  
   // Class constructor.
   public BST()
   {
       // Not really necessary, provided for clarity.
       m_objRootNode = null;
   }

   // Method to see if the tree is empty.
   public boolean IsEmpty()
   {
       // Return a boolean indicating whether the
       //   three is empty or not.
       return( m_objRootNode == null );
   }

   /* Functions to search for an element */
    public BSTNode Search( int nKeyValue )
    {
        return( Search( m_objRootNode, nKeyValue ) );
    }
  
    // Method to search for an element recursively.
    private BSTNode Search( BSTNode objNode, int nKeyValue )
    {
      
       if( objNode == null )
       {
           return( null );
       }
      
       // First, we get the key value for this node.
       int nThisKeyValue = objNode.GetKeyValue();
          
       // See if the passed in key value is less. If so,
       //   this indicates that we need to go left.
       if( nKeyValue < nThisKeyValue )
       {
           // Get the left node object reference so we
           //   can walk down it.
           objNode = objNode.GetLeftNode();
       }
          
       // See if the passed in key value is greater. If so,
       //   this indicates that we need to go right.
       else if( nKeyValue > nThisKeyValue )
       {
           // Get the right node object reference so we
           //   can walk down it.
           objNode = objNode.GetRightNode();
       }

       // Here we have found the node with the key
       //   value that was passed in.
       else
       {
           return( objNode );
       }
          
       // Now call Search recursively.
       return( Search( objNode, nKeyValue ) );
   }
  
    // This method inserts a node based on the key value.
    public void Insert( int nKeyValue )
    {
       // The root node is returned to m_objRootNode from Insert()
       m_objRootNode = Insert( nKeyValue, m_objRootNode );
    }  

    // Class protected (internal) method to insert nodes. This method
    //   will be called recursively.
    protected BSTNode Insert( int nKeyValue, BSTNode objNode )
    {

       // This node is null and simply needs to be allocated.
        if( objNode == null )
        {
           objNode = new BSTNode( nKeyValue );
        }
      
        // Here we need to walk left.
        else if( nKeyValue < objNode.GetKeyValue() )
        {
           // Set the left node of this object by recursively walking left.
           objNode.SetLeftNode( Insert( nKeyValue, objNode.GetLeftNode() ) );
        }
      
        // Here we need to talk right.
        else if( nKeyValue > objNode.GetKeyValue() )
        {
           // Set the right node of this object by recursively walking right.
           objNode.SetRightNode( Insert( nKeyValue, objNode.GetRightNode() ) );
        }
      
        return( objNode );
    }
  
  
  
  
}

===================================================================

File Name: BSTNode.java

===================================================================

public class BSTNode
{
   BSTNode m_objLeftNode, m_objRightNode;
   int m_nKeyValue;
  
   public BSTNode()
   {
       // Explicit set to null may not be necessary,
       //   but provided for clarity.
       m_objLeftNode = m_objRightNode = null;
      
       // Set this node's key value to default of 0.
       m_nKeyValue = 0;
   }

   public BSTNode(int nKeyValue)
   {
       // Explicit set to null may not be necessary,
       //   but provided for clarity.
       m_objLeftNode = m_objRightNode = null;
      
       // Set this node's key value
       m_nKeyValue = nKeyValue;
   }

   // Accessory method to set the left node.
   public void SetLeftNode( BSTNode objLeftNode)
   {
       // Assign the left node object reference.
       m_objLeftNode = objLeftNode;
   }
  
   // Accessory method to set the right node.
   public void SetRightNode( BSTNode objRightNode)
   {
       // Assign the right node object reference.
       m_objRightNode = objRightNode;
   }
  
   // Accessory method to get the left node object.
   public BSTNode GetLeftNode()
   {
       // Return the object.
       return( m_objLeftNode );
   }
  
   // Accessory method to get the right node object.
   public BSTNode GetRightNode()
   {
       // Return the object.
       return( m_objRightNode );
   }

   // Accessory method to set the node's key value.
   public void SetKeyValue( int nKeyValue )
   {
       // Set the value.
       m_nKeyValue = nKeyValue;
   }
  
   // Accessory method to get the node's key value.
   public int GetKeyValue()
   {
       // Return the value.
       return( m_nKeyValue );
   }

  

}

===================================================================

Explanation / Answer

public class BST { BSTNode root = new BSTNode("root"); public void insert(BSTNode root, String title){ if(root.title!=null){ if(title==root.title){ //return already in the catalog } else if(title.compareTo(root.title)0){ if(root.rightChild==null){ root.rightChild = new BSTNode(title); } else{ insert(root.rightChild,title); } } } } public void find(BSTNode root, String title){ if(root!= null){ if(title==root.title){ //return(true); } else if(title.compareTo(root.title)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.