Chciałem napisać program tworzący drzewo BST dla losowo generowanych liczb niepowtarzających się i potem je przetwarzać.
Napisałem funkcję losującą liczby, tworzącą drzewo i usuwającą.
Pierwsze dwie działają na pewno (przynajmniej tak mi wyszło w testach i analizie ich), usuwająca też wydaje się działać poprawnie.
Jednak jeżeli zwiększam ilość elementów (STEP
w kodzie), to dla 50 program się wysypuje przy wykonywaniu przy każdym uruchomieniu, przy wykonywaniu funkcji insert
dla 25 czasem wysypuje przy insert
, czasem dopiero na erase
, czasem wykona się bez żadnego problemu.
Będę wdzięczny za wszelką pomoc i ewentualne sugestie.
Kod:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const STEP=50;
struct BST{
int value;
struct BST *left,*right;
}*root;
void arrayRandomize(int *array,int arraySize){
int i,tmpArray[arraySize];
for(i=0;i<arraySize;i++){
tmpArray[i]=1;
}
for(i=0;i<arraySize;){
array[i]=rand()%arraySize;
if(tmpArray[array[i]]==1){
tmpArray[array[i]]=0;
i++;
}
}
}
void insert(struct BST *parent,int val){
if(parent==NULL){
parent=malloc(sizeof(struct BST *));
parent->value=val;
parent->left=NULL;
parent->right=NULL;
root=parent;
}
else{
if(val>parent->value){
if(parent->right==NULL){
parent->right=malloc(sizeof(struct BST*));
parent->right->value=val;
parent->right->left=NULL;
parent->right->right=NULL;
}
else{
insert(parent->right,val);
}
}
else{
if(parent->left==NULL){
parent->left=malloc(sizeof(struct BST*));
parent->left->value=val;
parent->left->left=NULL;
parent->left->right=NULL;
}
else{
insert(parent->left,val);
}
}
}
}
void erase(struct BST *parent){
if(parent->right==NULL&&parent->left==NULL) free(parent);
else{
if(parent->right!=NULL) erase(parent->right);
else erase(parent->left);
}
}
int main() {
int i,*array;
srand(time(NULL));
root=NULL;
array=malloc(sizeof(int)*STEP);
arrayRandomize(array,STEP);
for(i=0;i<STEP;i++) printf("%d ",array[i]);
printf("\nIneseruje.\n");
for(i=0;i<STEP;i++)insert(root,array[i]);
printf("Insert udany, usuwam.\n");
erase(root);
printf("Usuwanie udane.\n");
free(array);
system("Pause");
return 0;
}