c++ - 从二叉树中删除一个二叉树节点

Question

我有一个 BinarySearchTree，它由节点组成，这些节点都是 dataType student 的模板类，其中 student 是一个具有名称和年级私有(private)变量的类。

目前我可以打印树，在树中查找姓名和/或成绩，但我无法从树中删除节点。

我正在尝试删除所有成绩 < 50 的学生(因此失败)。

删除节点后，需要发生以下情况之一:

1. 左 child 为空:用右 child 替换节点。
2. 左 child 不为空:用左边最高的元素替换节点分支机构。

我对此的理解是，如果这是树的话:

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

如果 2 失败，即成绩 < 50

你最终会得到

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