-2

所以我有一个带有根节点的队列。每个节点都有一个子节点或兄弟节点。根可以有多个子节点，但只能指向一个子节点。那个孩子可以有孩子，但也会有其他兄弟姐妹。这些兄弟姐妹都是根节点的孩子。最后一个没有兄弟姐妹的孩子，我们称其父节点为兄弟节点，因此称为根。

我遇到的问题是当我想删除父节点时。我必须遍历孩子，直到没有孩子为止。如果我这样做 if(currNode->sibling)，这适用于所有儿童。但如果兄弟姐妹是根，我不应该认为它应该打破 if 语句。因为在执行此循环之前，我确实删除了 root。然后root = nullptr。那么为什么以兄弟为根的孩子仍然指向一个有效的位置而不是 nullptr 呢？万分感谢

4

1 回答 1

1

在纸上画出来。父节点不能是其自己子节点的兄弟节点。因此，您所说的“最后一个没有兄弟姐妹的孩子，我们将父节点称为其兄弟姐妹，因此根”是完全错误的。如果您实际上正在这样做，请停止这样做。最后一个节点后面没有兄弟节点，下面也没有子节点。

删除节点时，循环访问其兄弟节点是错误的。相反，您必须遍历其子代，并且仅更新其直接兄弟姐妹以相互指向，因为在删除完成后它们现在将成为新的兄弟姐妹。

尝试这样的事情：

struct node
{
    node *parent;
    node *children;
    node *previous;
    node *next;
    ...

    node() :
        parent(0), children(0), previous(0), next(0), ...
    {}

    ~node()
    {
        unlink();
        while (children)
            delete children;
    }

    void unlink()
    {
        if (previous)
            previous->next = next;

        if (next)
            next->previous = previous;

        if ((parent) && (parent->children == this))
            parent->children = next;

        parent = next = previous = 0;
    }

    void addChild(node *child)
    {   
        child->unlink();

        child->parent = this;
        if (children)
        {
             node *t = children;
             while (t->next)
                 t = t->next;
             child->previous = t;
             t->next = child;
        }
        else
            children = child;        
    }

    ...
};

class myqueue
{
private;
    node *root;
    ...

public:
    myqueue() :
        root(new node)
    {}

    ~myqueue()
    {
        delete root;
    }

    void addChild(node *parent = 0)
    {
        node n = new node;

        if (!parent)
             parent = root;

        parent->addChild(node);
    }

    void remove(node *n)
    {
        delete n;
    }

    ...
};
于 2017-05-17T07:13:11.267 回答