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

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

Re: BST node delete

Quote:

Node cannot be resolved to a type

Where is the data type/class Node defined?

Re: BST node delete

Hello i have this class

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

Re: BST node delete

Quote:

I dont have the node here declared

The compiler can not find a definition for Node.
Where is it defined?

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?

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

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?