Thread: Recursive Binary Tree

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    126

    Recursive Binary Tree

    Basically I'm trying to create a program that outputs a binary tree in the form of X's. If the X doesn't belong it outputs a -. This is what I got so far. Any help would be greatly appreciative as I'm not that advanced and need to do this asap lol.


    Code:
    #include <stdio.h>
    #include <math.h>
    
    #define element 64
    
    void makeTree(int left, int right, char array[][element], int depth, int terminate);
    void display(char array[][element], int depth);
    
    int main()
    {
    int row=7, left=0, right, depth, terminate, i, j;
    
    
    char array[row][element];
    
        right = pow(2, row);
        depth = 0;
        terminate=row;
        printf("row %d element %d", row, element);
    
        makeTree(left, right, array, depth, terminate);
        display(array, depth);
    
    }
    void makeTree(int left, int right, char array[][element], int depth, int terminate)
    {
    
        if (depth==terminate)
            return;
        else {
            array[depth][(right+left)/2]='x';
            makeTree(left, (right+left)/2, array, depth++, terminate);
            makeTree((right+left)/2+1, right, array, depth++, terminate);
    }
    
    }
    
    void display(char array[][element], int depth){
      int i, j;
    
      for(i = 0; i < depth; i++){
        for(j = 0; j < element; j++){
          if(array[i][j] == 'x')
        printf("%c", array[i][j]);
          else
        printf("-");      
        }
        printf("\n");
      }
      }

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    So what's your question?

    edit: For instance, is there an error or warning you're getting? Specific behaviour that doesn't make sense to you?

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    It doesn't do anything at all lol, so hard to narrow it down as I'm not sure where it is horribly wrong

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    makeTree(left, (right+left)/2, array, depth++, terminate);
    makeTree((right+left)/2+1, right, array, depth++, terminate);
    Perhaps you should try depth+1 instead.

    Step through it in the debugger.
    makeTree(left will have the SAME depth as the parent tree.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User camel-man's Avatar
    Join Date
    Jan 2011
    Location
    Under the moon
    Posts
    693
    Salem, In a recursive call like the one you mentioned, is it better to used ++depth as opposed to depth++?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    makeTree(left, (right+left)/2, array, depth++, terminate);
    makeTree((right+left)/2+1, right, array, depth++, terminate);
    What value(s) of depth get passed to each recursive call?

    makeTree(left, (right+left)/2, array, ++depth, terminate);
    makeTree((right+left)/2+1, right, array, ++depth, terminate);
    Now, what value(s) of depth get passed to each recursive call?

    They're both wrong.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    I'm completely lost as to where to go lol this is what I have now. I tried +1 doesn't make any difference. IDK why I called depth at set to 0 which made second function not work. My output is garbage lol. it has to be in my maketree function I believe. Well output isn't garbage just isn't a tree by any stretch of the imagination

    Code:
    #include <stdio.h>
    #include <math.h>
    
    #define element 128
    
    void makeTree(int left, int right, char array[][element], int depth);
    void display(char array[][element]);
    
    int main()
    {
    int row=7, left=0, right, depth, terminate, i, j;
    
    
    char array[row][element];
    
        right = pow(2, row);
        depth = 0;
        terminate=row;
    
    
        makeTree(left, right, array, depth-1);
        display(array);
    
    }
    void makeTree(int left, int right, char array[][element], int depth)
    {
    
        if (right>=left){
            array[depth][left]='x';
            return;
        }else {
            array[depth][(right+left)/2]='x';
            makeTree(left, (right+left)/2, array, depth+1);
            makeTree((right+left)/2+1, right, array, depth+1);
    }
    
    }
    
    void display(char array[][element]){
      int i, j, d=7;
    
      for(i = 0; i < d; i++){
        for(j = 0; j < element; j++){
          if(array[i][j] == 'x')
        printf("%c", array[i][j]);
          else
        printf("-");      
        }
        printf("\n");
      }
      }
    Last edited by Sorinx; 11-10-2012 at 01:58 AM.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > #define element 128
    Why not try say 4 or 8

    Something you could step through "on paper" without getting completely lost in 7 or 8 recursive calls.

    Having sorted out the base case, the only REALLY interesting case is the first recursive call which results in two base cases. If you get that nailed down, the rest should follow pretty easily.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    I lowered my rows and columns already. Can't figure out how to fix my recursive call at all. My first condition isn't any good in my makeTree function, ahh I put it backwards! 3:56 am editing original code now
    Last edited by Sorinx; 11-10-2012 at 02:56 AM.

  10. #10
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    Code:
    #include <stdio.h>
    
    
    #define element 32
    
    void makeTree(int left, int right, char array[][element], int depth);
    void display(char array[][element]);
    
    int main()
    {
    int row=5, left=0, right, depth, i, j;
    
    
    char array[row][element];
    
        right = element;
        depth = 0;
    
    
    
        makeTree(left, right, array, depth);
        display(array);
    
    }
    void makeTree(int left, int right, char array[][element], int depth)
    {
    
        if (left>=right){
            array[depth][left]='c';
            return;
        }else {
        {
            array[depth][(right+left)/2]='c';
            makeTree(left, (left+right)/2, array, depth+1);
            makeTree((right+left)/2+1, right, array, depth+1);
            
    }
    
    }
    }
    void display(char array[][element]){
      int i, j, d=5;
    
      for(i = 0; i < d; i++){
        for(j = 0; j < element; j++){
          if(array[i][j] == 'c')
        printf("%c", array[i][j]);
          else
        printf("-");      
        }
        printf("\n");
      }
      }
    Last edited by Sorinx; 11-10-2012 at 03:16 AM.

  11. #11
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    I'm so close!! lol.. And I'm done, ya baby

  12. #12
    Registered User
    Join Date
    Oct 2012
    Posts
    126
    Finished Product to help future people having similar issues

    Code:
    #include <stdio.h>
    
    
    #define element 32
    
    void makeTree(int left, int right, char array[][element], int depth);
    void display(char array[][element]);
    
    int main()
    {
    int row=5, left=0, right, depth, i, j;
    
    
    char array[row][element];
    
        right = element;
        depth = 0;
    
    
    
        makeTree(left, right, array, depth);
        display(array);
    
    }
    void makeTree(int left, int right, char array[][element], int depth)
    {
    
        if (left>=right){
            array[depth][left]='c';
            return;
        }else {
        {
            array[depth][(right+left)/2]='c';
            makeTree(left, (right+left)/2, array, depth+1);
            makeTree((right+left)/2+1, right, array, depth+1);
            
    }
    }
    }
    
    void display(char array[][element]){
      int i, j, d=5;
    
      for(i = 0; i < d; i++){
        for(j = 0; j < element; j++){
          if(array[i][j] == 'c')
        printf("%c", array[i][j]);
          else
        printf("-");      
        }
        printf("\n");
      }
      }

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Now if you can just clean up the indentation a little, it will be very nice.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive vs nonrecursive binary tree traversal
    By gaurav9991 in forum C Programming
    Replies: 4
    Last Post: 05-05-2011, 12:28 PM
  2. binary tree but iterative, not recursive!
    By budala in forum C Programming
    Replies: 2
    Last Post: 08-06-2009, 12:55 PM
  3. Recursive Tree Traversal
    By John_L in forum C++ Programming
    Replies: 12
    Last Post: 02-17-2008, 08:34 AM
  4. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  5. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM