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（）が例外をスローする場合があります。例外の無料ツリー破壊を書くことは可能ですか？どのように？

編集：

ここに興味がある場合は、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.9999％の時間を聞くでしょう。それが起こらなければ、ただ abort().

ところで、興味があるなら、 多くの記憶を割り当てることなく、長い（そして深い）木を横断する解決策.

Answer 2

私はこれをインタビューの質問として持っていました。

そして、私はこれが私がその場で解決しなければならなかった最も難しいことの一つであることを認めなければなりません。
個人的には、あなたがトリックを知っているかもしれないので、それは良い質問だとは思いません（あなたがクヌースを読んだ場合）その場合、解決するのは些細なことになりますが、あなたはまだインタビュアーをだまして、あなたがそれを解決したと思うようにさせることができます飛ぶ。

これは、ノードが静的構造にチャイルドポインターを保存すると仮定して実行できます。ノードがダイナミック構造に子のポインターを保存する場合、その場で木を再形成する必要があるため、動作しません（機能する可能性がありますが、保証はありません）。

驚くべきことに、解決策はO（n）です
（技術的には、すべてのノードが正確に2回訪問され、ツリーを再び走らせません）。
このソリューションはループを使用し（したがって、スタックのメモリ使用はありません）、削除する必要があるノードを保持するために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つポインターを追加して削除リストを保持し、これを使用してツリーをリストに変えるだけです。

Answer 3

元のコードが例外を投げるのはなぜですか？ツリー内の複数の場所で同じノードオブジェクトを使用するようなことをしていると思います。スタックオーバーフローは、通常の予想される状況によって引き起こされることはめったにありません。スタックオーバーフローは問題ではなく、問題の症状です。

コードを異なる方法で書き換えることはそれを修正しません。エラーを調査して修正するだけです。

Answer 4

例外の無料ツリー破壊を書くことは可能ですか？どのように？

おそらくこれ（テストされていないコード）：

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