Results 1 to 6 of 6

Thread: BST node delete

  1. #1
    KA5poker is offline Member
    Join Date
    Dec 2011
    Posts
    16
    Rep Power
    0

    Default BST node delete

    Hello, This is my second problem. i've made a Binary Search Tree. but de delete function dont work. What did i do wrong? the lines
    Node current = root;
    Node parent = root;
    gives the error: Node cannot be resolved to a type


    Java Code:
    import java.awt.Graphics;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    class BiTree
    { private static final int recNodecount = 0;
    BiLink root; // is initial null = empty tree
      int nodeCounter;
    
      void empty()
      { root = null;
      } // end empty
    
      void show( Graphics g)
      { nodeCounter = 0;
        recuShow( root, g, 1);
        nodeCounter = 0; // reset for other use
      } // end show
    
      private void recuShow( BiLink cursor, Graphics g, int line)
      { if (cursor == null) return;
        recuShow( cursor.left, g, line+1);
        g.drawString( cursor.asString(), ++nodeCounter*10, 40+line*10 );
        recuShow( cursor.right, g, line+1);
      } // end recuShow
    
      boolean found( char item)
      { return recuFound( root, item);
      } // end found
    
      private boolean recuFound( BiLink cursor, char item)
      { if (cursor == null) return false;
        if (cursor.contents == item) return true;
        if (item < cursor.contents) return recuFound(cursor.left, item);
        else return recuFound( cursor.right, item);
      } // end recuFound
    
    //////////////////////// DIEPTE///////////
      int depth()
      { return recuDepth( root);
      } // end depth
    
      private int recuDepth( BiLink cursor)
      { if (cursor==null) return 0;
        else return 1+Math.max(recuDepth(cursor.left),recuDepth(cursor.right));
      } // nde recuDepth
    
     /////////////////////////////////////// 
      
    ///////////////////////// de update met de recursiefe methode  v ////////////////// 
      void update (char newChar){ 
    	  root = recUpdate( root, newChar);
    	} // end method update
    
    
      private BiLink recUpdate( BiLink cursor, char newKey){ 
    	  if (cursor == null) 
    		  return new BiLink( newKey, null, null);
    	  if ( newKey < (cursor.contents)) 
    		  cursor.left = recUpdate( cursor.left, newKey); // recursion
    	  else cursor.right = recUpdate( cursor.right, newKey); // recursion
    	  return cursor;
      }
    
    ///////////////////////// de update met de recursiefe methode  ^ //////////////////
    
      
      
    //////////////////////////////////////// NODECOUNT v //////////////////////////////
      int nodecount() {
    	  return recNodecount (root, nodeCounter);
      }
      
      
      
      private  int recNodecount ( BiLink cursor, int x){
          return (root == null || x <=0) ? 0: (1 + recNodecount(cursor.left,x-1) + recNodecount(cursor.right,x-1));
      }
    ////////////////////////////////////////NODECOUNT ^ //////////////////////////////
    
      
      
    //////////////////////////////////////DELETE v////////////////////////////////////
    	  public boolean delete(int key) // delete node with given key
    	  {                           // (assumes non-empty list)
    		  Node current = root;
    		  Node parent = root;
    		  boolean isLeftChild = true;
    	
    	  while(current.iData != key)        // search for node
    	     {
    	     parent = current;
    	     if(key < current.iData)         // go left?
    	        {
    	        isLeftChild = true;
    	        current = current.leftChild;
    	        }
    	     else                            // or go right?
    	        {
    	        isLeftChild = false;
    	        current = current.rightChild;
    	        }
    	     if(current == null)             // end of the line,
    	        return false;                // didn't find it
    	     }  // end while
    	  // found node to delete
    	
    	  // if no children, simply delete it
    	  if(current.leftChild==null &&
    	                               current.rightChild==null)
    	     {
    	     if(current == root)             // if root,
    	        root = null;                 // tree is empty
    	     else if(isLeftChild)
    	        parent.leftChild = null;     // disconnect
    	     else                            // from parent
    	        parent.rightChild = null;
    	     }
    	
    	  // if no right child, replace with left subtree
    	  else if(current.rightChild==null)
    	     if(current == root)
    	        root = current.leftChild;
    	     else if(isLeftChild)
    	        parent.leftChild = current.leftChild;
    	     else
    	        parent.rightChild = current.leftChild;
    	
    	  // if no left child, replace with right subtree
    	  else if(current.leftChild==null)
    	     if(current == root)
    	        root = current.rightChild;
    	     else if(isLeftChild)
    	        parent.leftChild = current.rightChild;
    	     else
    	        parent.rightChild = current.rightChild;
    	
    	  else  // two children, so replace with inorder successor
    	     {
    	     // get successor of node to delete (current)
    	     Node successor = getSuccessor(current);
    	
    	     // connect parent of current to successor instead
    	     if(current == root)
    	        root = successor;
    	     else if(isLeftChild)
    	        parent.leftChild = successor;
    	     else
    	        parent.rightChild = successor;
    	
    	     // connect successor to current's left child
    	     successor.leftChild = current.leftChild;
    	     }  // end else two children
    	  // (successor cannot have a left child)
    	  return true;                                // success
    	  }  // end delete()                         // success
    ///////////////////////////////////////DELETE ^/////////////////////////////////
    
    } // end class BiTree

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,556
    Rep Power
    25

    Default Re: BST node delete

    Node cannot be resolved to a type
    Where is the data type/class Node defined?

  3. #3
    KA5poker is offline Member
    Join Date
    Dec 2011
    Posts
    16
    Rep Power
    0

    Default Re: BST node delete

    Hello i have this class
    Java Code:
    class BiLink
    { BiLink left, right;
      char contents;  // to easy use < > and ==
    
      BiLink (char contents, BiLink left, BiLink right)
      { this.contents = contents; this.left = left; this.right = right;}
    
      String asString()
      { return String.valueOf( this.contents);
      } // end asString
    
      void putString( String s)
      { if (s.length()==0) this.contents = ' ';
        else this.contents = s.charAt(0);
      } // end putString
    
    } // end BiLink
    I dont have the node here declared . is that the fault?
    greetings Kas

    greatings Kas

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,556
    Rep Power
    25

    Default Re: BST node delete

    I dont have the node here declared
    The compiler can not find a definition for Node.
    Where is it defined?

  5. #5
    KA5poker is offline Member
    Join Date
    Dec 2011
    Posts
    16
    Rep Power
    0

    Default Re: BST node delete

    THis is my new class. with the BiLink her above posted. No errors but it dont delete anything. Do you see the problem?

    Java Code:
    import java.awt.Graphics;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    class BiTree
    { private static final int recNodecount = 0;
    BiLink root; // is initial null = empty tree
      int nodeCounter;
    
      void empty()
      { root = null;
      } // end empty
    
      void show( Graphics g)
      { nodeCounter = 0;
        recuShow( root, g, 1);
        nodeCounter = 0; // reset for other use
      } // end show
    
      private void recuShow( BiLink cursor, Graphics g, int line)
      { if (cursor == null) return;
        recuShow( cursor.left, g, line+1);
        g.drawString( cursor.asString(), ++nodeCounter*10, 40+line*10 );
        recuShow( cursor.right, g, line+1);
      } // end recuShow
    
      boolean found( char item)
      { return recuFound( root, item);
      } // end found
    
      private boolean recuFound( BiLink cursor, char item)
      { if (cursor == null) return false;
        if (cursor.contents == item) return true;
        if (item < cursor.contents) return recuFound(cursor.left, item);
        else return recuFound( cursor.right, item);
      } // end recuFound
    
    //////////////////////// DIEPTE///////////
      int depth()
      { return recuDepth( root);
      } // end depth
    
      private int recuDepth( BiLink cursor)
      { if (cursor==null) return 0;
        else return 1+Math.max(recuDepth(cursor.left),recuDepth(cursor.right));
      } // nde recuDepth
    
     /////////////////////////////////////// 
      
    ///////////////////////// de update met de recursiefe methode  v ////////////////// 
      void update (char newChar){ 
    	  root = recUpdate( root, newChar);
    	} // end method update
    
    
      private BiLink recUpdate( BiLink cursor, char newKey){ 
    	  if (cursor == null) 
    		  return new BiLink( newKey, null, null);
    	  if ( newKey < (cursor.contents)) 
    		  cursor.left = recUpdate( cursor.left, newKey); // recursion
    	  else cursor.right = recUpdate( cursor.right, newKey); // recursion
    	  return cursor;
      }
    
    ///////////////////////// de update met de recursiefe methode  ^ //////////////////
    
      
      
    //////////////////////////////////////// NODECOUNT v //////////////////////////////
      int nodecount() {
    	  return recNodecount (root, nodeCounter);
      }
      
      
      
      private  int recNodecount ( BiLink cursor, int x){
          return (root == null || x <=0) ? 0: (1 + recNodecount(cursor.left,x-1) + recNodecount(cursor.right,x-1));
      }
    ////////////////////////////////////////NODECOUNT ^ //////////////////////////////
    
      
      
    //////////////////////////////////////DELETE v////////////////////////////////////
      void delete()
      {
    	root = recuDelete(root, char delete);
      } // end method delete
      
      public BiLink recuDelete(BiLink cursor, int key, char delete) 
    	  {                           
    		  BiLink current = root;
    		  BiLink parent = root;
    		  boolean isLeftChild = true;
    		  BiLink cursorToDelete = null;
    	
    		  while(delete != cursor.contents)        // zoek naar node
    	     {
    	     parent = current;
    	     if(key < cursor.contents)         // linksaf?
    	        {
    	        isLeftChild = true;
    	        current = current.left;
    	        }
    	     else                            // of rechtsaf?
    	        {
    	        isLeftChild = false;
    	        current = current.right;
    	        }
    	     if(current == null)             
    	        return cursorToDelete;                // niet gevonden
    	     }  
    	 
    	
    	  // geen aanhangende nodes. gewoon verwijderen.
    	  if(current.left==null && current.right==null)
    	     {
    	     if(current == root)             // als root
    	        root = null;                 // tree is leeg
    	     else if(isLeftChild)
    	        parent.left = null;     
    	     else                            
    	        parent.right = null;
    	     }
    	
    	  //  indien geen rechter nodes. vervang het met de linker
    	  else if(current.right==null){
    	     if(current == root){
    	        root = current.left;
    	     }
    	     else if(isLeftChild){
    	        parent.left = current.left;
    	     }
    	     else{
    	        parent.right = current.left;
    	     }
    	  }
    	
    	  // indien geen linker nodes, vervang het met de rechter 
    	  else if(current.left==null){
    	     if(current == root){
    	        root = current.right;
    	     }
    	     else if(isLeftChild){
    	        parent.left = current.right;
    	     }
    	     else{
    	        parent.right = current.right;
    	     }
    	  }
    	
    	  else if (cursor.right != null && cursor.left != null){  // 2 aanhangende nodes? 
                 grootsteNode(cursor.left, cursor, cursorToDelete);
                 }
    	return cursorToDelete;
    	  }
              
              
              private BiLink grootsteNode(BiLink cursor, BiLink oldCursor, BiLink cursorToDelete)
              {
                  int temp = 0;
    
                  if(cursor.right != null)  // rechts is altijd groter als links
                  {
                      return grootsteNode(cursor.right, cursor, cursorToDelete); // dus als er een rechter node is.. is dit de grootste node
                  }
                  else if(cursor.left == null)
                  {
                      temp = oldCursor.contents;
                      cursorToDelete.contents = cursor.contents;
    
                      if(temp < cursor.contents)
                          oldCursor.right = null;
                      else if (temp > cursor.contents)
                          oldCursor.left = null;
                      return oldCursor;
                  }
                  else if(cursor.left != null)
                  {
                      temp = oldCursor.contents;
    
                      cursorToDelete.contents = cursor.contents;
    
                      if (temp > cursor.contents)
                          oldCursor.left = cursor.left;
    
                  }
    
                  return cursor;
    
              }
    	                          
    	    // end delete()    
    	                          
    	     
    ///////////////////////////////////////DELETE ^/////////////////////////////////
    
    } // end class BiTree

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,556
    Rep Power
    25

    Default Re: BST node delete

    How do you execute the code for testing? Do you have a testing class with a main() method that uses the code that you have posted and that shows the problem?

Similar Threads

  1. node.x
    By java software in forum Java Software
    Replies: 0
    Last Post: 10-10-2011, 07:20 PM
  2. [DOM] How to insert a new node ?
    By adash in forum XML
    Replies: 0
    Last Post: 09-06-2011, 02:09 PM
  3. Vetex vs Node
    By BeijingDuck in forum New To Java
    Replies: 19
    Last Post: 01-19-2011, 07:29 PM
  4. Replies: 2
    Last Post: 04-20-2009, 08:00 AM
  5. How to disabled a node.
    By smartsubroto in forum New To Java
    Replies: 32
    Last Post: 07-01-2008, 07:30 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •