Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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() ) );
- }
- //System.out.print(objNode.GetKeyValue()+ "\n");
- return( objNode );
- }
- public boolean delete( int x )
- {
- boolean deleted = delete( x, m_objRootNode );
- System.out.print(deleted);
- return deleted;
- }
- private boolean delete( int x, BSTNode t )
- {
- boolean deleted = false;
- if( t == null )
- return false; // Item not found; do nothing
- //finds node with key, removes node
- if( x > t.GetKeyValue() )
- {
- delete( x, t.GetRightNode() );
- }
- else if( x < t.GetKeyValue() )
- {
- delete( x, t.GetLeftNode() );
- }
- else
- {
- System.out.print("hear\n");
- deleted = t.remove(x, t);
- System.out.print("hear\n");
- return deleted;
- }
- //return false;
- return deleted;
- }
- public BSTNode getRootNode()
- {
- return m_objRootNode;
- }
- public int getSubTreeSize()
- {
- int i = m_objRootNode.getSubtreeSize(m_objRootNode);
- return i;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement