-
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");
}
}
-
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?
-
It doesn't do anything at all lol, so hard to narrow it down as I'm not sure where it is horribly wrong
-
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.
-
Salem, In a recursive call like the one you mentioned, is it better to used ++depth as opposed to depth++?
-
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.
-
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");
}
}
-
> #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.
-
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
-
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");
}
}
-
I'm so close!! lol.. And I'm done, ya baby
-
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");
}
}
-
Now if you can just clean up the indentation a little, it will be very nice.