i'm new here and first of all, i wanna apologize if i make errors in question. My problem is: i want to implement a B-tree in C, using a file to store the tree...my program reads 10000 strings of 10 characters each from a Text file, and store that content in a .DAT binary file, organized via B-tree; then the user can search for a string.

I'm using algorithms of "Cormen,et al - Introduction to Algorithms (3ed)", which seems to be correct, clear and functional. BUT, my program just get runtime errors...like Segmentation Fault and Infinite Loop. I've been trying to debug for 5 days, but with no success! The B-tree functions are recursive, which i personally hate...i think exactly the recursion makes the debug so difficult!

My code is relatively big, and it's been divided in 2 files, one source, one header. I'll just post here the functions of B-tree and the variables declarations. But, if someone wants to see full code, i'll post an "iFile.it" link (is it allowed? Sorry if not!)...

Thanks very much for attention and help...sorry for the big question!

Source link [not so important,just main()] : <http://ifile.it/n73drmc/b-tree_file.c>

Header link [all functions are here]: <http://ifile.it/u1fa3kp/b-tree_file.h>

Text File with strings: <http://ifile.it/7hu95ot/arq_5.txt>

NOTES about code: 

i) The free() are with very strange behaviour...so i've commented them, because if i use them, my program bugs even more!

ii) All code comments are my ideas to try to solve the problems, and must be considered that i've tried them.

iii) I'm a native portuguese speaker, so functions and variables could have strange names for native english speakers...sorry for that !

THE CODE:

```
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>

 //defs of pre-compiler

 #ifdef __linux
    #define PAUSA "read p"
    #define CLRSCR "clear"
 #else
    #define PAUSA "Pause"
    #define CLRSCR "cls"
 #endif

 #define T 5 // minimum degree of B-tree
 #define Min (T-1)
 #define Max ((2*T)-1)
 //

 //global vars
 FILE *arqt, *arqb;

 char VAL[11];
 long int lt = 0;

 typedef struct {
    unsigned int num;
    long int pos;
    char chave[(Max+1)][11]; //chave in portuguese = key in english!
    short int folha; //folha in portuguese = leaf in english!
    long int c[(Max+2)];
 } Nod;

 Nod *raiz = NULL; //raiz in portuguese = root in english!
 //

 void b_split(Nod *x, unsigned int i, Nod *y) { //B-TREE-SPLIT-CHILD //that function split a B-tree node
Nod *z = NULL;
unsigned int j=1;

z = (Nod*)realloc(z,sizeof(Nod));

fseek(arqb,0,SEEK_END);
z->pos = ftell(arqb);

z->folha = y->folha;
z->num = Min;

for(j=1;j<=Min;j++) {strcpy(z->chave[j],y->chave[j+T]);}

if (y->folha == 0) {
    for(j=1;j<=T;j++) {z->c[j] = y->c[j+T];}

}

y->num = Min;

for(j=(x->num + 1);j<=(i+1);j--) {x->c[(j+1)] = x->c[j];}

x->c[(i+1)] = z->pos;

for(j=x->num;j<=i;j--) { strcpy(x->chave[j+1],x->chave[j]); }

strcpy(x->chave[i],y->chave[T]);

x->num = x->num + 1;

fseek(arqb,x->pos,SEEK_SET);
fwrite(x,sizeof(Nod),1,arqb);

fseek(arqb,y->pos,SEEK_SET);
fwrite(y,sizeof(Nod),1,arqb);

fseek(arqb,z->pos,SEEK_SET);
fwrite(z,sizeof(Nod),1,arqb);

//free(z);
//free(y);
}

void b_ins(Nod *x, char *val) { //B-TREE-INSERT-NONFULL //insert a key in nonfull node
unsigned int i=0;
Nod *C = NULL;

i = x->num;

if (x->folha == 1) {
    while ( (i >= 1) && (strcmp(val,x->chave[i]) < 0) ) {
        strcpy(x->chave[(i+1)],x->chave[i]);
        i--;
    }
    strcpy(x->chave[(i+1)],val);
    x->num = x->num + 1;

    fseek(arqb,x->pos,SEEK_SET);
    fwrite(x,sizeof(Nod),1,arqb);

}

else {
    while ( (i >= 1) && (strcmp(val,x->chave[i]) < 0) ) {i--;}
    i++;

    C = (Nod*)realloc(C,sizeof(Nod));

    fseek(arqb,x->c[i],SEEK_SET);
    fread(C,sizeof(Nod),1,arqb);

    if (C->num == Max) {
        b_split(x,i,C);

        if ( strcmp(val,x->chave[i]) > 0 ) {i++;}

    }
    fseek(arqb,x->c[i],SEEK_SET);
    fread(C,sizeof(Nod),1,arqb);

    b_ins(C,val);

    //free(C);
}

}

void insere_b(char *val) { //B-TREE-INSERT //i believe the problem is here!
Nod *S = NULL,*R = NULL;

R = (Nod*)realloc(R,sizeof(Nod));
R = raiz;

if (R->num == Max) {
    S = (Nod*)realloc(S,sizeof(Nod));

/*      fseek(arqb,0,SEEK_END);
        S->pos = ftell(arqb);
*/
    raiz = S;

    S->folha = 0;
    S->num = 0;
    S->c[1] = R->pos;

 /*      fseek(arqb,S->pos,SEEK_SET);
         fwrite(S,sizeof(Nod),1,arqb);

 */
    b_split(S,1,R);
    b_ins(S,val);

    //free(S);
}

else {b_ins(R,val);}

//free(R);
}

void busca_b(Nod *x, char *val) { //B-TREE-SEARCH //self explanatory
unsigned int i=1;
Nod *C = NULL;

while( (i <= x->num) && ( strcmp(val, x->chave[i]) > 0 ) ) {i++;}

if ( (i <= x->num) && ( strcmp(val, x->chave[i]) == 0 ) ) {printf ("\nValor encontrado!\n");}

else {
    if (x->folha == 1) {printf ("\nValor NAO encontrado!\n");}

    else {
        C = (Nod*)realloc(C,sizeof(Nod));
        fseek(arqb,x->c[i],SEEK_SET);
        fread(C,sizeof(Nod),1,arqb);

        lt++;

        busca_b(C,val);
        //free(C);
    }

}

}

void cria_b() { // cria arvore B //create the B-tree
long int i = 0;
char V[11];

raiz->folha = 1;
raiz->num = 0;
raiz->pos = 0;
for (i=1;i<=(Max+1);i++) {raiz->c[i] = -1;}

fseek(arqb,raiz->pos,SEEK_SET);
fwrite(raiz,sizeof(Nod),1,arqb);

rewind(arqt);
for (i=0;i<fSize(arqt);i++) {
    fscanf(arqt,"%s\n",V);
    insere_b(V);
}
}

```