StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PORemoving a node with two children in a Binary Tree
text
Body
copied!<p>So this is the code that I have so far. I think I've got the logic down for the most part but I'm stuck on the part with two children.. I've figured out what sort of algorithm I have to use to make it work (I've annotated with comments at the bottom of the function), I'm just not sure how to start... Can anyone point me in the right direction??</p> <p>Heres what I have so far:</p> <pre><code>void BinaryTree::remove(int data){ // Is the data valid? if(data < 0){ cerr << data << " is not valid. Must be a positive integer value." << endl; } else{ // Find the node BinNode* loc = root; BinNode* parent = nullptr; bool found = false; while(!found && loc != nullptr){ if(data > loc->data){ parent = loc; loc = loc->right; } else if(data < loc->data){ parent = loc; loc = loc->left; } else found = true; } // If there is a parent, take care of the pointer if(parent != nullptr){ if(loc->data < parent->data) parent->left = nullptr; else if(loc->data > parent->data) parent->right = nullptr; } // If there are children, save pointers to them BinNode* leftChild = nullptr; BinNode* rightChild = nullptr; if(loc->left != nullptr) leftChild = loc->left; if(loc->right != nullptr) rightChild = loc->right; // So now pointers to the children have been saved (if they exist) and // parent pointers have been taken care of (if they exist) the node can be deleted // If no children exist simply just delete the node and return delete loc; // If one child exists if(leftChild != nullptr || rightChild != nullptr){ if(leftChild != nullptr){ if(leftChild->data < parent->data) parent->left = leftChild; else if(leftChild->data > parent->data) parent->right = leftChild; } else if(rightChild != nullptr){ if(rightChild->data < parent->data) parent->left = rightChild; else if(rightChild->data > parent->data) parent->right = rightChild; } } // Both children exist...this sucks. else if(leftChild != nullptr && rightChild != nullptr){ // Find a minimum in the right subtree BinNode * min = root; BinNode * minParent = nullptr; while(min->left != nullptr){ minParent = min; min = min->left; } // Replace value of the node to be removed with the found minimum loc = new BinNode(min->data); // Delete the remaining duplicate node if(minParent != nullptr) minParent->left = nullptr; delete min; } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload