Print by hierarchy a binary tree

This is a discussion on Print by hierarchy a binary tree within the C Programming forums, part of the General Programming Boards category; Consider the tree in the image [ATTACH]Binary tree[/ATTACH] (the image is located at the footer) the hierarchy of this tree ...

1. Print by hierarchy a binary tree

Consider the tree in the image
[ATTACH]Binary tree[/ATTACH]
(the image is located at the footer)

the hierarchy of this tree is
Code:
` (6 (3 (2 5)) (7 ([] 8)))`
where the [] says that this node is null.

Lots of different ideas come to my mind, but i am pretty sure that most of them are overkill. I think i should stick with recursion.

My try

my struct
Code:
```typedef struct tnode *Treeptr;

typedef struct tnode {
int value;
Treeptr left;
Treeptr right;
} Treenode;```
the function
Code:
```/* flag is zero when we came form a left child and 1 when from a
right one.When called,function gets as 2nd parameter 0 */
void nodesprintHier(Treeptr p ,int flag)
{ if( p != NULL ) {
if(!flag)
printf("(%d ", p->value);
else
printf(" %d)", p->value);
nodesprintHier(p->left,0);
nodesprintHier(p->right,1);
}
}```

the output
Code:
```Nodes are HIER :
(6 (3 (2  5) 7) 8)```

2. i want to say your notation is inconsistent which makes it hard to print what you want.
Code:
``` (6
(3
(2 5)
)
(7
([] 8)
)
)```
for example, you want to print the null left pointer for the 7 leaf on the right tree, but not the null left/right for the other leaf nodes. that makes it difficult. also, you want nodes higher in the tree to be surrounded by left/right parents, but not the leaf nodes such as (2 5).

what if was like this instead, where each node is surrounded by parens and you print all the null leaf pointers. this prints the hierarchy you want but every node has the same paren wrapper.
Code:
```(6
(3
(2([])([]))
(5([])([]))
)
(7
([])
(8([])([]))
)
)

the code, which is a classic pre-order traversal

void nodesprintHier(Treeptr p ,int flag)
{
if (p == 0) {
printf("[]");
return;
}

printf("%d", p->value);

printf("(");
nodesprintHier(p->left,0);
printf(")");

printf("(");
nodesprintHier(p->right,1);
printf(")");

return;
}```
then if you want, you could detect that a node was null before descending into it, then not print the ([]). but then you would have to figure out how to print the [] for the left leaf of 7 but not the other ones.

3. Originally Posted by std10093
the hierarchy of this tree is
Code:
` (6 (3 (2 5)) (7 ([] 8)))`
where the [] says that this node is null.
In your recursion loop, first check if both children are NULL. If so, you only print the value of the current node, and return.

If the current node has at least one non-NULL child, you print the value of the current node, a space, and an open parenthesis. For a NULL child, you print just your NULL marker. For a non-NULL child, you do recursion (letting that call handle the printing for that subtree). You also print a space in between the children, and a close parenthesis after the second child. Then you return.

4. @dhm200 i appreciate your proposal,but the requirement is the output to be as i posted

@animal
Code:
```void nodesprintHier(Treeptr p)
{ if( p->right == NULL && p->left == NULL) {
printf("%d", p->value);
return;
}
else {
printf("%d )", p->value);
}
if(p->left != NULL) {
nodesprintHier(p->left);
}

??????
nodesprintHier(p->right,1);
}
}```
I really tried to convert your words into code,but i was not able to do it....Can you please make it clear for me?

5. Since you showed your own efforts first, I shall.
Code:
```void nodesprintHier(Treeptr p)
{
if (p->right == NULL && p->left == NULL) {
printf("%d", p->value);
return;
}

printf("(%d ", p->value);

if (p->left == NULL)
printf("[]");
else
nodesprintHier(p->left);

printf(" ");

if (p->right == NULL)
printf("[]");
else
nodesprintHier(p->right);

printf(")");
}```
The nodesprintHier() function first checks if both leaves are NULL, and if so, it just prints the value of the current node and returns.

