Исключение разрушения свободное дерево в C++

Question

Я недавно удалось получить переполнение стека при уничтожении дерева, удалив его корень «узел», в то время как узел деструктор похож на это:

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() может вызывать исключение. Можно ли написать исключение? Как?

EDIT:

Если кто-то заинтересован здесь исключение бесплатно нерекурсивна код вдохновленный алгоритма указывал 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.

Answer 1

Это то, с чем все бойцы сборщиков мусора. Однако самое лучшее, что вы можете сделать (ИМХО), - это молиться за достаточную память для стека, и ваши молитвы будут услышаны 99.99999% времени. Если этого не произойдет, просто abort().

BTW, если вы заинтересованы, есть solution to traverse long (and deep) trees without allocating much memory.

Answer 2

Почему исходный код генерирует исключение? Я предполагаю, что вы делаете что-то вроде использования одного и того же узла в нескольких местах в дереве. Переполнение стека редко вызвано нормальными ожидаемыми ситуациями. Переполнение стека не является проблемой, они являются симптомом проблемы.

Переписывание кода по-разному не исправит; вы должны просто исследовать ошибку &.

Answer 3

Можно ли написать исключение уничтожения дерева? Как?

Возможно, это (непроверенный код):

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

Answer 4

Я только что это как вопрос интервью.

И я должен признать, что это одна из самых трудных вещей, которые мне пришлось решать на лету.
Лично я не думаю, что это хороший вопрос, поскольку вы можете знать трюк (если вы читали Кнута), и в этом случае это становится тривиально, но вы все равно можете обмануть интервьюера, чтобы заставить его/ее думать, что вы его решили на лету.

Это можно сделать, предполагая, что узел хранит дочерние указатели в статической структуре. Если узел хранит дочерние указатели в динамической структуре, то он не будет работать, так как вам нужно повторно форматировать дерево «на лету» (это может работать, но нет гарантии).

Удивительно, но решение - 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] узел (даже если это значение NULL). Пока вам не нужно динамически выделять пространство для хранения детей [0]. В качестве альтернативы просто добавьте еще один указатель на объект узла, чтобы сохранить список удаления, и используйте это, чтобы превратить дерево в список.