Remove BinaryTreeNode from BinaryTree

Question

I have a BinarySearchTree , which consists of nodes that are like a template of the studentType student class, where the student is a class with private name and class variables.

At the moment, I can print the tree, find the names and / or ratings in the tree, but I can’t remove the nodes from the tree.

I am trying to remove all students who had a class of 50 (this did not succeed).

After removing node, you must do one of the following:

• Left child is empty: replace node with its right child.
• The left child is not empty: replace node with the highest element on the left branch.

My understanding of this, if it was a tree:

  1 / \ 2 3 / \ /\ 4 5 6 7 

If 2 failed, i.e. fifty

As a result, you get

  1 / \ 4 3 \ / \ 5 6 7 

4 - the highest element in the left branch.

If it was a tree:

  1 / \ 2 3 \ / \ 5 6 7 

and 2 failed

you will have

  1 / \ 5 3 / \ 6 7 

If it was a tree:

  1 / \ 2 3 / \ / \ 4 5 6 7 

and 1 failed to execute

you will have

  5 / \ 2 3 / / \ 4 6 7 

I am having problems creating functions for this, at the moment I have:

 void checkBranch() //called from main - used to pass the root node to checkBranch() { checkBranch(studentTree.getRoot()); } bool checkBranch(BTNode<Student>* currentNode) { if (currentNode != NULL) { if (checkBranch(currentNode -> getLeft())) { deleteNode(currentNode, true); } if (checkBranch(currentNode -> getRight())) { deleteNode(currentNode, false); } return (currentNode -> getData().getGrade() < 50.0); } else { return false; } } 

Now I'm trying to add the deleteNode function, where I just got stuck on what to do / handle what should happen:

 void deleteNode(BTNode<Student> *parentNode, bool left) { BTNode<Student>* nodeToDelete; if (left) { nodeToDelete = parentNode->getLeft(); } } 

Answer 1

I managed to achieve this with this:

 template <typename dataType> void BTree<dataType>::deleteNode(BTNode<dataType> *parentNode, bool left) { BTNode<dataType> *nodeToDelete; BTNode<dataType> *currentNode; if (left) { nodeToDelete = parentNode->getLeft(); } else { nodeToDelete = parentNode->getRight(); } if (nodeToDelete->getLeft() == NULL) { currentNode = nodeToDelete; if (left) { parentNode->setLeft(nodeToDelete->getRight()); } else { parentNode->setRight(nodeToDelete->getRight()); } delete nodeToDelete; } else { BTNode<dataType>* greatestNode = nodeToDelete->getLeft(); if (greatestNode->getRight() == NULL) { nodeToDelete->getLeft()->setRight(nodeToDelete->getRight()); if (left) { parentNode->setLeft(nodeToDelete->getLeft()); } else { parentNode->setRight(nodeToDelete->getLeft()); } } else { while (greatestNode->getRight()->getRight()) { greatestNode = greatestNode->getRight(); } nodeToDelete->setData(greatestNode->getRight()->getData()); BTNode<dataType> *nodeToDelete2 = greatestNode->getRight(); greatestNode->setRight(greatestNode->getRight()->getLeft()); delete nodeToDelete2; } } } 

Answer 2

Firstly, your checkBranch is wrong. What happens if the root node is invalid? It will not be deleted. I suggest a more elegant way to use a callback method that you might like:

 int deleteNodesOnCondition(BTNode<Student>* node, bool(* condition)(BTNode<Student>*)) { int deleteCount = -1; if(condition != NULL) { deleteCount = 0; if(node != NULL) { deleteCount += deleteNodesOnCondition(node->getLeft(), condition); deleteCount += deleteNodesOnCondition(node->getRight(), condition); bool satisfied = condition(node); if(satified) { deleteNode(node); deleteCount += 1; } } } return deleteCount; } bool checkValidGrade(BTNode<Student> *node) { return node != NULL && node->getData().getGrade() >= 50.0; } void checkBranch() { deleteNodesOnCondition(studentTree.getRoot(), checkValidGrade); } 

To test the implementation of delete here , where found == true. Note: this code is not verified.