Tak jak w temacie mam juz zrobiony projekt ale moje drzewo nie przechowuje duzej ilosci wezlow, ma miec przynajmniej 10^6 a przy 10000 program wywala blad ponizej kod.
#include <cstdlib>
#include <iostream>
using namespace std;
struct wezel
{
wezel *lewy, *prawy, *rodzic;
int liczba;
};
class BST
{
public:
wezel *korzen; //wskaznik na adres wezla
int ile;//liczba wezlow
BST();
wezel * BST::najmniejszy(wezel * x);
wezel * BST::najwiekszy(wezel * x);
wezel * BST::nastepnik(wezel *x);
bool wstawianie(wezel *n);
void idz (wezel *x);
wezel * BST::poprzednik(wezel * x);
wezel * BST::usun(wezel * x);
void BST::LiczWezel();
void del (BST * T);
wezel * BST::szukaj(int liczba);
void cale (BST *T);
};
//konstruktor
BST::BST()
{
korzen= NULL;
ile=0;
}
void BST::idz (wezel *x)
{
cout << x->liczba << " : Lewo: ";
if (x->lewy) cout<< x->lewy->liczba;
else cout<< "pusto";
cout << ", Prawo: ";
if(x->prawy) cout << x->prawy->liczba;
else cout <<"pusto";
cout << endl;
if(x->lewy) idz (x->lewy);
if(x->prawy) idz(x->prawy);
}
bool BST::wstawianie (wezel *n)
{
wezel *y = NULL, * x= korzen;
n->lewy = n->prawy = NULL;
while(x)// dopoki x = null
{
y = x; // przekazanie rodzica na y z korzenia
x= (n->liczba <= x->liczba) ? x->lewy : x->prawy;
}
if (!y) korzen=n;
else if (n->liczba <= y->liczba)
y->lewy=n;
else
y->prawy =n;
ile++;
return true;
}
void BST::LiczWezel()
{
cout << " Liczba wezlow drzewa BST : " << ile << endl << endl;
}
void dodaj (BST * T)
{
T->LiczWezel();
cout << "podaj liczbe wezelow";
int i,n;
wezel *x;
cin >>n;
int d[n];
for(i = 0; i < n; i++) d[i] = (rand()%(1000000));
for (i=0;i<n;i++)
{x = new wezel;
cout <<d[i] <<" ";
x->liczba = d[i];
T->wstawianie(x);
}
cout<<endl;
T->idz(T->korzen);
T->LiczWezel();
}
////////////////////////////////
wezel * BST::najmniejszy(wezel * x)
{
while(x->lewy) x = x->lewy;
return x;
}
//////////////////////////////////
wezel * BST::najwiekszy(wezel * x)
{
while(x->prawy) x = x->prawy;
return x;
}
////////////////////////////////////
wezel * BST::poprzednik(wezel * x)
{
if(x->lewy) return najwiekszy(x->lewy);
wezel * y;
do
{ y = x;
x = x->rodzic;
} while(x && (x->prawy !=y));
return x ;
}
///////////////////////////////////////
wezel * BST::nastepnik(wezel *x)
{
if(x->prawy) return najmniejszy (x->prawy);
wezel *y;
do
{
y=x;
x= x->rodzic;
}while(x && (x->lewy !=y));
return x;
}
/////////////////////////////////////
wezel * BST::BST::usun(wezel * x)
{
wezel * y = x->rodzic, *z;
if ((x->lewy) && (x->prawy))
{
z = (rand() %2) ? usun(poprzednik(x)) : usun(nastepnik(x));
z->lewy = x->lewy; if(z->lewy) z->lewy->rodzic = z;
z->prawy = x->prawy; if(z->prawy) z->prawy->rodzic = z;
ile ++;
}
else z = (x->lewy) ? x->lewy : x->prawy;
if (z) z->rodzic = z;
if (y != NULL) korzen = z; // tutaj sie zawiesza ;( !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
else if (y->lewy == x) y->lewy =z; else y->prawy = z;
ile--;
return x;
}
////////////////////////////////////////
void del (BST * T)
{
wezel * x;
int liczba;
cout << "Podaj klucz usuwanego wezla : ";
cin >> liczba;
x = T ->szukaj (liczba);
if (x)
{
delete T-> usun(x);
cout << endl;
if (T->korzen) T-> idz (T->korzen);
T->LiczWezel();
}
else cout << "\n nie ma takiego wezla";
}
void sprawdz(BST * T)
{
cout << "Sprawdzenie obecnosci wezla o danym kluczu w drzewie BST\n"
"--------------------------------------------------------\n\n"
"Podaj klucz wezla : ";
int liczba;
cin >> liczba;
cout << endl;
if(T->szukaj(liczba)) cout << "Wezel znaleziony.\n";
else cout << "W drzewie BST brak wezla o podanym kluczu\n";
}
/////////////////////////////////////////////////
wezel * BST::szukaj(int liczba)
{
wezel * x=korzen;
while ((x) && (x->liczba !=liczba))
x = (liczba < x->liczba) ? x->lewy : x->prawy;
return x;
}
int main(int argc, char *argv[])
{
BST * T = new BST();
int choice;
do
{
system("cls");
cout <<
" [0] Koniec\n"
" [1] Dodaj wezly\n"
" [2] Usun wezel\n"
" [3] Sprawdz obecnosc wezla\n"
"--------------\n"
"Twoj wybor : ";
cin >> choice;
system("cls");
switch(choice)
{
case 1 : dodaj(T); break;
case 2 : del(T); break;
case 3 : sprawdz (T); break;
}
if((choice >= 1) && (choice <=3))
{
cout << endl;
system("pause");
}
} while(choice);
delete T;
system("PAUSE");
return EXIT_SUCCESS;
}