1

我创建了 Raw BinaryTree。在这棵树中，插入不像 BST，它像这样::

  1. 如果树为空，则添加值并使其成为根。（假设 30）
  2. 如果树不为空，则输入父值（30）并将新值（20）添加到其左子树。
  3. 如果左子树不为空，则将值（20）插入右子树。
  4. 对于下一次插入，再次取父亲值来确定要在哪里添加值。＆ 很快..

它工作正常，除非我尝试删除一个有两个孩子的节点。我用来删除的方法是deleteWithCopy。

正如我的导师所说，deletewithcopy 是： 1. 找到要删除的节点（temp）的父亲。2. 如果 temp（要删除的节点）是 'father' 的右孩子，则找到 temp 的直接后继 3. 如果 temp（要删除的节点）是 'father' 的左孩子，则找到 temp 的直接前任 4. 交换值temp 及其前任/后继 5. 删除 temp（现在是树的叶子）。

现在如何找到继任者和前任者。

Successor = 一个节点的逻辑后继是它在左子树中最右边的子节点

Predecessor = 一个节点的逻辑前驱是它在右子树中最左边的子节点

根据算法我创建了函数，但删除后，当我遍历（或打印）树时，它显示运行时错误，binarytree.exe 中 0x008B5853 处的未处理异常：0xC0000005：访问冲突读取位置 0xFEEEFEEE。这是“0xFEEEFEEE 用于标记 Visual C++ 中释放的内存”的错误。

我一次又一次地试运行了这件事，我试图访问的内存中没有任何越界的东西，我已经修复了每一个松散的结局，但仍然:(

这是功能：

void BinaryTree<mytype>::deletewithTwoChild(BTNode<mytype> *temp)
{
    BTNode<mytype> *father = findfather(temp, root);    //found address of father of temp node & stored it in pointer
    BTNode<mytype> *leaf = temp;    //created a copy of temp node

    /////CASE 1 (for predecessor)
if(temp==root || father->left==temp)    //if temp is left child of its father then
{
    leaf = leaf->left;  //move leaf 1 time left
    while(leaf->right!=0 )  //until leaf reaches the right most node of left subtree
    {
        leaf = leaf->right; //move leaf 1 time to right
    }
    //swapping values
    mytype var = leaf->key_value;   //created a template variable to store leaf's key
    leaf->key_value = temp->key_value;  //assigning temp's key to leaf
    temp->key_value = var;  //assigning leaf's key to temp
    if(leaf->right!=0)  //if leaf has right child then call deletewithOneChild function
    {
        deletewithOneChild(leaf);   //call to respective function
    }
    else if(leaf->left==0 && leaf->right==0) //if leaf has no children then
    {
        deleteWithNoChild(leaf);    //call to respective function
    }
}
/////CASE 2 (for successor)
else if(father->right==temp)    //if temp is right child of its father, then
{
    leaf = leaf->right; //move leaf 1 time right
    while(leaf->left!=0)    //until leaf reaches the last node of tree which has no child
    {
        leaf = leaf->left;  //move leaf 1 time to left
    }
    //swapping values
    mytype var = leaf->key_value;   //created a template variable to store leaf's key
    leaf->key_value = temp->key_value;  //assigning temp's key to leaf
    temp->key_value = var;  //assigning leaf's key to temp
    if(leaf->right!=0)  //if leaf has right child then call deletewithOneChild function
    {
        deletewithOneChild(leaf);   //call to respective function
    }
    else if(leaf->left==0 && leaf->right==0) //if leaf has no children then
    {
        deleteWithNoChild(leaf);    //call to respective function
    }
}

}

我正在使用的数据集：

               30
              /  \
             20  80
            /   /  \
          10  40    120
               \     / \ 
              60  100 140
              / \     /  \
            50  70   130 150

当运行时错误弹出时，我试图删除节点 80、60、120、140。请帮助 :(( 我还需要指导如何处理树 iff 30 被删除。

4

1 回答 1

0

据我所知，继任者和前任者的定义是不同的。

Successor ：右子树的最小节点，即右子树的最左节点。 Predecessor：左子树的最大节点，即左子树的最右节点。

回到问题 1。我注意到if-else在案例 1 中交换值后的情况。因为，在案例 1 中，您正在找到子树的最右边的节点，leaf->right始终是null并且leaf->left可能不是null。因此，在交换值后不会调用任何删除函数。这将导致错误的 BST 问题，甚至更糟糕的是，程序崩溃。因此，if-else万一的条件是：

// leaf->right always be null, only need to verify leaf->left.
if (leaf->left != 0)
{
    deleteWithOneNode(leaf);
}
else 
{
    deleteWithNoChild(leaf);
}

问题 2。据我所知，BST中一个节点的删除没有选择前任或后继节点的规则，并且仅在交换整个节点时才使用被删除节点的父（父）节点，而不是仅交换节点的值。因此，我的删除功能将是：

void BinaryTree<myType>::delete(BTNode<myType>* node, BTNode<myType>* parent)
{
    if (node->right) // find successor first
    {
        BTNode* ptrParent = node;
        BTNode* ptr = node->right;
        while (ptr->left)
        {
            ptrParnet = ptr;
            ptr = ptr->left;
        }

        // Since the ptr will be delete, we only assign the value of ptr to the value node
        node->key_value = ptr->key_value;

        if (node == ptrParent)
        {
            ptrParnet->right = ptr->right;
        }
        else
        {
            ptrParent->left = ptr->right;
        }
        delete ptr;            
    }
    else if (node->left) // find predecessor
    {
        BTNode* ptrParent = node;
        BTNode* ptr = node->left;
        while (ptr->right)
        {
            ptrParent = ptr;
            ptr = ptr->right;
        }

        // Since the ptr will be delete, we only assign the value of ptr to the value node
        node->key_value = ptr->key_value;

        if (node == ptrParent)
        {
            ptrParent->left = ptr->left;
        }
        else
        {
            ptrParent->right = ptr->left;
        }
        delete ptr; 
    }
    else
    {
        if (node->key_value > parent->key_value)
        {
            parent->right = NULL;
        }
        else
        {
            parent->left = NULL;
        }
        delete node;
    }
}

通过使用该函数，删除 30 后的树将是

         40
       /    \
     20      80
    /       /   \
   10      60    120
          /  \   /  \
        50   70 100 140
                    /  \
                  130  150
于 2016-11-23T03:16:53.943 回答