albero libero distruzione delle eccezioni in C ++

Question

Ho da poco riuscito a ottenere un overflow dello stack quando distruggere un albero cancellando la sua radice 'Node', mentre il distruttore nodo è simile a questo:

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

Una soluzione che venire in mente era quella di utilizzare proprio stack. Quindi l'eliminazione della struttura in questo modo:

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

Ma c'è nel std :: :: pila push () può generare un'eccezione. E 'possibile scrivere un albero libero distruzione eccezione? Come?

EDIT:

Se qualcuno è interessato qui è un codice non ricorsiva eccezione gratuito ispirato l'algoritmo ha sottolineato da 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() è equivalente a Node::GetChildCount()!=0

Answer 1

Questo è ciò che tutti i netturbini lottano con. Tuttavia, la cosa migliore che puoi fare (IMHO) è quello di pregare per la memoria sufficiente per la pila, e le vostre preghiere sarà ascoltato 99,99999% del tempo. Non dovrebbe accadere, proprio abort().

A proposito, se siete interessati, v'è una soluzione per attraversare lungo (e profonda) alberi senza allocare molta memoria .

Answer 2

Ho appena avuto questo come una questione intervista.

E devo ammettere questa è una delle cose più difficili che ho dovuto risolvere al volo.
Personalmente non credo che sia una buona domanda, come si può sapere il trucco (se avete letto Knuth) nel qual caso diventa banale da risolvere, ma è ancora possibile ingannare l'intervistatore a fare di lui / lei pensa di aver risolto il volare.

Questo può essere fatto ipotizzando che i negozi nodo figlio puntatori in una struttura statica. Se i puntatori negozi nodo figlio in una struttura dinamica, allora non funzionerà, come avete bisogno di ri-modellare l'albero al volo (si può lavorare, ma non v'è alcuna garanzia).

A sorpresa la soluzione è O (n)
(Tecnicamente ogni nodo viene visitato esattamente il doppio, senza ri-scansione dell'albero).
Questa soluzione utilizza un ciclo (quindi non utilizzo della memoria per stack) e non assegnare dinamicamente memeroy ai nodi attesa che devono essere eliminati. Quindi è sorprendentemente efficiente.

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

Il metodo di cui sopra funziona fintanto che la loro è sempre un bambino [0] nodo (anche se è NULL). Finché non c'è bisogno di allocare dinamicamente spazio per contenere i bambini [0]. In alternativa basta aggiungere più un puntatore all'oggetto nodo che contenga l'elenco di eliminazione e utilizzare questo per trasformare l'albero in un elenco.

Answer 3

Perché il codice originale un'eccezione? Sto indovinando che si sta facendo qualcosa di simile con lo stesso oggetto nodo in più punti l'albero. overflow dello stack sono raramente causati da situazioni attesi normali. stack overflow non sono un problema, sono il sintomo di un problema.

Riscrivere il codice in modo diverso, non risolverà questo; si dovrebbe solo studiare e correggere l'errore.

Answer 4

  

E 'possibile scrivere un albero libero distruzione eccezione? Come?

Forse questo (codice non testato):

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