I am currently trying to program a Binary Tree for the first time, and I have hit a bit of a stumbling block and hope that I can get some insight from you guys about to how to continue.
I have most of the functionality in place at the moment (building the tree, inserting and finding nodes), however the part that I am perplexed by is the deletion of nodes from said tree.
I understand the theory behind node deletion, which is as follows (please correct me if I am wrong):
- If the node has no children, delete it outright.
- If the node only has a left or right child, replace the node to be deleted with it's child and delete the child
- If the node has has two children, find the logical successor to the node to be deleted (my understanding of this is, if possible, move right, and then as far left as you can go, thus finding the next largest node to replace the one being removed).
My question is this:
When I find the node that I want to replace my node that is to be deleted with, should I simply be swapping their values? Or, would it make more sense to re-assign the pointer of the parent node to the logical successor and do a bit of clean up thereafter?
Here is a pastebin of my code thus far (yes, I haven't put in my deleteNode(), as soon as I know the right approach, I will):http://pastebin.com/BtsbmEZP
If you guys could help I would much appreciate it, and also, if you have any input as to how I could make my current code more efficient, please tell me.
Thanks for your time.
[Edit]Some typos - 20110517