When at least one node is non-NULL, it prints an open parens (, the value of the current node, and a space.

If the left node is NULL, the function prints the null marker. Otherwise it uses a recursive call to print the value of the left subtree.

The function then prints the space.

If the right node is NULL, the function prints the null marker. Otherwise it uses a recursive call to print the value of the right subtree.

Finally, the function prints the close parens ), after which it is done.

Onwards:
Code:
```void treeprintHier(Treeptr p)
{
printf("(%d ", p->value);

if (p->left == NULL)
printf("[]");
else
nodesprintHier(p->left);

printf(" ");

if (p->right == NULL)
printf("[]");
else
nodesprintHier(p->right);

printf(")\n");
}```
If you look closely, the treeprintHier() function is almost a perfect duplicate, except it omits the initial check -- therefore always printing both leaves, even if one or both are NULL --, and prints a newline after the final close parens. If the left and/or right are not NULL, it uses nodesprintHier() to print them recursively.

If you use treeprintHier() to print out your trees, you will always get one line of output, in parentheses. If you use nodesprintHier() to print a tree with only the root node, you only get a plain number without any parentheses.
_ _ _ _ _

Now, say you occasionally want to print your trees to a file.

You rewrite the functions to take a stream handle, say into
Code:
```static void fprintnode(FILE *const out, Treeptr p)
{
if (p->right == NULL && p->left == NULL) {
fprintf(out, "%d", p->value);
return;
}

fprintf(out, "(%d ", p->value);

if (p->left == NULL) {
fputs("[] ", out);
} else {
fprintnode(out, p->left);
fputc(' ', out);
}

if (p->right == NULL) {
fputs("[])", out);
} else {
fprintnode(out, p->right);
fputc(')', out);
}
}

void fprinttree(FILE *const out, Treeptr p)
{
fprintf(out, "(%d ", p->value);

if (p->left == NULL) {
fputs("[] ", out);
} else {
fprintnode(out, p->left);
fputc(' ', out);
}

if (p->right == NULL) {
fputs("[])\n", out);
} else {
fprintnode(out, p->right);
fputs(")\n", out);
}
}```
and replace your original functions with wrappers:
Code:
```void treeprintHier(Treeptr p)
{
fprinttree(stdout, p);
}

void nodesprintHier(Treeptr p)
{
fprintnode(stdout, p);
}```
Does my suggestions make more sense now that you see the actual code?

6. That's a great explanation.I mean you don't just show the code,but you explained it good.
Let me make two modifications in order to get the exact output that is required .
Thank you.All is clear to me,
except the static in this function.Sorry for being so curious, but i do not want to use something i do not fully understand
Code:
```static void fprintnode(FILE *const out, Treeptr p)
{
if (p->right == NULL && p->left == NULL) {
fprintf(out, "%d", p->value);
return;
}

fprintf(out, "(%d ", p->value);

if (p->left == NULL) {
fputs("([] ", out);
} else {
fprintnode(out, p->left);
fputc(' ', out);
}

if (p->right == NULL) {
fputs("[])", out);
} else {
fprintnode(out, p->right);
fputc(')', out);
}
}```

7. Originally Posted by std10093
except the static in this function.Sorry for being so curious, but i do not want to use something i do not fully understand
We have a FAQ article for that:
FAQ > static and extern? - Cprogramming.com

8. When i hear static ,the following come to my mind : (remember i am still inexperienced )
• In C for variables that are inside a function and need to maintain their value through functions-calls.My god how difficult was for me when i tried to use this before i was teach'ed about it.I couldn't get the fact that the flow of the code will not assign again the static variable with its initial value.
Code:
` static int var = 0; /* This is what i am talking about */`
And first time i used it ,it was for recursive function , so it was a tough moment for me
• In C++ ,i used to declare functions as static in order not to be created for every object of the class,but every object would have reference to this one static function.Especially when copy constructor was used a lot.
• In java,again for functions ,but i do not remember the exact reason now.Maybe it was that they did not need to be associated with an instance of the class.

I read the link, but still can not understand what is the static keyword in this case provides to me and what will happen if i remove it?

