Witam. Mam problem z Binary Search Tree. Otóż kod w większości mam z książki Cormena, jednak usuwanie nie działa poprawnie. Przy usuwaniu całej listy z wyborem losowego elementu usuwa tylko kilka a potem program się crashuje. Zauważyłem jeszcze, że niekiedy przedtem jeszcze usuwa złe elementy. Występuje to tam, gdzie zostaje wyszukany następnik. Nie mam pojęcia jak to naprawić, wielokrotnie porównywałem kod z tym z książki. Na nazwy wskaźników proszę nie zwracać uwagi, szczególnie na prev - nie ma to często związku z jego funkcją.
Oto kod:
#include <iostream>
#include <vector>
#include <fstream>
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <windows.h>
using namespace std;
struct element {
int numer;
string imie;
string nazwisko;
};
struct bst {
element* student;
bst* p;
bst* l;
bst* r;
//------------------------------------dodawanie pojedynczego elementu
void dodaj(bst*& bste, element *student) {
bst *newel = new bst;
newel->student = student;
newel->l=NULL;
newel->r=NULL;
newel->p=NULL;
bst *ths= bste;
bst *prev=NULL;
while (ths!=NULL)
{
prev=ths;
if (ths->student->numer>newel->student->numer) ths=ths->l;
else ths=ths->r;
}
newel->p=prev;
if (prev==NULL)
{
bste=newel;
} else if (prev->student->numer>newel->student->numer)
{
prev->l=newel;
} else prev->r=newel;
}
//----------------------------szukanie, zwraca wskaznik
bst szukaj(bst*b, int numer)
{
if((b==NULL) || (numer==b->student->numer)) return *b;
if (numer < b->student->numer) {
return szukaj(b->l, numer); }
else {
return szukaj(b->r, numer);}
}
bst *min(bst*b)
{
while (b->l!=NULL) b=b->l;
return b;
}
bst *nast(bst*b)
{
if (b->r!=NULL) return min(b->r);
bst *prev = b->p;
while ((prev!=NULL) && (b==prev->r))
{
b=prev;
prev=prev->p;
}
return prev;
}
//-------------------------------------usuwanie pojedynczego elementu
void usun(bst*&bs, int numer)
{
bst *el = NULL;
el = &szukaj(bs,numer);
if (el!=NULL) {
bst *b = NULL;
bst *prev = NULL;
if ((el->l==NULL) || (el->r==NULL)) prev=el;
else prev= nast(el);
if (prev->l != NULL) { b=prev->l; }
else { b=prev->r; }
if (b!=NULL) b->p=prev->p;
if (prev->p==NULL) {
bs = b; }
else {
if (prev->student->numer==prev->p->l->student->numer) {prev->p->l=b;}
else if (prev->student->numer==prev->p->r->student->numer) {prev->p->r = b; }
}
if (prev!=el) el->student->numer=prev->student->numer;
}
}
//------------------- tworzenie calego drzewa z elementow tablicy
void wypelnij(bst*& bste, vector<element> tablica, int inc) {
for (int i=0; i<inc; i++)
{
element *student=new element;
student->imie=tablica[i].imie;
student->nazwisko=tablica[i].nazwisko;
student->numer=tablica[i].numer;
//cout << tablica[i].numer << tablica[i].nazwisko << endl;
bste->dodaj(bste, student);
}
}
};
// ----------------- wczytywanie z pliku do tablicy
void wczytajtab(string load, vector<element> &tablica, int &inc) {
load+=".txt";
ifstream dane(load.c_str()) ;
string ftmp;
while( !dane.eof())
{
element *nowyel = new element;
getline(dane, ftmp, ' ');
nowyel->numer = atoi(ftmp.c_str());
getline(dane, ftmp, ' ');
nowyel->imie = ftmp;
getline(dane, ftmp);
nowyel->nazwisko = ftmp;
tablica.push_back(*nowyel);
inc++;
delete nowyel;
}
dane.close() ;
}
// ----------------------- tworzenie tablicy posortowanych liczb naturalnych
void itab(int max, vector<int> &indeksy) {
for(int j=1;j<=max;j++)
{
indeksy.push_back(j);
}
}
// --------------------------------- MAIN
int main(){
srand(time(NULL));
bst *bste=NULL;
string load;
int inc=0,suma=0;
vector<element> tablica;
vector<int> indeksy;
int wybor;
cin >> load;
wczytajtab(load,tablica,inc);
bste->wypelnij(bste, tablica, inc);
itab(inc,indeksy);
random_shuffle(indeksy.begin(),indeksy.end());
for (int i=0;i<inc;i++)
{
bste->usun(bste, indeksy[i]);
}
delete bste;
return 0;
}