Like Tree2Likes
  • 1 Post By Tclausex
  • 1 Post By whiteflags

Need help for explanation of the code.

This is a discussion on Need help for explanation of the code. within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to ...

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    14

    Need help for explanation of the code.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
     
    /* A binary tree node has data, pointer to left child
       and a pointer to right child */
    struct node
    {
         int data;
         struct node* left;
         struct node* right;
    };
     
    /* Helper function that allocates a new node with the
       given data and NULL left and right pointers. */
    struct node* newNode(int data)
    {
         struct node* node = (struct node*)
                                      malloc(sizeof(struct node));
         node->data = data;
         node->left = NULL;
         node->right = NULL;
     
         return(node);
    }
     
    /* Given a binary tree, print its nodes according to the
      "bottom-up" postorder traversal. */
    void printPostorder(struct node* node)
    {
         if (node == NULL)
            return;
     
         // first recur on left subtree
         printPostorder(node->left);
     
         // then recur on right subtree
         printPostorder(node->right);
     
         // now deal with the node
         printf("%d ", node->data);
    }
     
    /* Given a binary tree, print its nodes in inorder*/
    void printInorder(struct node* node)
    {
         if (node == NULL)
              return;
     
         /* first recur on left child */
         printInorder(node->left);
     
         /* then print the data of node */
         printf("%d ", node->data);  
     
         /* now recur on right child */
         printInorder(node->right);
    }
     
    /* Given a binary tree, print its nodes in inorder*/
    void printPreorder(struct node* node)
    {
         if (node == NULL)
              return;
     
         /* first print data of node */
         printf("%d ", node->data);  
     
         /* then recur on left sutree */
         printPreorder(node->left);  
     
         /* now recur on right subtree */
         printPreorder(node->right);
    }    
     
    /* Driver program to test above functions*/
    int main()
    {
         struct node *root  = newNode(1);
         root->left             = newNode(2);
         root->right           = newNode(3);
         root->left->left     = newNode(4);
         root->left->right   = newNode(5); 
     
         printf("\n Preorder traversal of binary tree is \n");
         printPreorder(root);
     
         printf("\n Inorder traversal of binary tree is \n");
         printInorder(root);  
     
         printf("\n Postorder traversal of binary tree is \n");
         printPostorder(root);
     
         getchar();
         return 0;
    }
    The part in which i am stuck in this program is that....say consider in the function printPreorder what happens when when node==NULL.....where does the control flow...all in all if i am able to understand any of the traversal function code be it preorder or any...it could solve my problem.Please help.






  2. #2
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    Control returns to the calling function, namely main(). The called function ends execution at the return statement.

  3. #3
    Registered User
    Join Date
    Dec 2011
    Posts
    14
    I apologize for my previous thread i posted on the link:Need help for explanation of the code. ...this new thread contains the same problem which i wrongly posted.

  4. #4
    Registered User
    Join Date
    Dec 2011
    Posts
    14
    Thank you...but here say i want the preorder traversal....so in the function printPreorder there is a recursion "printPreorder(node->left)" which calls itself....when i took one example of a tree:say- Name:  tree12.gif
Views: 94
Size:  3.5 KB 1 is the root node, 1's left child is 2 and right child is 3, then 2's left child is 4 and right child is 5. First of the all main() called the function printPreorder by passing the pointer to the root. Then as in the function it checked the condition and printed as traversed in preorder...first 1 then 2 then 4 till here i understood but now when it printed 4 after then the statement printPreorder(node->left) will cause the condition node==null to go true...so after then what happens so that the function prints the leftover nodes in the tree of the above example?? Please help.

  5. #5
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    My answer doesn't really change much... I'll just call your function 'pre' for brevity,

    Code:
    pre(1)
      pre(1->left)   // in 1, call pre(2)
        pre(2->left) // in 2, call pre(4)
          return       // node == NULL, return to calling function where node was 2
        pre(2->right) // in 2, call pre(5)
          return      //  node == NULL, return to calling fuction where node was 2
        // pre ends execution where node is 2 and return to calling function where node was 1
      pre(1->right)
    and so into pre(3).
    Rohit88 likes this.

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    after then the statement printPreorder(node->left) will cause the condition node==null to go true...so after then what happens so that the function prints the leftover nodes in the tree of the above example?? Please help.
    That printPreorder will return to main() just like you wrote. But remember, a recursion function uses the function call stack to repeat itself.

    So you made a stack of function calls:
    printPostorder(root); /* from main() - 1 */
    printPostorder(node->left); /* 2 */
    printPostorder(node->left); /* 4 */

    The call in the stack that will eventually print 4 calls again to end that side of the tree, and then you have to start on the right side since it is the next recursive call.
    printPostorder(node->right); /* right of 4 - null */
    printPostorder(node->right); /* right of 2 - node 5 */
    printPostorder(node->right); /* right of 1 - node 3 */

    That done, you start printing values to unwind the entire stack.
    3
    5
    4
    2
    1

    I'm pretty sure that the order is that...

    Anyway, trace the recursion yourself to prove it.
    Rohit88 likes this.

  7. #7
    Registered User
    Join Date
    Dec 2011
    Posts
    14
    thanks a lot to each one of you.....your support were sufficient to get over the problem..thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. a little code explanation
    By orhanli1 in forum C Programming
    Replies: 4
    Last Post: 12-27-2010, 12:44 PM
  2. Code explanation
    By Kong_Han_Dao in forum C Programming
    Replies: 4
    Last Post: 02-22-2010, 11:03 AM
  3. Code explanation
    By terminator in forum C Programming
    Replies: 9
    Last Post: 04-18-2008, 02:37 PM
  4. Code Explanation
    By dmkanz07 in forum C Programming
    Replies: 1
    Last Post: 03-27-2007, 08:24 PM
  5. code explanation
    By chasingxsuns in forum C Programming
    Replies: 2
    Last Post: 02-04-2006, 12:47 AM

Tags for this Thread


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