0

バイナリ ノード ポインタのスタックを使用して非再帰的なデストラクタを作成することを考えていました。このコードは実行されますか?

binaryNode* parent = root;
while (!empty())
{
  if (parent->left)
  {
    stack1.push(parent)
    parent = parent->left;
  }
  else if (parent->right)
  {
    stack1.push(parent)
    parent = parent->right;
  } else 
  {
    delete parent;
    parent = stack1.pop();
  }
}

基本的なプログラムが完成していないので、上記のコードはテストされていません。何も悪くないはずだと思います。動作はテストされていませんが、二分探索木をトレースしたところ、問題なく動作しました。さらに、stackoverflow でバイナリ サーチ ツリー トラバーサルを使用したスタック実装を見つけることができませんでした。

4

1 に答える 1

0

私には、そこのコードにかなりの問題があるように見えますが、コードを実装していたときにあなたの意図が何であったかを確認することも困難です (つまり、どの問題が C++ の問題で、どの問題が「デザイン」の問題になるか) -level" 疑似コード)。コードの問題の 1 つは、delete parentが参照するオブジェクトによって占有されているスペースのみを解放するparentことです。そのため、スタックをポップするif (parent->left)と、ブランチを再実行するdeleteことになり、同じオブジェクトを再度実行する可能性があります。そして、あなたはdeleteノードをリーフするように見えるだけです。

私が抱えている最大の問題は、アルゴリズムの設計が明確でないことです。再帰アルゴリズムのスタックベースのバージョンを実行する通常の方法は、再帰バージョンを最初に (少なくとも紙の上で) 実行し、次に再帰を因数分解することです。この場合、以下の への呼び出しとして実装された標準のポストオーダー トラバーサルは、次のようになります。do_actionnode = root

do_action(node)
    if node has left descendant
        do_action(left descendant)
    if node has right descendant
        do_action(right descendant)
    perform action on node

あなたの場合、actionノードを削除します。これで、明示的な再帰なしでこれを実装できます (そして、Non recursive Depth first search algorithmへの回答で示されているように、これは一部のツリー トラバーサルの問題では非常に簡単です)。ただし、この場合になぜそうしたいのかについては議論の余地がありますか? 再帰呼び出しはプログラム独自のスタックを使用しますが、代わりに独自のデータ構造を使用して暗黙的に再帰したい場合。スタックでシミュレートするのではなく、ここでは再帰が実際に排除されるため、利点が白黒であるのは末尾再帰を削除する場合のみです。

再帰を削除するルートをたどると、コードがかなり醜くなる可能性があるようです。オーダートラバーサル。暗黙的に再帰的なコードは、元の明示的に再帰的なコードよりも時間および/または空間でパフォーマンスが低下する可能性があります。それは確かにもっとバグがある可能性があります！

于 2013-04-27T22:41:23.513 に答える