Recursive Binary Tree

Question

The point is to print a binary tree such as:

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

My code is:

#include <stdio.h>
#include <math.h>

#define LENGTH 16

void makeBranches(int left, int right, char a[][LENGTH], int);
void display(char a[][LENGTH], int);

void main(){
  int i, lines;
  double a;

  a = log10(LENGTH*2)/log10(2);
  lines = (int)a; 
  char array[lines][LENGTH];

  makeBranches(0, LENGTH-1, array, 0);
  display(array, lines);
}

void makeBranches(int left, int right, char a[][LENGTH], int line){

  if(left >= right){
    a[line][left] = 'X';
    return;
  } else{
    a[line][(right+left)/2] = 'X';
    makeBranches(left, (right+left)/2, a, line+1);
    makeBranches((right+left)/2+1, right, a, line+1); 
  }
}

void display(char a[][LENGTH], int lines){
  int i, j;

  for(i = 0; i < lines; i++){
    for(j = 0; j < LENGTH; j++){
      if(a[i][j] == 'X')
    printf("%c", a[i][j]);
      else
    printf("-");      
    }
    printf("\n");
  }
}

This works fine for LENGTH values of 4,8,16 but when you get to trying 32,64 etc. it has some stray X's. For example:

The LENGTH 32

---------------X----X-------X---
-------X---------------X--------
---X-------X-------X-------X----
-X---X---X---X---X---X---X---X--
X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

The LENGTH 64

-------------------------------X--------------------------------
---------------X-------------------------------X----------------
-------X---------------X---------------X---------------X--------
---X-------X-------X-------X-------X-------X-------X-------X----
-X---X---X---X---X--XX---X--XX---X---X---X---X---X---X---X---X--
X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

This has got to be a simple fix somewhere but I just cannot see it. Hopefully someone can.

I've ran your program and everything worked fine. I didn't see any stray Xs. — Yamaneko
– Yamaneko, Commented Nov 8, 2012 at 23:34

Brendan Long · Accepted Answer · 2012-11-08 23:39:25Z

3

char array[lines][LENGTH];

This creates an empty array, where every value is whatever is currently in memory (which is sometimes 0, but not guaranteed to be). This means that sometimes, at random, the memory will already contain an "X" byte. You can solve this by initializing the array to be full of 0's (that's the null character, not '0'):

memset(array, 0, LENGTH * lines);

Or:

for(size_t i = 0; i < lines; i++){
    for(size_t j = 0; j < LENGTH; j++){
        a[i][j] = 0;
    }
}

answered Nov 8, 2012 at 23:39

Brendan Long

54.5k21 gold badges154 silver badges194 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

hmakholm left over Monica · Accepted Answer · 2012-11-08 23:40:24Z

2

Your array is a local variable in main, and you never initialize most of its values. Local variables that are not explicitly initialized start out containing "random garbage" -- which is not really "random", but is "garbage" enough that you can't be sure some of the positions do not accidentally contain the value 'X' initially.

Start by looping over the entire array and initializing all positions to something known.

(Nitpicking language lawyers will know that "random garbage" is not the technically correct term for what happens with unitialized locals, but it is close enough to work as a mental model in practical programming).

answered Nov 8, 2012 at 23:40

hmakholm left over Monica

23.4k3 gold badges55 silver badges75 bronze badges

Collectives™ on Stack Overflow

Recursive Binary Tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related