2

二分木をたどるさまざまな方法について学んでいます。これについていくつか質問があります。私はそのようなインオーダー・トラバーサルの疑似コードを見てきました (例えば):

 InOrder (a node N)
{
   if N is not empty
   {
     InOrder (N's left child)
     visit N
     InOrder (N's right child)
   }
}

ノードを「訪問する」とはどういう意味ですか? これは単に印刷するという意味ですか？また、アルゴリズムは、すでにアクセスしたノードをどのように追跡しますか? 幅優先トラバーサルで使用されるようなキューを使用しますか?

ありがとうございました

4

5 に答える 5

3

"visit" はそれを使って何かをするという意味です。結局のところ、すべてのノードを処理するだけでなく、すべてのノードで何かをしたいと思うでしょう。

アルゴリズムは、関数の引数で、コールスタックでアクセスされたものを「追跡」します。つまり、「情報はどこにありますか?」と尋ねた場合です。— 情報があります。追加のストレージは必要ありません。これが再帰の優れた点です。

于 2013-10-31T01:51:23.747 に答える
1

ノードにアクセスすることは、何らかのアクションをノードに適用することです。その例としては、ノードを印刷することができます。

ツリー トラバーサル関数のそのような実装の 1 つは、各ノードに対して呼び出される必要があるアクション (関数オブジェクト) を受け入れます。C での例は次のようになります。

typedef void (*node_func)(node_t *);

void in_order (node_t *root, node_func f) {
    if (root) {
        in_order(root->left);
        f(root);              // "visit" the node
        in_order(root->right);
    }
}

そして、おそらく印刷機能を実装します。

void print_node (node_t *node) {
    printf("Node: %s", node->id); // or whatever your node looks like
}

そして、次のように呼び出すことができます。

void print_tree(node_t *root) {
    in_order(root, &print_node);
}
于 2013-10-31T01:51:42.210 に答える
0

訪問すると、それを印刷するか、何らかの方法で使用することについて話しているだけだと思います。順番トラバーサルは幅優先とは異なります。順番トラバーサルの youtube ビデオを見ると、説明しようとするよりも理解が深まると思います。

https://www.youtube.com/watch?v=9870BucMg64 これは、かなり明確な順序の例である簡単なビデオです。

于 2013-10-31T01:51:14.953 に答える