1

我正在研究 AVL 树。似乎 my remove 仅在某些时候正常工作。我建了一棵看起来像这样的树

          f
        /   \
       e     j
      /    /   \
     a    h     s

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

当我删除a, or j, or h, or s, ore时，一切正常。如果我删除f，那么它会替换f为h，这是正确的，但我会丢失jand s。

这是第一个被调用的函数。

    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;

并且临时指针的行为是我不熟悉的，或者我的整个实现是错误的。我知道丢失的节点在某处，因为我的内存泄漏告诉我丢失的那两个节点永远不会被删除。

4

1 回答 1

2

我想知道它是否与线条有关

是的。Node<ItemType>* & temp = node->rightChild;说temp是 的别名node->rightChild。所以while循环修改node->rightChild了，你失去了原来的右孩子的句柄。

取一个普通的指针，沿着右子树向下走，直到到达它最小成员的父节点。然后获取最小成员的值将其复制到node->item中，并删除父级的左孩子。

于 2013-04-02T20:39:57.467 回答