2

二分探索木のチュートリアルに取り組んでいます。そして、私はこの機能を見つけましdestroy_tree(node* leaf)た。その動作が心配です。コール スタックがどのように見えるか想像できません。説明してもらえますか?

void btree::destroy_tree(node* leaf)
{
    if (leaf !=NULL)
    {
        destroy_tree(leaf->left);
        destroy_tree(leaf->right);
        delete leaf;
    }
}
4

1 に答える 1

3

再帰関数に関する質問については、単純なツリーを考えたり描いたりして、関数がどのように通過するかを紙にマッピングするだけでも役立つ場合があります。

まず、C++ を使用してからしばらく経ちましたが、この例のために、コードを次のように変更します。

void btree::destroy_tree(node* leaf)
{
    if(leaf !=NULL)
    {
        if (leaf->left != NULL)
            destroy_tree(leaf->left);

        if (leaf->right != NULL)
            destroy_tree(leaf->right);

        delete leaf;
    }
}

スタック上のものが少なくなるように。

この関数のロジックがツリーを介して再帰的にどのように機能するかを考えてみてください。ウィキペディアから引っかかった次のツリーの例を見てください

二分探索木の例 に電話するとしましょうdestroy_tree(root)。関数が最初にdestroy_tree(root)呼び出さdestroy_tree(node->left)れ、次にdestroy_tree(node->right). つまり、左の子は常に、右の子より先に繰り返されます。したがって、上記のツリーで番号を使用するには、ツリーは次の順序でトラバースします8,3,1,6,4,7,10,14,13。これに基づいて、すべての左側の子がトラバースされていることがわかります。まだ横断されていない左側がある間、右側の子は横断されません。

プログラムが実行されると、コール スタックは同じように見えるはずです。呼び出すと、右側のノードに到達する前に、連続するすべての左側のノードでdestroy_tree(left)``destroy_tree()'' が呼び出されます。

于 2013-09-03T14:32:18.247 に答える