Earlier I posted the C++ solution to a tree/web traversal programming problem. Here’s the C solution, including a vector-like array for pointers to children, so one doesn’t have to hard code left, right, etc. In this case Max Children is 5 but it can be any number. A sample output is included below
/* recursion.C */
/* Follow-up to _ recursion problem, web prowling question at _ */
/* input:
(M)
| \
(N) (P)
| \ \
(Q) (S) (T)
(3 level b tree, M has two kids, N and P, and N has two kids, Q and S. P has one child – T.)
output:
Q, S, T, N, P, M
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_NAME_N_LEVEL 1000
#define MAX_KIDS 5
/* Structure in which the input data arrives: */
struct node {
char name; struct node *(kids[MAX_KIDS]);
};
/* Structure the result vector (array) is built from: */
struct nameNLevel {
char name; int level;
};
/* Global scope variables for putting struct node + name data, as discovered in recursive part. */
struct nameNLevel* nsNLs[ MAX_NAME_N_LEVEL ];
int nmLvlCount = 0;
/*
* Synopsis: void recur( int level, struct node* n ) {
* args:
* int level
* struct node* n
* returns: void, BUT puts a record into nsNLs[] and increments nmLvlCount.
* The record contins a node name and the level it was found at.
* Apr 5, 2011 Bill Abbott
*/
void recur( int level, struct node* n ) {
/* first make the new record in the list of names and levels */
struct nameNLevel* thisNmNLvl = (struct nameNLevel*) malloc( sizeof( struct nameNLevel)); /* allocate name string & level num struct */
if (0 == thisNmNLvl ) { /* allocation failed! */
printf(“Memory allocation failed at level %d, struct node %s, go ahead and crash!\n”, level, n->name );
}
thisNmNLvl->level = level; /* fill in level, */
if ( n != 0 ) thisNmNLvl->name = n->name; /* 1 char name… */
nsNLs[ nmLvlCount++ ] = thisNmNLvl;
printf(“\n”);
printf(“recur level: %d n: 0x%x name: %c\n”, level, n, n->name );
/*
printf(“(long)*(n > kids) : 0X%x \n”, (long)*(n->kids) );
printf(“(long)(n > kids[0]): 0X%x \n”, (long)(n->kids[0]) );
*/
/* those two should be the same… */
if ( 0 != n->kids ) { /* this pointer should always have an array where it points, but just in case… */
int j;
for (j=0; j<3; j++ ) {
printf(” (n > kids[%d]) = 0x%x “, j, (n->kids[j]) );
if ( n->kids[j] ) { printf(” >name = %c\n”, (n->kids[j])->name ); }
else { printf( “\n” ); }
} /* ha! This was the hardest part… */
}
int i;
/* now look for any child nodes an call recursivly for them… */
for ( i = 0; n->kids[i] != 0; i++ ) {
recur(level+1, n->kids[i]);
} /* for int it… */
} /* recur */
/*
* Synopsis: void passThrough( struct node* n )
* args:
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011 Bill Abbott
*/
void passThrough( struct node* n ) {
int i;
for( i = 0; i< MAX_NAME_N_LEVEL; i++ ) { /* not strictly required…*/
nsNLs[ i ] = 0; // set ’em all to null to start with.
} /* for i… */
int level = 0;
nmLvlCount = 0;
recur( level, n );
int maxLevel = 0;
for (i = 0; i < nmLvlCount; i++ ) {
if ( nsNLs[ i ]->level > maxLevel ) {
maxLevel = nsNLs[ i ]->level;
} /* if…*/
} /* for int i… */
/* printf(“\nlevel %d nmLvlCount %d maxLevel %d \n”, level, nmLvlCount, maxLevel ); */
int lvl;
printf(“\n”);
for ( lvl = maxLevel; lvl >= 0; lvl– ) { // this is serious, collect and print, all done.
for ( i = 0; i < nmLvlCount; i++ ) {
if (nsNLs[i]->level == lvl ) {
printf( “%c, “, nsNLs[i]->name );
}
}
} /* for int i… */
printf(“\n”);
for ( lvl = maxLevel; lvl >= 0; lvl– ) { // this is serious, collect and print, all done.
for ( i = 0; i < nmLvlCount; i++ ) {
if (nsNLs[i]->level == lvl ) {
printf( “%d, “, nsNLs[i]->level );
}
}
} /* for int i… */
printf(“\n”);
} /* passThrough */
/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int argc count of command line arguments
* char* argv[] vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Apr 7, 2011 Bill Abbott
*/
int main( int argc, char* argv[] ) {
/* 3 level b tree:
* M has two kids, N and P, and
* N has two kids, Q and S.
* Q has no kids
* S has no kids
* P has one child – T.
* T has no kids
*/
char nameIt[] =”malloc “;
char theRest[] = ” failed. Out of memory\n”;
struct node* T = malloc( sizeof(struct node));
if ( 0 == T ) { printf(“%s T %s”, nameIt, theRest ); return( 0 ); }
T->name = ‘T’;
T->kids[MAX_KIDS] = (struct node*) malloc(sizeof(struct node*) * MAX_KIDS);
if ( 0 == T->kids ) { printf(“%s T->kids %s”, nameIt, theRest); return( 0 ); }
T->kids[0] = (void*) 0;
T->kids[1] = (void*) 0;
T->kids[2] = (void*) 0;
/*
printf(“\n”);
printf(“(long)(T > kids) = 0X%x \n”, (long)*(T->kids) );
if ( (T->kids[0])) printf(“*(T > kids[0]) = %c\n”, *(T->kids[0]) );
if ( (T->kids[0])) printf(“( (T > kids[0]) >name = 0x%x %c\n”, (T->kids[0])->name, (T->kids[0])->name );
if ( (T->kids[1])) printf(“( (T > kids[1]) >name = 0x%x %c\n”, (T->kids[1])->name, (T->kids[1])->name );
if ( (T->kids[2])) printf(“( (T > kids[2]) = 0x%x\n”, (T->kids[2]) );
*/
struct node* S = malloc( sizeof(struct node));
if ( 0 == S ) { printf(“%s S %s”, nameIt, theRest ); return( 0 ); }
S->name = ‘S’;
S->kids[MAX_KIDS] = malloc( sizeof( struct node*) * MAX_KIDS);
if ( 0 == S->kids ) { printf(“%s S->kids %s”, nameIt, theRest); return( 0 ); }
S->kids[0] = (void*) 0;
S->kids[1] = (void*) 0;
S->kids[2] = (void*) 0;
struct node* Q = malloc( sizeof(struct node));
if ( 0 == Q ) { printf(“%s Q %s”, nameIt, theRest ); return( 0 ); }
Q->name = ‘Q’;
*(Q->kids) = malloc(sizeof(struct node*) * MAX_KIDS);
if ( 0 == Q->kids ) { printf(“%s Q->kids %s”, nameIt, theRest); return( 0 ); }
Q->kids[0] = (void*) 0;
Q->kids[1] = (void*) 0;
Q->kids[2] = (void*) 0;
struct node* P = malloc( sizeof(struct node));
if ( 0 == P ) { printf(“%s P %s”, nameIt, theRest ); return( 0 ); }
P->name = ‘P’;
P->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == P->kids ) { printf(“%s P->kids %s”, nameIt, theRest); return( 0 ); }
P->kids[0] = T;
P->kids[1] = (void*) 0;
P->kids[2] = (void*) 0;
struct node* N = malloc( sizeof(struct node));
if ( 0 == N ) { printf(“%s N %s”, nameIt, theRest ); return( 0 ); }
N->name = ‘N’;
N->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == N->kids ) { printf(“%s N->kids %s”, nameIt, theRest); return( 0 ); }
N->kids[0] = Q;
N->kids[1] = S;
N->kids[2] = (void*) 0;
struct node* M = malloc( sizeof(struct node));
if ( 0 == N ) { printf(“%s N %s”, nameIt, theRest ); return( 0 ); }
M->name = ‘M’;
M->kids[MAX_KIDS] = malloc(sizeof(struct node*) * MAX_KIDS );
if ( 0 == M->kids ) { printf(“%s M->kids %s”, nameIt, theRest); return( 0 ); }
M->kids[0] = N;
M->kids[1] = P;
M->kids[2] = (void*) 0;
/* printf(“\n”);
printf(“(long)(M > kids) = 0X%x \n”, (long)*(M->kids) );
printf(“*(M > kids[0]) = %c\n”, *(M->kids[0]) );
printf(“( (M > kids[0]) >name = 0x%x\n”, (M->kids[0])->name );
printf(“( (M > kids[1]) >name = 0x%x\n”, (M->kids[1])->name );
printf(“( (M > kids[2]) = 0x%x\n”, (M->kids[2]) );
*/
passThrough( M );
return( 1 );
} // main…
Macintosh-6:interview Bill4$ cc recursion.c
Macintosh-6:interview Bill4$ a.out
recur level: 0 n: 0x100260 name: M
(n > kids[0]) = 0x100220 >name = N
(n > kids[1]) = 0x1001e0 >name = P
(n > kids[2]) = 0x0
recur level: 1 n: 0x100220 name: N
(n > kids[0]) = 0x1001a0 >name = Q
(n > kids[1]) = 0x100160 >name = S
(n > kids[2]) = 0x0
recur level: 2 n: 0x1001a0 name: Q
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0
recur level: 2 n: 0x100160 name: S
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0
recur level: 1 n: 0x1001e0 name: P
(n > kids[0]) = 0x100120 >name = T
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0
recur level: 2 n: 0x100120 name: T
(n > kids[0]) = 0x0
(n > kids[1]) = 0x0
(n > kids[2]) = 0x0
Q, S, T, N, P, M,
2, 2, 2, 1, 1, 0,
Macintosh-6:interview Bill4$