Witam serdecznie!
Jestem totalnie początkująca jeśli chodzi o język C++. Poza tym to moje pierwsze starcie z drzewami BST w tym języku więc z góry proszę o wyrozumiałość :D
Program się kompiluję ale jest problem z pamięcią i niestety nie mam pojęcia jak go naprawić. Program muszę jutro oddać więc mile widziana będzie pomoc w naprawie.
// drzewa_lab03_struktury.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
/**************** PROTOTYPY FUNKCJI ****************/
/*drzewoBST* szukaj(drzewoBST *start, int liczba);
int Dodaj(drzewoBST *start, int liczba);
void DodajWiele(drzewoBST *start, int liczba);
drzewoBST* najbardziejLewy (drzewoBST *start);
void Usun(drzewoBST *start);*/
/**************** STRUKTURA DRZEWA ****************/
struct drzewoBST
{
int data;
drzewoBST *rodzic;
drzewoBST *lewy; //lewy potomek
drzewoBST *prawy; //prawy potomek
};
drzewoBST *korzeń;
/**************** FUNCJA WYSZUKIWANIA ****************/
//funkcja zwraca węzeł o podanej wartości bądź null gdy taki węzeł nie istnieje
drzewoBST* szukaj(drzewoBST *start, int liczba) {
// węzeł ma szukaną wartość
if (start->data == liczba)
{
cout<< "Element " << liczba << " jest w drzewie!"<<endl;
return (start);
}
//węzeł jest mniejszy od podanej liczby więc sprawdzamy lewe poddrzewo
else if (start->data < liczba && start->lewy != NULL)
{
return (szukaj(start->lewy, liczba));
}
//węzeł jest większy od podanej liczby więc sprawdzamy prawe poddrzewo
else if (start->data < liczba && start->prawy != NULL)
{
return (szukaj(start->prawy, liczba));
}
cout<< "Brak elementu " << liczba << " w drzewie!" << endl;
return NULL;
}
/**************** FUNCJA DODAWANIA WĘZŁÓW ****************/
//dodaje węzeł o podanej liczbie przez użytkownika (liczba) do drzewa o korzeniu start
int Dodaj(drzewoBST *start, int liczba){
//jeżeli drzewo jest puste dodaj korzeń start
/*1*/ if (korzeń == NULL )
{
drzewoBST *korzeń = new drzewoBST;
korzeń->data = liczba;
korzeń->lewy = NULL;
korzeń->prawy = NULL;
korzeń->rodzic = NULL;
}
//jeżeli liczba jest mniejsza od korzenia idziemy do lewego
/*1*/ else if (liczba < start->data)
{
if (start->lewy != NULL) //sprawdzamy czy istnieje lewe poddrzewo
{
Dodaj(start->lewy, liczba); //rekurencja
}
else
{
drzewoBST *nowy = new drzewoBST;
nowy->data = liczba;
nowy->lewy = NULL;
nowy->prawy = NULL;
nowy->rodzic = start;
start->lewy = nowy;
}
}
/*1*/ else //sprawdzam czy liczba jest większa bądź równa korzeniowi
{
if (start->prawy != NULL)
{
Dodaj(start->prawy, liczba); //rekurencja
}
else
{
drzewoBST *nowy = new drzewoBST;
nowy->data = liczba;
nowy->lewy = NULL;
nowy->prawy = NULL;
nowy->rodzic = start;
start->prawy = nowy;
}
}
return 0;
}
/**************** FUNCJA DODAWANIU WIELU ELEMENTÓW ****************/
void DodajWiele (drzewoBST *start, int liczba){
srand(time(NULL));
for (int i = 0; i < liczba; i++)
{
Dodaj(start, rand());
}
}
/**************** FUNCJA WYSZUKIWANIA NAJMNIEJSZEJ WARTOŚCI Z LEWEJ STRONY ****************/
drzewoBST* najbardziejLewy (drzewoBST *start){
if (start->lewy == NULL)
{
return (start->lewy);
}
else
{
return start;
}
}
/**************** FUNCJA USUWANIA WĘZŁÓW ****************/
void Usun(drzewoBST *start){
/*1*/ if (start->lewy == NULL && start->prawy == NULL) //jeżeli węzeł nie ma dzieci
{
/*2*/ if (start->rodzic == NULL) //jeżeli węzeł jest korzeniem
{
korzeń = NULL;
}
/*2*/ else if (start->rodzic->lewy == start) //jeżeli usuwany węzeł jest po lewej stronie
{
start->rodzic->lewy = NULL;
}
/*2*/ else // węzeł jest po prawej stronie
{
start->rodzic->prawy = NULL;
}
delete start;
}
/*1*/ else if (start->lewy == NULL || start->prawy == NULL) //węzeł ma tylko jedno dziecko
{
/*3*/ if (start->lewy == NULL) // po lewej stronie brak dziecka
{
/*4*/ if (start->rodzic == NULL) // jest korzeniem
{
korzeń = start->prawy;
}
/*4*/ else if (start->rodzic->lewy == start) // po lewej stronie rodzica
{
start->rodzic->lewy = start->prawy; // przyczepiamy z lewej rodzica to co z prawej usuwanego węzła
}
/*4*/ else
{
start->rodzic->prawy = start->prawy; // przyczepiamy z prawej rodzica to co z prawej usuwanego węzła
}
}
/*3*/ else
{
/*5*/ if (start->rodzic == NULL) // jest korzeniem
{
korzeń = start->lewy;
}
/*5*/ else if (start->rodzic->lewy == start) // po lewej stronie rodzica
{
start->rodzic->lewy = start->lewy; // przyczepiamy z lewej rodzica to co z lewej usuwanego węzła
}
/*5*/ else
{
start->rodzic->prawy = start->lewy; // przyczepiamy z prawej rodzica to co z lewej usuwanego węzła
}
}
delete start;
}
/*1*/ else
{
drzewoBST *tmp; // w miejsce usuwanego elementu wstawiam najmniejszą wartość z prawego poddrzewa
tmp = najbardziejLewy(start->prawy);
start->data = tmp->data;
Usun(tmp);
}
}
/**************** FUNCJA PRZECHODZENIA DRZEWA INORDER ****************/
void INORDER (drzewoBST *start) {
if (start->lewy != NULL)
{
INORDER(start->lewy);
cout<< "-> " << start->data << endl;
}
else if (start->prawy != NULL)
{
INORDER(start->prawy);
cout<< "-> " << start->data << endl;
}
else
{
cout << "Drzewo jest puste!" << endl;
}
}
/**************** PROGRAM GŁÓWNY ****************/
int _tmain(int argc, _TCHAR* argv[])
{
drzewoBST *start = NULL;
Dodaj(start, 23);
Dodaj(start, 18);
Dodaj(start, 2);
Dodaj(start, 7);
Dodaj(start, 3);
cout<<endl;
INORDER(start);
cout<<endl;
DodajWiele(start, 5);
cout<<endl;
szukaj(start,23);
szukaj(start, 20);
cout<<endl;
cout<<"Usuwanie węzła 23"<<endl;
Usun(szukaj(start, 23));
cout<<"Usuwanie węzła 7"<<endl;
Usun(szukaj(start, 7));
cout<<endl;
cout<<"Przechodzenie drzewa w kolejnosci in order"<<endl;
INORDER(start);
cout<<endl;
return 0;
}