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

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

2 голосов
/ 20 августа 2010

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

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.

Ответы [ 4 ]

4 голосов
/ 20 августа 2010

У меня только что было это как вопрос для интервью.

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

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

Удивительно, но решение - 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].В качестве альтернативы просто добавьте еще один указатель на объект узла для хранения списка удаления и используйте его, чтобы превратить дерево в список.

1 голос
/ 20 августа 2010

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

Кстати, если вам интересно, есть решение для обхода длинных (и глубоких) деревьев без выделения большого количества памяти .

0 голосов
/ 20 августа 2010

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

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

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)
}
0 голосов
/ 20 августа 2010

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

Переписывание кода другим способом не исправит это; Вы должны просто исследовать и исправить ошибку.

...