Ausnahme frei Baum Zerstörung in C ++

Question

Ich habe vor kurzem bekommt einen Stapelüberlauf verwaltet werden, wenn durch das Löschen seiner Wurzel ‚Knoten‘ einen Baum zu zerstören, während die Knoten destructor dies ähnelt:

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

Eine Lösung, die mir in den Sinn kommen war eigenen Stack zu verwenden. So löschen Sie den Baum so:

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

Aber da die std :: Stack :: push () kann eine Ausnahme auslösen. Ist es möglich, eine Ausnahme frei Baum Zerstörung zu schreiben? Wie?

EDIT:

Wenn jemand interessiert ist, ist hier eine Ausnahme frei nicht-rekursive Code durch den Algorithmus inspiriert wies darauf hin, durch 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;
}

. Hinweis: Node::IsLeaf() entspricht Node::GetChildCount()!=0

Answer 1

Dies ist, was alle Müllsammler kämpfen mit. das Beste, was Sie können jedoch tun (IMHO) ist für genügend Speicher für den Stack und Ihre Gebete werden gehört 99,99999% der Zeit zu beten. Sollte es nicht passieren, nur abort().

BTW, wenn Sie interessiert sind, gibt es eine Lösung lange zu durchqueren (und tief) Bäume ohne viel Zuweisen von Speicher .

Answer 2

ich dies als eine Interview-Frage nur hatte.

Und ich muss zugeben, das ist eines der schwierigsten Dinge, die ich hatte im Fluge zu lösen.
Ich persönlich glaube nicht, dass es eine gute Frage, wie Sie den Trick kennen kann (wenn Sie Knuth gelesen haben), in welchem ??Fall es trivial zu lösen, aber man kann immer noch der Interviewer täuschen zu machen ihn / sie denken, dass Sie gelöst haben es auf die fliegen.

Dies kann unter der Annahme durchgeführt, dass die Knoten speichern Kind Zeiger in einer statischen Struktur. Wenn der Knoten speichert Kind Zeiger in einer dynamischen Struktur dann wird es nicht funktionieren, wie Sie benötigen neu zu gestalten, den Baum auf der Fliege (es funktionieren kann, aber es gibt keine Garantie).

Überraschenderweise ist die Lösung O (n)
(Technisch gesehen ist jeder Knoten besucht genau zweimal ohne erneute Scannen des Baumes).
Diese Lösung verwendet eine Schleife (so zum Stapel ohne Speichernutzung) und nicht dynamisch memeroy zu halten Knoten zuteilen, dass Bedarf gelöscht werden. So ist es überraschend effecient.

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

Die obige Methode funktioniert, solange sie ist immer ein Kind [0] Knoten (auch wenn es NULL ist). Solange Sie müssen nicht dynamisch zuweisen Raum zu halten, Kinder [0]. Alternativ fügen Sie einfach einen weiteren Zeiger auf den Knoten Objekt die Löschliste zu halten und diese den Baum in eine Liste zu machen verwenden.

Answer 3

Warum der ursprüngliche Code ist eine Ausnahme zu werfen? Ich schätze, dass Sie so etwas wie mit dem gleichen Knotenobjekt an mehreren Stellen im Baum tun. Stapelüberläufe werden nur selten von normalen erwarteten Situationen verursacht. Stapelüberläufe sind kein Problem, sie sind das Symptom eines Problems.

Umschreiben des Codes anders wird das nicht beheben; Sie sollten nur untersuchen und die Fehler beheben.

Answer 4

  

Ist es möglich, eine Ausnahme frei Baum Zerstörung zu schreiben? Wie?

Vielleicht ist dies (ungetestet Code):

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