C ++中的非例外树破坏
-
30-09-2019 - |
题
最近,我通过删除其根部“节点”来破坏树时设法获得了堆栈溢出,而节点驱动器与此相似:
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
.
解决方案
这就是所有垃圾收集者所努力的。但是,您能做的最好的事情(恕我直言)就是为堆栈祈祷足够的记忆,您的祈祷将在99.99999%的时间听到。如果不发生,只是 abort()
.
顺便说一句,如果您有兴趣, 解决长(和深)树的解决方案,而无需分配很多记忆.
其他提示
我只是把这个作为面试问题。
我必须承认,这是我即时要解决的最难解决的事情之一。
就我个人而言,我认为这不是一个好问题,因为您可能知道窍门(如果您已经阅读了Knuth),在这种情况下,解决方案变得很琐碎,但是您仍然可以欺骗面试官让他/她认为您已经在其上解决了问题飞。
可以做到,假设节点将儿童指针存储在静态结构中。如果节点将儿童指针存储在动态结构中,那么它将无法工作,因为您需要飞行(可能会起作用,但不能保证)。
令人惊讶的是,解决方案是O(n)
(从技术上讲,每个节点都会完全访问两次,没有树的重新扫描)。
该解决方案使用循环(因此没有用于堆栈的内存使用),并且不会动态分配MEMEROY以容纳需要删除的节点。因此,这是令人惊讶的效率。
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;
}
上面的方法将起作用,只要他们始终是孩子[0]节点(即使是零)。只要您不必动态分配空间来抱着孩子[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)
}