Удаление BinaryTreeNode из BinaryTree

Question

У меня есть BinarySearchTree, который состоит из узлов, которые являются шаблоном класса dataType student, где student - это класс с личными переменными имени и класса.

В данный момент я могу распечатать дерево, найти имена и / или оценки в дереве, но у меня возникают проблемы при удалении узлов из дерева.

Я пытаюсь удалить всех учеников, у которых был <50 баллов (так не получилось). </p>

После удаления узла необходимо выполнить одно из следующих действий:

1. Левый дочерний элемент пуст: замените узел его правым дочерним элементом.
2. Левый потомок не пуст: замените узел на самый высокий элемент слева ветви.

Насколько я понимаю, если бы это было дерево:

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

Если 2 не пройден, т.е. имел оценку <50 </p>

В итоге вы получите

     1
    /  \
  4     3
   \    / \
    5  6  7

4 - самый высокий элемент в левой ветви.

Если это было дерево:

     1
    /  \
   2     3
   \     / \
    5  6   7

и 2 не удалось

вы бы в итоге получили

     1
    /  \
  5      3
        /  \
       6   7

Если это было дерево:

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

и 1 не удалось

вы бы в итоге получили

     5
    /  \
  2     3
 /      / \
4      6  7

У меня было много проблем при попытке создать функции для этого, на данный момент у меня есть:

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;
}
}

Теперь я пытаюсь добавить функцию deleteNode, где я просто застрял в том, что делать / обрабатывать, что должно произойти:

void deleteNode(BTNode<Student> *parentNode, bool left)
{
BTNode<Student>* nodeToDelete;

if (left)
{
    nodeToDelete = parentNode->getLeft();
}
}

Answer 1

Мне удалось добиться этого с помощью:

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

Во-первых, ваш checkBranch отчасти неправильный.Что произойдет, если корневой узел недействителен?Он не будет удален.Я предлагаю более элегантный способ использования подхода обратного вызова, который может выглядеть следующим образом:

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);
}

Для проверки реализации delete здесь где найдено == trueПримечание: этот код не проверен.