Thread: 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)

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.

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.

@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?

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 {
        fputc('(', out); //adjustment no.1
        fprintnode(out, p->left);
        fputc(' ', out);
    }

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

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

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?

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.

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

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

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

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