la destrucción del árbol libre de excepción en C ++

Question

Me han logrado recientemente para obtener un desbordamiento de pila cuando la destrucción de un árbol mediante la supresión de su raíz 'nodo', mientras que el destructor de nodo es similar a esto:

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

Una solución que ha subido a la mente fue utilizar la propia pila. Por lo tanto eliminando el árbol de esta manera:

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

Pero allí la pila std :: :: push () puede lanzar una excepción. ¿Es posible escribir una destrucción árbol libre excepción? ¿Cómo?

EDIT:

Si alguien está interesado aquí es un código no recursivo libre de excepción inspirado por el algoritmo señalado por 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;
}

Nota:. Node::IsLeaf() es equivalente a Node::GetChildCount()!=0

Answer 1

Esto es lo que todos los recolectores de basura luchan. Sin embargo, lo mejor que puede hacer (en mi humilde opinión) es orar por suficiente memoria para la pila, y sus oraciones se escuchará 99,99999% del tiempo. En caso de que no suceda, simplemente abort().

Por cierto si usted está interesado, hay una solución para atravesar larga (y profundo) árboles sin asignar la cantidad de memoria .

Answer 2

Me acaba de tener esto como una pregunta de la entrevista.

Y debo admitir que esto es una de las cosas más difíciles que tuvo que resolver sobre la marcha.
Personalmente no creo que sea una cuestión bueno como usted puede saber el truco (si has leído Knuth), en cuyo caso se vuelve trivial para resolver pero todavía se puede engañar al entrevistador en la fabricación de él / ella cree que ha resuelto sobre la volar.

Esto se puede hacer asumiendo que las tiendas nodo hijo punteros en una estructura estática. Si los punteros tiendas nodo hijo en una estructura dinámica, entonces no va a funcionar, como sea necesario para volver a dar forma al árbol sobre la marcha (que pueden funcionar, pero no hay garantía).

Sorprendentemente la solución es O (n)
(Técnicamente cada nodo es visitado exactamente el doble sin re-exploración del árbol).
Esta solución utiliza un bucle (por lo que no uso de memoria para la pila), y no asignar dinámicamente memeroy a los nodos de retención que deben suprimirse. Por lo que es sorprendentemente eficiente.

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

El método anterior funcionará siempre que su es siempre un niños [0] nodo (incluso si es NULL). Mientras usted no tiene que asignar dinámicamente espacio para contener los niños [0]. Como alternativa sólo tiene que añadir una más puntero al nodo objeto de mantener la lista de eliminación y usar esto para girar el árbol en una lista.

Answer 3

¿Por qué es el código original lanzar una excepción? Supongo que está haciendo algo parecido con el mismo objeto de nodo en múltiples lugares en el árbol. Los desbordamientos de pila rara vez son causados ??por situaciones normales esperados. Los desbordamientos de pila no son un problema, son el síntoma de un problema.

La reescritura del código diferente que no va a arreglar; sólo debe investigar y corregir el error.

Answer 4

  

¿Es posible escribir una destrucción árbol libre excepción? ¿Cómo?

Tal vez esto (código no probado):

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