9. The static keyword, when used with file-scope identifiers (i.e. not local variables), is information for the linker. The linker is the part that combines several object files (the result of simply compiling a .c file), and any libraries into the final executable. If you had two .c files, each with a function named fprintnode, and both of those .c files needed to be in your final executable, the linker would get confused. The static keyword tells the linker to only make that function visible to other code in the same .c file. Thus, you can have two fprintnode functions in two different files, and the linker wont get confused, so long as both are static.

EDIT: If you remove it in your code, then probably nothing will happen, because you probably don't have a second function with the same name.

10. Perfect! Thank you
And thanks goes too nomimal animal and dhm2000 too

11. I really appreciate you trying to understand, instead of just copying code.

Originally Posted by std10093
static
Like the FAQ anduril462 pointed out describes, it means the function will only be visible within the current compilation unit (.c file, usually).

Here, I used it to indicate programmer intent: that the function is intended to be used internally by other functions in this same file, rather than being directly called by other code.

I'm also very pleased that you're being sharp. You see, I thought that this subtree
Code:
```  2
╱
1```
was supposed to output 2 1 [], but based on your code, and taking a second look at the example output, it should output 2 (1 []) instead!

Your modifications are correct, but I'd write them a bit differently:
Code:
```static void fprintnode(FILE *const out, Treeptr p)
{
if (p->right == NULL && p->left == NULL) {
fprintf(out, "%d", p->value);
return;
}

fprintf(out, "(%d (", p->value);

if (p->left == NULL) {
fputs("[] ", out);
} else {
fprintnode(out, p->left);
fputc(' ', out);
}

if (p->right == NULL) {
fputs("[]))", out);
} else {
fprintnode(out, p->right);
fputs("))", out);
}
}```
The differences are very minor, though.

The fputs() (to output a string) and fputc() are significantly faster than fprintf() -- but that difference is irrelevant in practice (unless you do a LOT of output), since fprintf() is almost never a bottleneck slowing down the program.

I simply personally prefer to use those when they are more appropriate than fprintf(). You could just as well use fprintf() for all the outputs above, and never see any difference in run time, unless you build up insanely large trees. (I actually wondered whether I should have used fprintf() instead, but decided not to.)

12. Less code does the same job.More readable first of all.Shall use it
Thanks again all

13. Originally Posted by Nominal Animal
The fputs() (to output a string) and fputc() are significantly faster than fprintf() -- but that difference is irrelevant in practice (unless you do a LOT of output), since fprintf() is almost never a bottleneck slowing down the program.

I simply personally prefer to use those when they are more appropriate than fprintf(). You could just as well use fprintf() for all the outputs above, and never see any difference in run time, unless you build up insanely large trees. (I actually wondered whether I should have used fprintf() instead, but decided not to.)
EDIT:
Indeed, you're bypassing all the complicated slow code of converting arguments when printf finds a format specifier, you're probably adding a couple basic if statements over fputs. Furthermore, some compilers (GCC for certain and probably others) will take care of this when they optimize. GCC replaces a fprintf call with fputs if there are no format specifiers in the format string, or with fputc if the format string is exactly one character.

Still, those optimizations can be disabled, so using the fputs/fputc where appropriate is the safest bet.

14. Final version ( can handle the case of trees with depth less or equal to one, the above version can not)
- i wrote a function that calculates depth -
Code:
```int computedepth(Treeptr p)              /* Compute depth of tree p */
{ int n1, n2;
if (p == NULL)                        /* Depth of empty tree is 0 */
return 0;
n1 = computedepth(p->left);         /* Compute depth of left subtree */
n2 = computedepth(p->right);       /* Compute depth of right subtree */
return (n1 > n2) ? n1+1 : n2+1;
/* Return maximun of depths of left and right subtrees plus 1 */
}

int treedepth(Treeptr p)
{
return computedepth(p) - 1;         /* Root node does not count*/
}

void treeprintHier(Treeptr p)
{
if( treedepth(p) <= 1 ) {
nodesprintHier(p);
return;
}
fprinttree(stdout, p);
}```
the other functions remain as before