高效删除树数据结构

树的根有没有父母ANS以前没有兄弟姐妹（它可以旁边的兄弟姐妹）。
每个节点都有唯一的父节点。
每个节点都有一个指向它的下一个和上一个兄弟，孩子和父母的指针。

此树数据结构正在填充数百万个节点。当我删除一棵树有大量的节点时，会引发堆栈溢出异常。当节点数量相对较少或建立在发布模式时，数据结构运行良好。

这是一个节点的析构函数：

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; 
      } 
     } 
    }

一个可以实现非递归算法遍历树并删除所有它的节点。

你能否建议一个高效的后序遍历算法来删除一个非二叉树？

来源

2012-02-13 Ghassen Hamrouni

另一种方法（使用额外内存）是通过节点存储对数组或专用链接列表中的所有树节点的引用，并根据该节点而不是树结构进行删除。 – 2012-02-13 18:50:17

您应该保留原始代码，否则问题无法理解。您现在公开的代码（未接受我的答案），**不会引发任何堆栈溢出，正如您已经测试的那样。 – CapelliC 2012-02-14 11:25:41

不幸的是，原始代码和代码会引发堆栈溢出。但你的代码更清晰... – 2012-02-14 12:50:16

编辑：错过了有关向父节点返回指针的位。这意味着我们不需要维护路径历史来回溯，我们可以取消堆栈。

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; 
}

来源

2012-02-13 22:24:42

我认为这不是'工作：当它回到父母，删除儿子后，它仍然有firstChild设置，但指向释放节点。 – CapelliC 2012-02-14 10:52:57

@chac你是对的，谢谢。固定（我希望;））。 – 2012-02-14 11:00:51

我会尝试一些简单得多，而且让递归析构函数行使职责：

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

来源

2012-02-13 18:38:41 CapelliC

你的算法比我的更简单，但不幸的是它并不能解决我的特殊问题。 – 2012-02-13 18:49:32

我用你的建议更新了我的算法 – 2012-02-13 18:50:01

我提出了这个简化，因为我不确定你以前的，特别是最后一部分的正确性（类似于删除lastChild ...），现在堆栈使用非常有限：只有2个指针* max_tree_deepth。你是否已经验证了堆栈溢出？ – CapelliC 2012-02-13 19:27:34

您可以尝试创建一个静态函数来做删除。我发现在以前的应用程序中，要求大树对象执行任务可能比使用独立功能在树上执行操作要慢很多。静态函数本质上是全局的，所以递归调用确切地知道去哪里。使用递归“方法”需要通过每个对象查找函数，这可能会增加额外的开销，特别是对于像这样缓存不友好的操作。沿着同样的路线，如果违反界面以避免对每个对象执行getNextSibling（）调用并使程序流完全保留在一个全局递归函数中，您可能会获得更好的性能。

这不是递归本身，而是你的指令管道在你通过这棵树运行时不断拖延数据访问。

来源

2012-02-13 19:31:57 phkahler

再次想到，无论何时“删除”，都必须执行析构函数查找。这可以通过将它们全部链接到实际上未被删除的单个列表中来避免。 – phkahler 2012-02-13 19:35:14

考虑一下，你是否真的需要打扰走树和处理每个节点。

我经常发现为特定任务设置一个专用内存池很方便，然后一旦完成就可以一次释放整个池。

来源

2012-02-13 21:35:41 doynax

下面是一个非递归溶液的草图：

初始化一个指向与根指针的节点;
重复
- 如果当前节点有一个儿子，移动到那个儿子;
- 否则，删除当前节点并返回其父节点（如果有的话）;
直到当前节点没有父节点。

来源

2012-02-13 22:15:55

或者，您可以简单地增加堆栈大小。

在Windows和Visual C++中，默认值是微不足道的1 MB - 只是将其增加到10 MB甚至100 MB - 此内存实际上不会是承诺直到（并且除非）您真的需要它， d只是预先保留（请参阅/STACK选项）。你甚至可以选择性地仅对Debug配置进行操作，以解释那里的“更胖”堆栈。

来源

2012-02-15 01:38:11

高效删除树数据结构

回答

相关问题