Efficient delete of a tree data structure

I have a tree data structure :

The root of the tree has no parents ans no previous siblings (it can have next siblings).

Every node has a unique parent.

Every node has a pointer to it's next and previous siblings, children and parent.

This tree data structure is being populated with millions of nodes. When I delete a tree having an enormous amount of nodes, a stack-overflow exception is thrown. The data structure works well when the number of nodes is relatively small or when I build in release mode.

This is the destructor of a node :

    Entity::~Entity(void)
    {
        Entity* child = NULL;

        if (firstChild != NULL)
            child = firstChild->getNextSibling();

        while(child != NULL)
        {
            delete child->getPreviousSibling();
            child->setPreviousSibling(NULL);

            child = child->getNextSibling();
        }

        if (lastChild != NULL)
            delete lastChild;

        if (isRoot())
        {
            if (nextSibling != NULL)
            {
                nextSibling->setPreviousSibling(NULL);
                delete nextSibling;
            }
        }
    }

One can implement a non recursive algorithm to traverse the tree and delete all it's nodes.

Could you suggest an efficient postorder traversal algorithm to delete a non binary tree ?

---

EDIT: Missed the bit about back-pointers to the parent node. That means we don't need to maintain a path history to backtrack, and we can do away with the stack.

node = root;
while (node)
{
    if (node->firstChild)
    {
        next = node->firstChild;
        node->firstChild = null;
    }
    else 
    {
        next = node->nextSibling ? node->nextSibling : node->parent;
        delete node;
    }
    node = next;
}

---

Original answer:

Anything you can do recursively, you can do with a loop and a stack. While this doesn't require any less memory, the advantage is that you can put that memory on the heap and avoid an overflow.

s.push(root);
while (!s.empty())
{
     node = s.pop();
     if (node->nextSibling) s.push(node->nextSibling);
     if (node->firstChild) s.push(node->firstChild);
     delete node;
}

---

我会尝试一些更简单的方法，让递归析构函数完成它们的任务：

Entity::~Entity(void)
{
    Entity* child = firstChild;
    while (child) {
      Entity *succ = child->getNextSibling();
      delete child;
      child = succ;
    }
}

---

Here is the sketch of a non-recursive solution:

initialize a pointer to a node with the root pointer;

repeat

if the current node has a son, move to that son;

else, delete the current node and return to its parent, if any;

until the current node has no parent.

链接地址: http://www.djcxy.com/p/30466.html

上一篇: 从Tree（图）获取有序列表的最有效方法是什么？

下一篇: 高效删除树形数据结构