3

我最近在通过删除树的根“节点”来销毁树时设法获得堆栈溢出，而节点析构函数与此类似：

Node::~Node(){
    for(int i=0;i<m_childCount;i++)
        delete m_child[i];
}

我想到的一个解决方案是使用自己的堆栈。所以以这种方式删除树：

std::stack< Node* > toDelete;

if(m_root)
    toDelete.push(m_root);

while(toDelete.size()){
    Node *node = toDelete.top();
    toDelete.pop();

    for(int i=0;i<node->GetChildCount();i++)
        toDelete.push(node->Child(i));

    delete node;
}

但是在那里 std::stack::push() 可能会抛出异常。是否可以编写无异常树销毁？如何？

编辑：

如果有人对这里感兴趣，这里是一个受 jpalecek 指出的算法启发的无异常非递归代码：

Node *current = m_root;

while(current){
  if(current->IsLeaf()){
    delete current;
    return;
  }

  Node *leftMostBranch = current;// used to attach right subtrees

  // delete all right childs
  for(size_t i=1; i<current->GetChildCount(); i++){
    while(!leftMostBranch->Child(0)->IsLeaf())
      leftMostBranch = leftMostBranch->Child(0);

    delete leftMostBranch->Child(0);
    leftMostBranch->Child(0) = current->Child(i);
  }

  // delete this node and advance to the left child
  Node *tmp = current;
  current = current->Child(0);
  delete tmp;
}

注意：Node::IsLeaf()相当于Node::GetChildCount()!=0.

4

4 回答 4

4

我只是把这个作为面试问题。

我必须承认这是我必须即时解决的最困难的事情之一。
就我个人而言，我认为这不是一个好问题，因为你可能知道诀窍（如果你读过 Knuth），在这种情况下解决起来变得微不足道，但你仍然可以欺骗面试官，让他/她认为你已经解决了飞。

这可以假设节点将子指针存储在静态结构中来完成。如果节点将子指针存储在动态结构中，那么它将不起作用，因为您需要即时重新塑造树（它可能会起作用，但不能保证）。

令人惊讶的是，解决方案是 O(n)
（从技术上讲，每个节点都被访问了两次，无需重新扫描树）。
该解决方案使用循环（因此堆栈不使用内存）并且不会动态分配内存来保存需要删除的节点。所以效果出奇的好。

class Node
{
    // Value we do not care about.
    int   childCount;
    Node* children[MAX_CHILDREN];
 };

freeTree(Node* root)
{
    if (root == NULL)
    {    return;
    }
    Node* bottomLeft  = findBottomLeft(root);

    while(root != NULL)
    {
        // We want to use a loop not recursion.
        // Thus we need to make the tree into a list.
        // So as we hit a node move all children to the bottom left.
        for(int loop = 1;loop < root->childCount; ++loop)
        {
            bottomLeft->children[0] = root->children[loop];
            bottomLeft->childCount  = std::max(1, bottomLeft->childCount);
            bottomLeft = findBottomLeft(bottomLeft);
        }

        // Now we have a root with a single child
        // Now we can delete the node and move to the next node.
        Node* bad = root;
        root      = root->children[0];
        delete bad;     // Note the delete should no longer destroy the children.
    }
}

Node* findBottomLeft(Node* node)
{
    while((node->childCount > 0) && node->children[0] != NULL))
    {    node = node->children[0];
    }
    return node;
}

只要它们始终是 children[0] 节点（即使它为 NULL），上述方法就可以工作。只要您不必动态分配空间来容纳 children[0]。或者，只需再添加一个指向节点对象的指针来保存删除列表，并使用它来将树变成一个列表。

于 2010-08-20T16:25:07.560 回答
1

这是所有垃圾收集器都在努力解决的问题。但是，您可以做的最好的事情（恕我直言）是为堆栈祈祷足够的内存，您的祈祷将在 99.99999% 的时间里被听到。如果它不发生，只是abort()。

顺便说一句，如果您有兴趣，有一个解决方案可以在不分配太多内存的情况下遍历长（和深）树。

于 2010-08-20T11:47:25.340 回答
0

为什么原始代码会抛出异常？我猜你正在做一些事情，比如在树的多个位置使用相同的节点对象。堆栈溢出很少是由正常的预期情况引起的。堆栈溢出不是问题，它们是问题的征兆。

以不同的方式重写代码并不能解决这个问题。您应该调查并修复错误。

于 2010-08-20T11:33:23.477 回答
0

是否可以编写无异常树销毁？如何？

也许这个（未经测试的代码）：

void destroy(Node* parent)
{
  while (parent)
  {
    //search down to find a leaf node, which has no children
    Node* leaf = parent;

    while (leaf->children.count != 0)
      leaf = leaf->chilren[0];

    //remember the leaf's parent
    parent = leaf->parent;

    //delete the leaf
    if (parent)
    {
      parent->children.remove(leaf);
    }
    delete leaf; 

  } //while (parent)
}
于 2010-08-20T13:10:05.897 回答