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. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    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)
    Attached Images Attached Images  

  2. #2
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    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. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    856
    Quote Originally Posted by std10093 View Post
    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. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    @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. #5
    Registered User
    Join Date
    Oct 2011
    Posts
    856
    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?
    Last edited by Nominal Animal; 10-31-2012 at 11:54 AM.

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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
        }
    }

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,577
    Quote Originally Posted by std10093 View Post
    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. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,577
    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. #10
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Perfect! Thank you
    And thanks goes too nomimal animal and dhm2000 too

  11. #11
    Registered User
    Join Date
    Oct 2011
    Posts
    856
    I really appreciate you trying to understand, instead of just copying code.

    Quote Originally Posted by std10093 View Post
    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. #12
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Less code does the same job.More readable first of all.Shall use it
    Thanks again all

  13. #13
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,577
    Quote Originally Posted by Nominal Animal View Post
    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.
    Last edited by anduril462; 10-31-2012 at 01:31 PM.

  14. #14
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree doesn't print it's elements
    By cr33p in forum C Programming
    Replies: 2
    Last Post: 08-17-2011, 10:27 AM
  2. Print all nodes of the same level from binary tree
    By budala in forum C Programming
    Replies: 3
    Last Post: 09-08-2010, 06:31 AM
  3. how to print a binary tree..
    By transgalactic2 in forum C Programming
    Replies: 6
    Last Post: 11-19-2008, 12:53 PM
  4. print a binary tree!
    By basilis in forum C Programming
    Replies: 1
    Last Post: 08-26-2001, 10:36 AM
  5. print a binary tree!
    By basilis in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 08-26-2001, 07:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21