C ++二叉树遍历和函数指针参数 [英] C++ Binary Tree Traverse and Function Pointer Parameter

问题描述

我想要做的是按顺序遍历该节点，以便可以按顺序在二叉树中打印该节点.

What I want to do is to traverse the node in order, so that I can print the node in binary tree in order.

   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);
   }

我看到了这段代码，用于顺序遍历二叉树.遍历所有节点，所以我认为我可以使用遍历功能打印所有已访问节点的所有数据.能行吗?我很困惑多态函数参数要传递什么.

I saw this code for inorder traversing a binary tree. Traversing goes all the nodes so I thought I could print all the data of all visited nodes using traversing function. Would it work? I am very confused what to pass for the polymorphic function parameter.

如果我像下面那样构造二叉树并尝试遍历并打印树中的所有数据，我应该将什么传递给上面的inorder_traverse函数?

If I construct binary tree like the following and try to traverse and print all the data in tree, what should I pass to the function inorder_traverse above?

    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);

谢谢，我将不胜感激.

推荐答案

请考虑您在遍历函数中的工作，即将节点值发送到stdout，以及如何在回调函数中完成此操作，而该回调函数需要一个每次调用都访问了节点.这正是访问函数对象可以完成的.一个例子是:

Consider what you're doing in the traversal function, namely sending the node value to stdout, and how that could be done in a callback function instead that takes a visited node with each invocation. That is precisely what could be done by the visit function object. An example of this is:

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

现在，您的有序遍历就变成这样:

Now your inorder traversal simply becomes this:

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回调机制.但我希望您了解它现在是如何工作的.

Note: this is not really a grand design. It looks like the original author is attempting to utilize a C-callback mechanism wrapped in a C++ world. But I hope you understand how it works now.

这篇关于C ++二叉树遍历和函数指针参数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！