rendered paste body#include <iostream>
using namespace std;
class node {
public:
int wartosc ;
node * lewy ;
node * prawy ;
node(int x) {wartosc=x, lewy=NULL, prawy=NULL;}
void dodaj(int x);
void usun(int x);
void wypisz(node *wsk) ;
};
node * root ;
/////////////////////////////////////////////
void node::dodaj (int x)
{
if(root!=NULL) {
node *q=root, *nowy;
while(q) {
if (q->wartosc < x)
{
nowy=q->prawy;
if(nowy==NULL)
{
q->prawy=new node(x);
return;
}
}
else
{
nowy=q->lewy;
if(nowy==NULL)
{
q->lewy=new node(x);
return;
}
}
q=nowy;
}
}
else root=new node(x);
}
////////////////////////////////////////
void node::usun(int x) {
if(root==NULL) {cout << "nie ma co usuwać - lista jest juz pusta" << endl;return ;}
node * q = root ;
node * rodzic = NULL;
while( (q != NULL) && (q->wartosc!=x)) {
cout << "petlu" << endl;
if(q->wartosc > x )
{
rodzic = q ;
q = q->lewy;
}
else if(q->wartosc < x )
{
rodzic = q ;
q = q->prawy;
}
}
if(q==NULL) { cout << "Nie znaleziono elementu do usuniecia" << endl; return ;}
else {
//mamy do czynienia z lisciem?
if(q->lewy == NULL && q->prawy ==NULL) {
if(rodzic==NULL) {root=NULL; return ;}
if(rodzic->lewy==q) {
rodzic->lewy=NULL ;
delete q ;
}
else {
rodzic->prawy=NULL;
delete q ;
}
return ;
}
//ma tylko lewego syna:
if(q->lewy!=NULL && q->prawy==NULL) {
if(rodzic==NULL) {root=q->lewy; return ;}
if(rodzic->lewy==q) {
rodzic->lewy=q->lewy ;
delete q ;
return ;
}
else {
rodzic->prawy=q->lewy ;
delete q ;
return ;
}
}
///ma tylko prawego syna
else if (q->prawy!=NULL && q->lewy==NULL) {
if(rodzic==NULL) {root=q->prawy; return ;}
if(rodzic->lewy==q) {
rodzic->lewy=q->prawy ;
delete q ;
return ;
}
else {
rodzic->prawy=q->prawy;
delete q ;
return ;
}
}
/////
else {
node * wierzejski ;
node * ojciec_z_wermachtu ;
ojciec_z_wermachtu=q ; //q->prawy;
wierzejski=q->prawy ;
while(wierzejski->lewy!=NULL) {
ojciec_z_wermachtu=wierzejski ;
wierzejski=wierzejski->lewy ;
}
if(ojciec_z_wermachtu!=q && wierzejski->prawy!=NULL) ojciec_z_wermachtu->lewy=wierzejski->prawy;
if(rodzic==NULL) {
root=wierzejski;
wierzejski->lewy=q->lewy;
if(q->prawy!=wierzejski)
wierzejski->prawy=q->prawy ;
delete q ;
}
else if(rodzic->prawy=q) {
rodzic->prawy=wierzejski ;
wierzejski->lewy=q->lewy;
if(q->prawy!=wierzejski)
wierzejski->prawy=q->prawy ;
delete q ;
}
else {
rodzic->lewy=wierzejski ;
wierzejski->lewy=q->lewy;
if(q->prawy!=wierzejski)
wierzejski->prawy=q->prawy ;
delete q ;
}
}
}
};
////////////
void node::wypisz(node *wsk)
{
if(wsk)
{
cout<<"(";
wypisz(wsk->lewy);
cout<<wsk->wartosc;
wypisz(wsk->prawy);
cout<<")";
}
else cout<<"*";
}
////////////////////////////
/////////////////
int main() {
int x , a ;
root->dodaj(7) ;
root->dodaj(8) ;
root->dodaj(6) ;
root->dodaj(4) ;
root->dodaj(5) ;
//root->dodaj(9) ;
while (a) {
cout << "implementacja drzewa bst, menu:\n\n" << endl ;
cout << "1 - dodaj element (wartosc)" << endl ;
cout << "2 - usun element (wartosc)" << endl ;
cout << "3 - wyswietl drzewko" << endl ;
cout << "0 - wyjscie " << endl;
cin >> a ;
switch(a) {
case 1:
system("cls");
cout << "Podaj wartosc (nie powtarzaj sie:P)" << endl ;
cin >> x ;
root->dodaj(x) ;
cout << "dodano" << endl ;
system("Pause");
break ;
case 2:
system("cls");
cout << "Podaj wartosc do skasowania" << endl ;
cin >> x ;
root->usun(x) ;
cout << "poszlo w kosmos" << endl ;
system("Pause");
break ;
case 3:
system("cls");
cout << endl ;
root->wypisz(root) ;
cout << endl ;
system("Pause");
break ;
case 0:
return 1;
default:
break ;
}
}
}