Witam, mam do napisania projekt dotyczący BST. Na różnych forach czytałem wiele kodów, ale zawsze jest coś inaczej i ciągle się gubie jeśli chodzi o usuwanie elementu w drzewie. Oto mój projekt
drzewaBst.cpp
#include "drzewaBST.h"
#include <iostream>
using namespace std;
WezelDrzewa::WezelDrzewa(){
wartosc=0;
lewy=NULL;
prawy=NULL;
}
WezelDrzewa::WezelDrzewa(int x){
wartosc=x;
lewy=NULL;
prawy=NULL;
}
WezelDrzewa::WezelDrzewa(int x,WezelDrzewa *wskLewy,WezelDrzewa *wskPrawy){
wartosc=x;
lewy=wskLewy;
prawy=wskPrawy;
}
void dodajDoBST(WezelDrzewa *&korzen, int x){
if(korzen==NULL)
korzen=new WezelDrzewa(x);
else{
bool wstawilem=false;
WezelDrzewa *pomocnik=korzen;
while(wstawilem==false){
if(pomocnik->wartosc>x)
{
if(pomocnik->lewy!=NULL){
pomocnik=pomocnik->lewy;
}
else{
pomocnik->lewy=new WezelDrzewa(x);
wstawilem=true;
}
}
else{
if(pomocnik->prawy!=NULL){
pomocnik=pomocnik->prawy;
}
else{
pomocnik->prawy=new WezelDrzewa(x);
wstawilem=true;
}
}
}
}
}
void wyswietlPreorder(WezelDrzewa *&korzen){
if(korzen!=NULL)
{
cout << korzen->wartosc << " ";
wyswietlPreorder(korzen->lewy);
wyswietlPreorder(korzen->prawy);
}
}
void wyswietlPostorder(WezelDrzewa *&korzen){
if(korzen!=NULL)
{
wyswietlPreorder(korzen->lewy);
wyswietlPreorder(korzen->prawy);
cout << korzen->wartosc << " ";
}
}
void wyswietlInorder(WezelDrzewa *&korzen){
if(korzen!=NULL)
{
wyswietlPreorder(korzen->lewy);
cout << korzen->wartosc << " ";
wyswietlPreorder(korzen->prawy);
}
}
WezelDrzewa wyszukiwanie(WezelDrzewa *&korzen,int x){
while(korzen!=NULL){
if(korzen->wartosc==x){
break;
}
if(korzen->wartosc>x){
korzen=korzen->lewy;
cout << "Przechodze do lewego" << endl;
}
if(korzen->wartosc<x){
korzen=korzen->prawy;
cout << "Przechodze do prawego" << endl;
}
}
return korzen->wartosc;
}
int treeHeight(WezelDrzewa *&korzen)
{
if (korzen == NULL)
{
return -1;
}
int lewy = treeHeight(korzen->lewy);
int prawy = treeHeight(korzen->prawy);
return 1 + std::max(lewy, prawy);
}
void usuwanie(WezelDrzewa *&korzen,int x){ // na 100% źle, próbowałem usunać chociaż liścia...
while(korzen!=NULL){
WezelDrzewa *pom;
if(korzen->wartosc==x){
pom=korzen;
korzen=NULL;
}
if(korzen->wartosc>x){
korzen=korzen->lewy;
cout << "Przechodze do lewego" << endl;
}
if(korzen->wartosc<x){
korzen=korzen->prawy;
cout << "Przechodze do prawego" << endl;
}
}
}
void ZwalniaDrzewo(WezelDrzewa *&korzen)
{
WezelDrzewa *pom,*pop;
pom=korzen;
while(pom!=NULL)
pom=pom->lewy;
pop=pop->prawy;
}
int wysokosc(WezelDrzewa *korzen)
{
int i,j=0;
if(korzen==NULL)
return 0;
else
{
i=wysokosc(korzen->lewy);
j=wysokosc(korzen->prawy);
if(i>j)
return (i+1);
else
return (j+1);
}
}
WezelDrzewa *getParent(WezelDrzewa *&korzen,int x)
{
WezelDrzewa *rodzic=NULL;
while(korzen)
{
if(korzen->wartosc>x)
korzen=(rodzic=korzen)->lewy;
else if(korzen->wartosc<x)
korzen=(rodzic=korzen)->prawy;
else {
cout << "znalazlem rodzica :)" << endl;
return rodzic;
}
}
return NULL;
}
drzewaBST.h
#ifndef drzewaBST_h
#define drzewaBST_h
class WezelDrzewa{
public:
int wartosc;
WezelDrzewa *lewy;
WezelDrzewa *prawy;
WezelDrzewa();
WezelDrzewa(int x);
WezelDrzewa(int x, WezelDrzewa *wskLewy, WezelDrzewa *wskPrawy);
};
void dodajDoBST(WezelDrzewa *&korzen, int x);
void DodajDoBSTRek(WezelDrzewa *&korzen,int x);
void wyswietlPreorder(WezelDrzewa *&korzen);
void wyswietlPostorder(WezelDrzewa *&korzen);
void wyswietlInorder(WezelDrzewa *&korzen);
WezelDrzewa wyszukiwanie(WezelDrzewa *&korzen,int x);
void usuwanie(WezelDrzewa *&korzen,int x);
int wysokosc(WezelDrzewa *korzen);
int treeHeight(WezelDrzewa *&korzen);
void ZwalniaDrzewo(WezelDrzewa *&korzen);
WezelDrzewa *getParent(WezelDrzewa *&korzen,int x);
#endif
a to mój main:
#include <iostream>
#include "drzewaBST.h"
#include <cstdlib>//rand
#include <time.h>
using namespace std;
int main(int argc, char** argv) {
WezelDrzewa *korzen=0;
WezelDrzewa *pom;
cout << " " << endl;
int x;
int n;
do{
cout << "1.Dodanie do drzewa" << endl;
cout << "2.Wyswietl PreOrder" << endl;
cout << "3.Wyswietl PostOrder" << endl;
cout << "4.Wyswietl InOrder" << endl;
cout << "5. Dodaj" << endl;
cout << "6.Znajdz" << endl;
cout << "7.Wysokosc drzewa" << endl;
cout << "8.Zwolnij" << endl;
cout << "9.Usuwanie" << endl;
cout << "0.Wyjscie" << endl;
cin >> x;
switch(x){
case 0:
break;
case 1:
cout << "Wybrales dodanie do drzewa" << endl;
cout << "Podaj ile liczb losowych chcesz dodac do drzewa: " << endl;
cin >> n;//ilosc wezlow
{
//clock_t start,koniec;
//start=clock();
//start=start-clock();
{
for(int i=0;i<n;i++){
int j;
j=rand()%30;
if(j==j){
j=rand()%50;
}
dodajDoBST(korzen,j);
}
}
//koniec=clock();
//long czas=koniec-start;
//cout << "czas w ms: " << czas << endl;
}
break;
case 2:
cout << "Wyswietlanie PreOrder: " << endl;
wyswietlPreorder(korzen);
cout << endl;
break;
case 3:
cout << "Wyswietlanie PostOrder: " << endl;
wyswietlPostorder(korzen);
cout << endl;
break;
case 4:
cout << "Wyswietl InOrder:" << endl;
wyswietlInorder(korzen);
cout << endl;
break;
case 5:
cout << "Podaj wezel, ktory chcesz dodac:" << endl;
cin >> n;
DodajDoBSTRek(korzen,n);
cout << endl;
break;
case 6:
cout << "Wyszukiwanie:" << endl;
cin >> n;
wyszukiwanie(korzen,n);
cout << endl;
break;
case 7:
cout << "Wysokosc:" << endl;
cout << treeHeight(korzen) << endl;
cout << endl;
break;
case 8:
cout << "Zwolnienie drzewa" << endl;
ZwalniaDrzewo(korzen);
cout << endl;
break;
case 9:
cout << "Usuwanie:" << endl;
cout << "Podaj klucz do usuniecia" << endl;
cin >> n;
usuwanie(korzen,n);
cout << endl;
break;
case 10:
cout << "Szukanie rodzica" << endl;
cin >> n;
pom=getParent(korzen,n);
cout << endl;
break;
default:
cout << "Error" << endl;
}
}while(x!=0);
return 0;
}
Proszę o jakąkolwiek pomoc w usuwaniu...