1

私はプログラミングの割り当てに取り組んでおり、二分探索木を実装するための一連の関数を書いています。いくつかの関数が与えられています。再帰は理解できたと思っていたのですが、方向を切り替えるのに夢中になっています。

代入で与えられた関数は次のとおりです。

static void deleteAll(BSTNode<Data>* n) {
  if (0 == n) return;
  deleteAll(n->left);
  deleteAll(n->right);
  delete n;
}

非常に短いツリーを削除するには、

    根
   / \
左利き右利き

私は電話しますdeleteAll(root)。n != 0だから今私は電話しますdeleteAll(lefty)。n != 0だから私は電話しますdeleteAll(lefty->left)。もちろん、左のノードはありません。lefty ノードを追加したとき、コンストラクターは左、右、および親のポインターを 0 に初期化したので、n == 0. したがって、関数から戻り、righty を削除することはありません。どうすれば にたどり着けますdeleteAll(n->right)か?

おっしゃる通り、この機能は提供されているので、変更する必要はありません。一番左または一番右のノードを呼び出すdeleteAll(b.begin())かb.end()、開始する必要があるのではないかと思いましたが、頭の中でそれを通過するたびにn == 0.

理解を助けてください。

4

2 に答える 2

5

実行中の現在の行を指す矢印を想像してください。を呼び出すとdeleteAll(root)、まずrootが 0かどうかを確認します。

--> if (0 == root) return;
    deleteAll(root->left);
    deleteAll(root->right);
    delete root;

を呼び出すためroot != 0、次のように呼び出しますdeleteAll(root->left)。

    if (0 == root) return;
--> deleteAll(root->left); /*
    |-1-> if (0 == lefty) return;
    |-2-> deleteAll(lefty->left);
    |-3-> deleteAll(lefty->right);
    |-4-> delete lefty; */
    deleteAll(root->right);
    delete root;
  }

これで、矢印が関数の先頭に戻り、同じことを に対して開始leftyし、コメントの 1 ～ 4 行を実行します (2 行目で、null ノードが見つかるまで、同じ展開が再び行われます)。ただし、ここで重要なことは、後で再開できるように、関数呼び出しの前の場所を覚えていることです。だからdeleteAll(root->left)行って、それがすることをし、最終的に戻ってきます。その後、元の呼び出しが続行されます。

    if (0 == root) return;
    deleteAll(root->left);
--> deleteAll(root->right);
    delete root;

これで右側のノードも削除されました。これは、再帰のすべてのステップで発生します。return再帰チェーン全体ではなく、現在の関数からのみ戻ることに注意してください。

于 2012-10-04T22:11:19.113 に答える
2

return は、それを呼び出した関数にのみ返されます。その場合deleteAll(lefty)（私が正しいと理解していれば、それまたはdeleteAll(root)）。deleteAll(n->right)リターン後に呼び出されdeleteAll(n->left)ます。deleteAll の事後条件は、n とそのすべての子が削除されることです。

次のツリーがあるとします。

    a
   / \
   b c
  /   \
 d     e

コール グラフは次のようになります。

deleteAll(a)
    deleteAll(a->left)
        deleteAll(a->left->left)
            deleteAll(a->left->left->left)
            deleteAll(a->left->left->right)
        deleteAll(a->left->right)
    deleteAll(a->right)
        deleteAll(a->right->left)
        deleteAll(a->right->right)
            deleteAll(a->right->right->left)
            deleteAll(a->right->right->right)

またはノード名に関して：

deleteAll(a)
    deleteAll(b)
        deleteAll(d)
            deleteAll(NULL)
            deleteAll(NULL)
        deleteAll(NULL)
    deleteAll(c)
        deleteAll(NULL)
        deleteAll(e)
            deleteAll(NULL)
            deleteAll(NULL)
于 2012-10-04T22:02:33.400 に答える