我正在处理AVL树。看来我的删除有时只能正常工作。我建了一棵像这样的树

          f
        /   \
       e     j
      /    /   \
     a    h     s

通过按顺序f e h s j a插入。我知道它在插入和平衡方面工作正常。

当我删除ajhse时,一切正常。如果我删除f,那么它将用f替换h,这是正确的,但是我丢失了js

这是第一个被调用的函数。
    void remove(const ItemType& item)
    {
        if(root == NULL)
            return;
        else
        {
            remove(root, item);
        }
    };

第一个函数调用此函数以递归方式找到正确的节点。
    void remove(Node<ItemType>* & node, const ItemType& item)
    {
        if(item > node->item)
        {
            if (node->rightChild == NULL)
            {
                return; // there is nothing here to remove
            }
            else
            {
                // recurse to next node
                remove(node->rightChild, item);
            }
        }
        else if (item < node->item)
        {
            if (node->leftChild == NULL)
            {
                return; // there is nothing here to remove
            }
            else
            {
                // recurse to next node
                remove(node->leftChild, item);
            }
        }
        else if (node->item == item)
        {
            remove(node);
        }

        if (node != NULL)
            node->updateHeight();
    };

这是最后一个要调用的函数。在此完成删除和交换。
    void remove(Node<ItemType>* & node)
    {
        if (node->rightChild == NULL && node->leftChild == NULL)
        {
            delete node;
            node = NULL;
        }
        else if (node->rightChild == NULL)
        {
            Node<ItemType>* temp = node;
            node = node->leftChild;
            delete temp;
        }
        else
        {
            Node<ItemType>* & temp = node->rightChild;
            while (temp->leftChild != NULL)
                temp = temp->leftChild;

            node->item = temp->item;
            delete temp;
            temp = NULL;
        }

        if(node != NULL)
            node->initializeHeight();
    };

我想知道这是否与线条有关
            Node<ItemType>* & temp = node->rightChild;
            while (temp->leftChild != NULL)
                temp = temp->leftChild;

            node->item = temp->item;
            delete temp;
            temp = NULL;

并且临时指针正在执行我不熟悉的行为,或者如果我的整个实现是错误的。我知道丢失的节点在某个地方,因为我的内存泄漏显示出丢失的两个节点从未删除。

最佳答案



是。 Node<ItemType>* & temp = node->rightChild;tempnode->rightChild的别名。因此,while循环修改node->rightChild,您将失去原来的正确子项的句柄。

拿一个普通的指针,沿着正确的子树向下走,直到到达最小成员的父节点为止。然后获取最小成员的值,将其复制到node->item,并删除父级的左 child 。

关于c++ - 简单的AVL树删除有时仅适用,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/15773705/

10-11 23:02
查看更多