1 Replies - 273 Views - Last Post: 09 October 2012 - 06:34 PM Rate Topic: -----

#1 noobcode  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 03-February 12

Binary Search tree deletion

Posted 09 October 2012 - 03:13 PM

Hello,
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


Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search tree deletion

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Binary Search tree deletion

Posted 09 October 2012 - 06:34 PM

This is horribly complicated for nothing if you want to replace a node with a single child (that is what you posted)
If your method contains() return the node, just assign the son value to that node and you are done
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1