New Topic/Question
Reply
I am currently programming a Binary Search and came across a problem with my deleting a node with one child. I do not know why but every time i delete a node with one child it messes up my results... Please Help!!!!!
Ex: Input File contains: 67, 90, 7, 94, 9, 91, 100, 92, 93
In-Order Traversal (Before Deletion): 7 9 67 90 91 93 94 100 101
Enter the number you want to delete: 7
In-Order Traversal (After Deletion): 67 90 91 93 94 100 101
When I delete the number 7, 9 also dissappears. I was wondering if any one could show me what my error could be in my delete method
public void deleteNumber(int number) {
//Delete the parameter from the tree
if (BinarySearchTree.contains(number, this.root)) {
//If the value exists in the tree
TreeNode t = root; //The eventual parent of the node that must be deleted
TreeNode left = root.getLeft(); //Left child of eventual paret
TreeNode right = root.getRight(); //Right child of eventual parent
TreeNode toBeDeleted = null; //The node that must be deleted
if ((Integer) (t.getValue()) != number) {
//If the root does not contain the value
while (true) {
//Get to the correct parent
if (left != null && number == (Integer) (left.getValue())) {
//Left child is node to be deleted
toBeDeleted = left; //Set it as the one that must be deleted
break; //Correct parent is at t
} //End if
else if (right != null && number == (Integer) (right.getValue())) {
//Right child is node to be deleted
toBeDeleted = right; //Set it as the one that must be deleted
break; //Correct parent is at t
}//End else if
if ((Integer) (t.getValue()) < number) {
//The current values are too small
t = t.getRight(); //Move to bigger values
} //End if
else {
//The current values are too big
t = t.getLeft(); //move to smaller values
} //End else
left = t.getLeft(); //Reset left
right = t.getRight(); //Reset right
} //End while
} //End if
else {
//Root holds the number to be deleted
toBeDeleted = root; //Set root as the one to be deleted
} //End else
int numChildren = BinarySearchTree.getNumChildren(toBeDeleted); //Get the number of children of the node to be deleted
if (toBeDeleted == root) {
//Must delete the root
if (numChildren == 0) {
//Root has no children
root = null; //Nothing left in tree
} //End if
else if (numChildren == 1) {
//Root has 1 child
if (root.getLeft() != null) {
//Left child exists
root = root.getLeft(); //Grandparent takes parent's child
} //End if
else {
//Right child exists
root = root.getRight(); //Grandparent takes parent's child
} //End else
} //End else if
else if (numChildren == 2) {
//Root has 2 children
int newRootValue; //The new value for root
TreeNode temp1 = root; //The parent before left and all the way right
TreeNode temp2 = root.getLeft(); //The node at the end
int i = 0; //Checker for if we have gone just left or left and right
while (temp2.getRight() != null) {
//While there are more rights
temp1 = temp2; //Reset parent
temp2 = temp2.getRight(); //Reset node at the end
i++; //Increment i
} //End while
newRootValue = (Integer) (temp2.getValue()); //Get the new root value
if (i != 0) {
//Gone left and right
temp1.setRight(temp2.getLeft()); //Set the node at the end's children to the parent before the node at the end
} //End if
else {
//Gone only left
temp1.setLeft(temp2.getLeft()); //Set the node at the end's children to the parent before the node at the end
} //End else
root.setValue((Integer) (newRootValue)); //Set the new value of the root
} //End else if
} //End if
else {
//Do not delete the root
if (numChildren == 0) {
//Node has no children
if (left == toBeDeleted) {
t.setLeft(null); //Parent loses left child
} //End if
else if (right == toBeDeleted) {
t.setRight(null); //Parent loses right child
} //End else if
} //End if
else if (numChildren == 1) {
//Node has 1 child
if (t.getLeft() != null && (Integer) (t.getLeft().getValue()) == number) {
//Left child exists and has the correct value
t.setLeft(toBeDeleted.getLeft()); //Grandparent inherits children
} //End if
else {
//Right child exists and has the correct value
t.setRight(toBeDeleted.getRight()); //Grandparent inherits children
} //End else
} //End else if
else {
//Node has 2 children
int newNodeValue; //The new value for node
TreeNode temp1 = toBeDeleted; //The parent before left and all the way to the right
TreeNode temp2 = toBeDeleted.getLeft(); //The node at the end
int i = 0; //Checker for if we have gone just left or left and right
while (temp2.getRight() != null) {
//While there are more rights
temp1 = temp2; //Reset parent
temp2 = temp2.getRight(); //Reset node at the end
i++; //Increment i
} //End while
newNodeValue = (Integer) (temp2.getValue()); //Get the new root value
if (i != 0) {
//Gone left and right
temp1.setRight(temp2.getLeft()); //Set the node at the end's children to the parent before the node at the end
} //End if
else {
//Gone just left
temp1.setLeft(temp2.getLeft()); //Set the node at the end's children to the parent before the node at the end
} //End else
toBeDeleted.setValue((Integer) (newNodeValue)); //Set the new value of the node
} //End else
} //End else
} //End if
} //End deleteNumber
MultiQuote
| 