高效删除树形数据结构
我有一个树形数据结构：
此树数据结构正在填充数百万个节点。 当我删除一个具有大量节点的树时，会引发堆栈溢出异常。 当节点数量相对较少或建立在发布模式时，数据结构运行良好。
这是一个节点的析构函数：
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;
}
}
}
可以实现一个非递归算法来遍历树并删除它的所有节点。
你能建议一个有效的后序遍历算法来删除一个非二叉树吗？
编辑：错过了有关向父节点返回指针的位。 这意味着我们不需要维护路径历史来回溯，我们可以取消堆栈。
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;
}
原始答案：
任何你可以递归地做的事情，你可以做一个循环和一个堆栈。 虽然这不需要更少的内存，但优点是可以将该内存放在堆上并避免溢出。
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;
}
}
以下是非递归解决方案的草图：