Binary Tree Recursive Function

Question

I need to print out a binary tree that looks like this:

--------x-------
----x-------x---
--x---x---x---x-
-x-x-x-x-x-x-x-x 
xxxxxxxxxxxxxxxx

Using recursion to print the left side of the line and the right side of the line with the exception of the first line. So the function would call a display function with parameters of the left starting point and the right ending point. Then it calls itself twice, on for the left side and one for the right.

    #include <stdio.h>

#define LENGTH 16

void makeBranches(int, int);
void display(int, int);

int main(){

  makeBranches(0, LENGTH-1);
}

void makeBranches(int left, int right){

  if(left >= right){
    return;
  } else{
    display(left, right);
      makeBranches(left, (right+left)/2);
      makeBranches((right+left)/2+1, right);  
  }
}

void display(int left, int right){
  int mid = (left+right)/2;
  int i;

  for(i = left; i <= right; i++){
    if(i == mid)
      printf("X");
    else
      printf("-");
  }

  if(right == LENGTH-1)
    printf("\n");

}

This is currently what my code looks like, although it has changed many times.

I cannot figure out how to get the first call of makeBranches execute and then the second call. Right now it only does the left side calls and looks like this:

-------X--------
---X-----X--X-

score 0 · Answer 1 · answered Nov 08 '12 at 19:19

As you can see already your problem lies within the structure tree of calling the recursive functions. In order to prevent this type of behavior you need to implement a design where the entire tree is scanned before you print anything out.

Your call structure right now works like this:

makeBranches(left,right) -> 
  makeBranches(left, (right+left)/2) ->
    makeBranches(left, ((right+left)/2+left)/2) ->
      makeBranches(left, (((right+left)/2+left)/2+left)/2) -> etc.
  makeBranches((right+left)/2+1,right) ->
    makeBranches((right+(right+left)/2+1)/2+1,right) ->
      makeBranches((right+(right+(right+(right+left)/2+1)/2+1)/2+1)/2+1,right) -> etc.

In order to flatten this out what you should be aiming to do is capture each level before printing. To do this you'll need some form of collection like a Linked List to add to for each side, then once the entire tree is scanned you can reconstruct the drawing.

Within your display function you've already created a check to know if this is a left or right side of the line:

if(right == LENGTH-1)
    printf("\n");

So let's modify the display call.

void display(int left, int right){
  int mid = (left+right)/2;
  int i;
  string thisLine = "";

  for(i = left; i <= right; i++){
    if(i == mid)
      thisLine += "X";
    else
      thisLine += "-";
  }

  if(right == LENGTH-1) {
    rightList.add(thisLine);
  } else {
    leftList.add(thisLine);
  }
}

Now, from your main() after the entire tree is constructed print out every node of each list going left->right->"\n" (repeat until empty).

Some caveats you can watch out for, but could design around are the fact that your very first call to display creates the entire line so if you used my code it'd drop it on the right list meaning you'd have to draw it like right->(left->right->"\n")repeat

Does this make sense? I hope I didn't skip out on anything as I did this all conceptually :\

score 0 · Answer 2 · answered Nov 08 '12 at 20:03

0

You will need to do a breadth-first traversal.

answered Nov 08 '12 at 20:03

aib

45,516
10
73
79

Binary Tree Recursive Function

2 Answers2

Linked