lojo Temat założony przez niniejszego użytkownika |
Usuwanie elemenu drzewo BST » 2015-01-25 13:03:18 Witam mam problem z usuwaniem elementu z drzewa BST po usunięciu elementu i próbie wyświetlenia drzewa wywala mi błąd "Program przestał działać" i nie wiem dlaczego mógłby ktoś pomóc?
class BST{ public: int wartosc; BST *rodzic; BST *lewy; BST *prawy; BST(int x);
};
BST::BST(int x) { wartosc=x; lewy=NULL; prawy=NULL; }
BST * NajwiekszyKluczWPoddrzewie(BST * korzen) { BST * x = korzen;
while(x->prawy) x = x->prawy;
return x; }
BST * Poprzednik(BST * x) { if(x->lewy) return NajwiekszyKluczWPoddrzewie(x->lewy); BST * y;
do { y = x; x = x->rodzic; } while(x && (x->prawy != y));
return x; }
BST* Znajdz(BST *korzen, int x) { while(korzen) { if(korzen->wartosc==x) { return korzen; } else if(korzen->wartosc<x) {="{" korzen="korzen-">prawy; } else { korzen=korzen->lewy; } } }
void UsunelementDrzewaBST(BST *&korzen, int k) {
BST* usun = Znajdz(korzen,k); if (usun) { if ((usun->lewy) && (usun->prawy)) { BST* poprzedni = Poprzednik(usun); usun->wartosc=poprzedni->wartosc; if (poprzedni->rodzic->lewy == poprzedni) poprzedni->rodzic->lewy=poprzedni->lewy; else poprzedni->rodzic->prawy=poprzedni->lewy; delete poprzedni; } else { BST* poddrzewo = usun->lewy ? usun->lewy : usun->prawy; if (usun->rodzic) { if (usun->rodzic->lewy == usun) usun->rodzic->lewy = poddrzewo; else usun->rodzic->prawy = poddrzewo; if (poddrzewo) poddrzewo->rodzic = usun->rodzic; } else { poddrzewo->rodzic=NULL; korzen=poddrzewo; } delete usun; } } } |
|
darko202 |
» 2015-01-26 07:47:10 1. w metodzie BST* Znajdz(BST *korzen, int x) brakuje return
2. w tej metodzie masz też błąd składni w linii else if(korzen->wartosc<x) {="{" korzen="korzen-">prawy; |
|
lojo Temat założony przez niniejszego użytkownika |
a » 2015-01-26 09:44:02 metode Znajdz poprawilem calkiem ale nadal nie działa...
BST * BSTsearch(BST * root, int key) { BST * x = root;
while((x) && (x->wartosc != key)) x = (key < x->wartosc) ? x->lewy : x->prawy;
return x; } |
|
darko202 |
» 2015-01-26 13:50:06 1. mógłbyś dołączyć pełny kod po zmianach + zawartość main
2. nie zapomnij o formatowaniu kodu [cpp] [/cpp] 3. opisz w którym miejscu się wykłada |
|
lojo Temat założony przez niniejszego użytkownika |
» 2015-01-27 09:03:57 Main.cpp #include <iostream> #include "drzewaBinarne.h"
using namespace std;
int main( int argc, char ** argv ) { Menu(); return 0; }
drzewaBinarne.h #ifndef drzewaBinarne_h #define drzewaBinarne_h
class BST { public: int wartosc; BST * rodzic; BST * lewy; BST * prawy; BST( int x ); };
void DodajElementDoDrzewaBST( BST *& korzen, int x ); void UsunelementDrzewaBST( BST *& korzen, int k ); void DodajBSTzTablica( int a[], int rozmiar, BST *& korzen ); BST * Znajdz( BST * korzen, int x ); BST * NajwiekszyKluczWPoddrzewie( BST * korzen ); BST * Poprzednik( BST * x );
void WyswietlInOrder( BST * korzen ); void WyswietlPreOrder( BST * korzen ); void WyswietlPostOrder( BST * korzen );
BST * LosoweKlucze();
void Sortowanie( BST * korzen );
int WysokoscDrzewaBst( BST * korzen );
void Menu();
#endif
drzewaBinarne.cpp #include "drzewaBinarne.h" #include <iostream> #include <cstdlib> #include <ctime>
using namespace std;
BST::BST( int x ) { wartosc = x; lewy = NULL; prawy = NULL; rodzic = NULL; }
void Menu() { int menu = 1, n; BST * korzen = 0; int tab[] = { 5, 3, 8, 2, 6, 4, 9, 1, 7 }; DodajBSTzTablica( tab, 8, korzen ); while( menu != 0 ) { cout << "\n\t\t\tDRZEWA BST\n\n"; cout << "\t\t\t MENU\n"; cout << "1.) Losowe Drzewo BST.\n"; cout << "2.) Wyswietl in-order.\n"; cout << "3.) Wyswietl pre-order.\n"; cout << "4.) Wyswietl post-order.\n"; cout << "5.) Dodawanie elementu do drzewa BST.\n"; cout << "6.) Usuwanie elementu z drzewa BST.\n"; cout << "7.) Sortowanie drzewa BST.\n"; cout << "8.) Wysokosc Dorzewa BST.\n"; cout << "9.) Wyjscie 0.\n"; cin >> menu; switch( menu ) { case 1: { system( "cls" ); korzen = LosoweKlucze(); break; } case 2: { system( "cls" ); WyswietlInOrder( korzen ); break; } case 3: { system( "cls" ); WyswietlPreOrder( korzen ); break; } case 4: { system( "cls" ); WyswietlPostOrder( korzen ); break; } case 5: { system( "cls" ); cout << "Podaj wartosc ktora chcesz dodac do drzewa BST.\n"; cin >> n; DodajElementDoDrzewaBST( korzen, n ); break; } case 6: { system( "cls" ); cout << "Podaj wartosc elementu ktory chcesz usunac.\n"; cin >> n; UsunelementDrzewaBST( korzen, n ); break; } case 7: { system( "cls" ); WyswietlInOrder( korzen ); break; } case 8: { system( "cls" ); cout << "Wysokosc drzewa BST wynosi: " << WysokoscDrzewaBst( korzen ); break; } } } }
void DodajBSTzTablica( int a[], int rozmiar, BST *& korzen ) { korzen = NULL; for( int i = 0; i < rozmiar; i++ ) { DodajElementDoDrzewaBST( korzen, a[ i ] ); } }
BST * Znajdz( BST * root, int key ) { BST * x = root; while(( x ) &&( x->wartosc != key ) ) x =( key < x->wartosc ) ? x->lewy : x->prawy; return x; }
BST * NajwiekszyKluczWPoddrzewie( BST * korzen ) { BST * x = korzen; while( x->prawy ) x = x->prawy; return x; }
BST * Poprzednik( BST * x ) { if( x->lewy ) return NajwiekszyKluczWPoddrzewie( x->lewy ); BST * y; do { y = x; x = x->rodzic; } while( x &&( x->prawy != y ) ); return x; }
void UsunelementDrzewaBST( BST *& korzen, int k ) { BST * usun = Znajdz( korzen, k ); if( usun ) { if(( usun->lewy ) &&( usun->prawy ) ) { BST * poprzedni = Poprzednik( usun ); usun->wartosc = poprzedni->wartosc; if( poprzedni->rodzic->lewy == poprzedni ) poprzedni->rodzic->lewy = poprzedni->lewy; else poprzedni->rodzic->prawy = poprzedni->lewy; delete poprzedni; } else { BST * poddrzewo = usun->lewy ? usun->lewy: usun->prawy; if( usun->rodzic ) { if( usun->rodzic->lewy == usun ) usun->rodzic->lewy = poddrzewo; else usun->rodzic->prawy = poddrzewo; if( poddrzewo ) poddrzewo->rodzic = usun->rodzic; } else { poddrzewo->rodzic = NULL; korzen = poddrzewo; } delete usun; } } }
void DodajElementDoDrzewaBST( BST *& korzen, int x ) { if( korzen == NULL ) { korzen = new BST( x ); } else { int wstawiono = 0; BST * pom = korzen; while( wstawiono == 0 ) { if( korzen->wartosc <= x ) { if( korzen->prawy == NULL ) { korzen->prawy = new BST( x ); wstawiono = 1; } else { korzen = korzen->prawy; } } else if( korzen->lewy == NULL ) { korzen->lewy = new BST( x ); wstawiono = 1; } else { korzen = korzen->lewy; } } korzen = pom; } }
BST * LosoweKlucze() { int zakres, ilosc; int * t, a; int * T, i; BST * korzen = NULL; do { cout << "Podaj z jakiego zakresu maja byc losowane liczby " << endl; cin >> zakres; cout << endl << "Ile liczb chcesz wylosowac?" << endl; cin >> ilosc; cout << endl << endl << endl; system( "cls" ); } while( zakres < ilosc ); T =( int * ) malloc( zakres * sizeof( int ) ); for( i = 0; i < zakres; i++ ) T[ i ] = i + 1; srand( time( 0 ) ); t =( int * ) malloc( ilosc * sizeof( int ) ); for( i = 0; i < ilosc; i++ ) { a =( rand() % zakres ); t[ i ] = T[ a ]; T[ a ] = T[ zakres - 1 ]; zakres--; } for( i = 0; i < ilosc; i++ ) DodajElementDoDrzewaBST( korzen, t[ i ] ); return korzen; }
int WysokoscDrzewaBst( BST * korzen ) { int hl, hp; if( korzen != NULL ) { hl = WysokoscDrzewaBst( korzen->lewy ); hp = WysokoscDrzewaBst( korzen->prawy ); return( 1 +( hl > hp ? hl: hp ) ); } else return 0; }
void WyswietlPostOrder( BST * korzen ) { if( korzen ) { WyswietlPostOrder( korzen->lewy ); WyswietlPostOrder( korzen->prawy ); cout << korzen->wartosc << " "; } }
void WyswietlPreOrder( BST * korzen ) { if( korzen != NULL ) { cout << korzen->wartosc << " "; WyswietlPreOrder( korzen->lewy ); WyswietlPreOrder( korzen->prawy ); } }
void WyswietlInOrder( BST * korzen ) { if( korzen != NULL ) { WyswietlInOrder( korzen->lewy ); cout << korzen->wartosc << " "; WyswietlInOrder( korzen->prawy ); } }
Program wywala się gdy usunę element i próbuje wyświetlić zawartość drzewa |
|
darko202 |
» 2015-01-27 13:53:05 W funkcji UsunelementDrzewaBST masz wielokrotnie np. poprzedni->rodzic->lewy = poprzedni->lewy;
a oglądając twój główny obiekt korzen to dla wszystkich elementów rodzic = 0x00000000
nie jest to dziwne bo jak popatrzymy na funkcję DodajElementDoDrzewaBST elementu rodzic nie jest wypełniany jakakolwiek wartością
usuwając poprzez komendę poprzedni->rodzic->lewy to faktycznie jest to 0x003456CF12->null->null
stąd opisywany przez Ciebie błąd
Dodatkowo 1. mógłbyś wszystkie te funkcje wciągnąć do klasy jako metody 2. plik klasy jest po to aby umieszczać w nim klasę - konwencja klasa nazywa się identycznie jak plik 3. podciągnij technikę debugowania kodu - unikniesz straty czasu i nerwów
najprostsza technika : * wyświetlam wartość zmiennej (klas, warunków, itp. ) * tryb debug kompilatora i watch na badaną zmienną |
|
« 1 » |