2

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.

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

THanks, I would greatly appreciate it.

Improve this question

2 Answers 2

Reset to default
3

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

And it is invoked as such:

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

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

You can do away with visit as that function is just to perform whatever you're going to do with your "current" node. So you can simply replace the call with printing your data:

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

    inorder_traverse(root->left);
    cout << root->data << ", ";
    inorder_traverse(root->right);
}
Improve this answer

4 Comments

Yeah, my bad, forgot to change those arguments, however with those changed it should work. I just removed visit for him as it seemed for him to be redundant for his purpose
THanks, but I wanted to traverse in order. Let me correct the question
@dfsadxsadqwd213 this should traverse your tree in order assuming the tree is ordered from left to right
@dfsadxsadqwd213 This wil traverse in-order as requested. The "visit" action is simply removed and put directly in the traversal recursive function (in this case, the "visit" action is to simply print the node data value). If that is all you want, this will work (and +1).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.