Okay, I'm finishing up my Binary Search Tree implementation that I'm doing out of boredom. The one thing that I'm having trouble on is a delete algorithm that isn't recursive. Most cases work great. When the deleted node has only one subtree (left or right), deleting a leaf, and for the most part deleting a node with two subtrees works alright. Here is my implementation. If it's too messy, tell me, I'll clean it up and repost it . But I'll hilight the problem area
If my tree/subtree is in the formCode:template <typename T> void BSTree<T>::Delete(T x) { if (root == NULL) { std::cout << "-- Tree is empty --" << std::endl; return; } BinaryTreeNode<T>* prev = root; //points to previous node BinaryTreeNode<T>* next = root; //points ahead size_t dir = 0; //globally stores pointer direction while (true) { if(next == NULL) { std::cout << "-- " << x << " not found --" << std::endl; return; } else if (next->data == x) //if the data has been found and... { //...both children are null if (next->child[0] == NULL && next->child[1] == NULL) { if (next == root) //delete if data is at root root = NULL; else prev->child[dir] = NULL; delete next; } else if (next->child[0] == NULL) //...the left child is null { if (next == root) { root = next->child[1]; //point root to it's only child } else prev->child[dir] = next->child[1]; next->child[1] = NULL; delete next; } else if (next->child[1] == NULL) //...the right child is null { if (next == root) root = next->child[0]; else prev->child[dir] = next->child[0]; next->child[0] = NULL; delete next; } else //...neither child is null { //pointers to right subtree BinaryTreeNode<T>* prevR = next->child[1]; BinaryTreeNode<T>* nextR = prevR; //find the smallest node in right subtree and replace while (true) { if (nextR->child[0] == NULL) { //Connect smallest node's parent //with smallest node's right child //will be null if no right child exists prevR->child[0] = nextR->child[1]; //replace node next->data = nextR->data; //if the rightmost node has no children //set next's right child to NULL if (prevR == nextR && nextR->child[1] == NULL) next->child[1] = NULL; else next->child[1] = nextR->child[1]; //nullify node's children array nextR->child[0] = nextR->child[1] = NULL; delete nextR; break; } else { prevR = nextR; nextR = nextR->child[0]; } } } std::cout << "-- " << x << " has been deleted --" << std::endl; return; } else { prev = next; dir = x < next->data ? 0 : 1; next = next->child[dir]; } } }
------O
-----/-\
----O---O
nd I need to delete the root of that tree, I have a problem with the getting the root of that tree to have their right child nulled. What I'm basically saying is that is there a more "modular" way to implement this without being recursive, and without confusing myself by trying to find clever ways to make use of as few pointers as possible.
Edit: Okay new and improved BST deletion, if there's anything missing which I can't tell at the moment please advise me on some ways to improve it.