Alright so I have to create a B-tree of order 'n', where the user puts in a desired
'n'. I borrowed and modified code of a B-tree of order 5, but I can't get it to work and it crashes. I also need it to display the contents of the tree in FIFO order. What do I need to change in order to get it to work? Suggestions?
#include <cstdlib>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cstdlib>
#include <iostream>
#include <string>
#include <sys/stat.h>
using namespace std;
/*
*
*/
struct node{
/*
struct node operator=(struct node root) {
if(this == &root){
return *this;
}
}
*/
int numOfKeys;
double* array;
double* value;
int count ;
struct node** child;
};
/*
* Node creator
*/
struct node* create (int keyNum){
int size=2*keyNum;
struct node* ptr=( struct node * ) malloc ( sizeof ( struct node ) );
ptr->value=new double[size];
ptr->child=new struct node* [size];
return ptr;
};
FILE *txtFile;
node *rootNode;
int treeOrder=0;
int MAX=treeOrder*2;
int MIN=(treeOrder*2)/2;
int numOfNodes=0;
struct node * insert ( int, struct node * ) ;
int setval ( int, struct node *, int *, struct node ** ) ;
struct node * search ( int, struct node *, int * ) ;
int searchnode ( int, struct node *, int * ) ;
void fillnode ( int, struct node *, struct node *, int ) ;
void split ( int, struct node *, struct node *, int, int *, struct node ** );
/*
* Method that checks to seee if specified file exists
*/
bool FileExists(string strFilename) {
struct stat fileInfo;
bool blnReturn;
int intStat;
// Attempt to get the file attributes
intStat = stat(strFilename.c_str(),&fileInfo);
if(intStat == 0) {
// We were able to get the file attributes
// so the file obviously exists.
blnReturn = true;
}
else {
cout << "File not found.....\n";
blnReturn = false;
}
return(blnReturn);
}
struct node * insert ( int val, struct node *root )
{
int i ;
struct node *c;
int flag ;
flag = setval ( val, root, &i, &c ) ;
if ( flag )
{
struct node *n =create(treeOrder);
n -> count = 1 ;
n -> value[1] = i ;
n -> child[0] =root ;
n->child[1]=c;
return n ;
}
return root ;
}
/* sets the value in the node */
int setval ( int val, struct node *n, int *p, struct node **c )
{
int k ;
if ( n == NULL )
{
*p = val ;
*c = NULL ;
return 1 ;
}
else
{
if ( searchnode ( val, n, &k ) )
printf ( "\nKey value already exists.\n" ) ;
if ( setval ( val, n -> child [k], p, c ) )
{
if ( n -> count < MAX )
{
fillnode ( *p, *c, n, k ) ;
return 0 ;
}
else
{
split ( *p, *c, n, k, p, c ) ;
return 1 ;
}
}
return 0 ;
}
}
/* searches value in the node */
struct node * search ( int val, struct node *root, int *pos )
{
if ( root == NULL )
return NULL ;
else
{
if ( searchnode ( val, root, pos ) )
return root ;
else
return search ( val, root -> child [*pos], pos ) ;
}
}
/* searches for the node */
int searchnode ( int val, struct node *n, int *pos )
{
if ( val < n -> value [1] )
{
*pos = 0 ;
return 0 ;
}
else
{
*pos = n -> count ;
while ( ( val < n -> value [*pos] ) && *pos > 1 )
( *pos )-- ;
if ( val == n -> value [*pos] )
return 1 ;
else
return 0 ;
}
}
/* adjusts the value of the node */
void fillnode ( int val, struct node *c, struct node *n, int k )
{
int i ;
for ( i = n -> count ; i > k ; i-- )
{
n -> value [i + 1] = n -> value [i] ;
n -> child [i + 1] = n -> child [i] ;
}
n -> value [k + 1] = val ;
n -> child [k + 1] = c ;
n -> count++ ;
}
/* splits the node */
void split ( int val, struct node *c, struct node *n, int k, int *y, struct node **newnode )
{
int i, mid ;
if ( k <= MIN )
mid = MIN ;
else
mid = MIN + 1 ;
*newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
for ( i = mid + 1 ; i <= MAX ; i++ )
{
( *newnode ) -> value [i - mid] = n -> value [i] ;
( *newnode ) -> child [i - mid] = n -> child [i] ;
}
( *newnode ) -> count = MAX - mid ;
n -> count = mid ;
if ( k <= MIN )
fillnode ( val, c, n, k ) ;
else
fillnode ( val, c, *newnode, k - mid ) ;
*y = n -> value [n -> count] ;
( *newnode ) -> child [0] = n -> child [n -> count] ;
n -> count-- ;
}
void numFromFile(char file []){
txtFile=fopen(file, "r");
if(txtFile!=NULL){
int num; //value in which the int is read in and inserted into the B-tree
do{ //while not at the end of the file do:
fscanf(txtFile,"%d", &num);
cout << num << "\n";
rootNode=insert(num, rootNode);
}
while(feof(txtFile)==0);
fclose(txtFile); // reading in words is done. The file is closed.
}
}
void display ( struct node *root )
{
int i ;
if ( root != NULL )
{
for ( i = 0 ; i < root -> count ; i++ )
{
display ( root -> child [i] ) ;
printf ( "%d\t", root -> value [i + 1] ) ;
}
display ( root -> child [i] ) ;
}
}
/*
* Main method......
*/
int main(int argc, char** argv) {
bool fileToInsert=false;
char responseOne [100];
double numToInsert;
cout << "Input the order of the B-tree: ";
cin >> treeOrder;
do{
cout << "Will you be providing a file name for reading the numbers to be inserted from?\n";
cin >> responseOne;
if(stricmp(responseOne, "yes")==0 || stricmp(responseOne, "y")==0){
fileToInsert=true;
}
}
while(stricmp(responseOne, "yes")!=0 && stricmp(responseOne, "no")!=0 && stricmp(responseOne, "y")!=0 && stricmp(responseOne, "n")!=0);
if(fileToInsert==true){
char fileName[50];
cout << "Input the name of the file you wish to use: ";
cin >> fileName;
if(!(FileExists(fileName))){ //checks to see if 'fileName' exists
cout << "The file you have specified does not exist\n";
cout << "Run the program again and insert a valid file name.\n";
return 1;
}
numFromFile(fileName);
display(rootNode);
}
else{
cout << "Then input the number of keys to be generated/inserted into the B-tree: ";
cin >> numToInsert;
}
return 0;
}