Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Usuwanie elemenu drzewo BST

Ostatnio zmodyfikowano 2015-01-27 13:53
Autor Wiadomość
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;
        }
    }
}
P-125522
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;
  
P-125555
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;
}
P-125558
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
P-125560
lojo
Temat założony przez niniejszego użytkownika
» 2015-01-27 09:03:57
Main.cpp
C/C++
#include <iostream>
#include "drzewaBinarne.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

int main( int argc, char ** argv ) {
   
    Menu();
   
    return 0;
}
drzewaBinarne.h
C/C++
#ifndef drzewaBinarne_h
#define drzewaBinarne_h

class BST {
public:
    int wartosc;
    BST * rodzic;
    BST * lewy;
    BST * prawy;
    BST( int x );
   
   
};

//1
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 );


//2
void WyswietlInOrder( BST * korzen );
void WyswietlPreOrder( BST * korzen );
void WyswietlPostOrder( BST * korzen );
//3
BST * LosoweKlucze();
//4
void Sortowanie( BST * korzen );
//5
int WysokoscDrzewaBst( BST * korzen );


//dodatkowe
void Menu();



#endif
drzewaBinarne.cpp
C/C++
#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 ) {
        // system (" CLS ");
        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 ) ); //zaalokuj pamiec na pule liczb do wylosowania
    for( i = 0; i < zakres; i++ )
         T[ i ] = i + 1;
   
    srand( time( 0 ) );
    t =( int * ) malloc( ilosc * sizeof( int ) ); //zaalokuj pamiec na pule liczb wylosowanych
    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 ) );
        //(1+(jesli hl jest wieksze od hp to zwroc hl w przeciwnym wypadku zwroc 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
P-125593
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ą
P-125601
« 1 »
  Strona 1 z 1