Recursive printf of binary tree elements

Question

I went back to K & R to read one chapter, and noticed an example that I had previously skipped. This chapter discusses the topic of a binary tree data type. I understand that they store new records in nodes, but the print function confuses me. Why is the left part printed first?

Will this work if printf is the first command in a function and then left and right?

If not, then why?

 /* treeprint: in-order print of tree p */ void treeprint(struct tnode *p) { if (p != NULL) { treeprint(p->left); printf("%4d %s\n", p->count, p->word); treeprint(p->right); } } 

Answer 1

First, lowering the left side, and then type node itself, and then lowering the right side, what does this operation bypass the tree in order. If you moved printf before the left downs, you think this will make it a preliminary workaround. And if you first made both descents, it will be a post-order. All three possibilities visit all nodes, but in three different orders.

Consider a simple tree

  * / \ a + / \ bc 

If you pass this tree in preliminary order, you will receive

 * a + bc 

B-order

 a * b + c 

After ordering,

 abc + * 

Which of these features you need depends on what you do.

Answer 2

Of course, this "worked." You just get a different output order. You can also print the node after printing both child nodes. (And imagine if you had a tree with several children, not just two.)

The real question is whether the values ​​of the tree nodes correspond to any special rules and, therefore, does any specific traversal order make sense. For example, for a binary search tree tree, left-right order returns values ​​in sort order.

Answer 3

You can go through the binary tree in different ways: pre-order, order and order.

printf may be a completely different procedure (computing node data). Some problems require different ways of walking in a tree, for example, if you balance a binary tree, you calculate the balance ratio after visiting both child trees.

Thus, printf can be considered as a place holder for other procedures / functions to solve various problems.