2

私がやりたいことは、ノードを順番にトラバースして、ノードを二分木で順番に出力できるようにすることです。

   void inorder_traverse(node* root, function<void(node*)> visit)
   {
          if (root == nullptr) return;

          cout << root->data << ", ";
          inorder_traverse(root->left, visit);
          visit(root);
          inorder_traverse(root->right, visit);
   }

二分木を順番にたどるこのコードを見ました。トラバースはすべてのノードを通過するため、トラバース機能を使用して、訪問したすべてのノードのすべてのデータを出力できると考えました。それはうまくいくでしょうか？ポリモーフィック関数のパラメーターに何を渡すか非常に混乱しています。

次のようなバイナリ ツリーを構築し、ツリー内のすべてのデータをトラバースして出力しようとすると、上記の関数 inorder_traverse に何を渡す必要がありますか?

    struct node* root = new node(NULL);
    root->data = 10;
    root = insertion(root, 1);
    root = insertion(root, 11);
    root = insertion(root, 2);
    root = insertion(root, 12);
    root = insertion(root, 3);
    root = insertion(root, 13);
    root = insertion(root, 5);
    root = insertion(root, 20);
    root = insertion(root, 7);
    root = insertion(root, 15);

ありがとう、私はそれを大いに感謝します。

4

2 に答える 2

3

トラバーサル関数で行っていること、つまりノード値を stdout に送信することと、呼び出しごとに訪問したノードを取得する代わりにコールバック関数でそれを行う方法を検討してください。これはまさに、visit 関数オブジェクトによって実行できることです。これの例は次のとおりです。

void print_node_value(node *p)
{
    std::cout << p->data << ' ';
}

これで、順序どおりのトラバーサルは次のようになります。

void inorder_traverse(node* root, std::function<void(node*)> visit)
{
   if (root == nullptr) 
      return;

   inorder_traverse(root->left, visit);
   visit(root); // <<== calls provided function object
   inorder_traverse(root->right, visit);
}

そして、次のように呼び出されます。

inorder_traverse(root, std::function<void(node*)>(print_node_value));

注: これは実際にはグランド デザインではありません。元の作成者は、C++ の世界にラップされた C コールバック メカニズムを利用しようとしているようです。しかし、それが今どのように機能するかを理解していただければ幸いです。

于 2013-08-24T01:33:13.327 に答える
2

その関数は、「現在の」ノードで行うことを実行するためのものであるため、visit を廃止できます。したがって、呼び出しをデータの印刷に置き換えるだけです。

void inorder_traverse(node* root)
{
    if (root == nullptr) return;

    inorder_traverse(root->left);
    cout << root->data << ", ";
    inorder_traverse(root->right);
}
于 2013-08-24T01:11:56.703 に答える