witam, mam dzisiaj proste pytanie .Ostatnio jakiś czas męczę drzewo binarne .Ostateczne udało mi się napisać działającą implementacje tej struktury .Myślę że zanim powiem co dokładnie mam na myśli to podam fragment którego pytanie dotyczy oraz cały kod dla pewności :
Funkcja delete:
void deleteTree(DataTrees *&element) { //usowanie drzewa , element w nagłówku to korzen drzewa
if(element)deleteTree(element->leftChild); //usuwamy dla lewego poddrzewa
if(element)deleteTree(element->rightChild); //usuwamy dla prawego poddrzewa
element = nullptr; //takie proto usuwanie elemntów (kiedy dam po ludzku delete to nie działa)
}
Cały program:
#include "stdafx.h"
using namespace std;
struct DataTrees {
int data;
DataTrees *leftChild;
DataTrees *rightChild;
};
void add(DataTrees *&parent, int value) { //wstawaianie elementu
if (!parent) { //jezeli jest tu puste mijsce
parent = new DataTrees;
parent->data = value;
parent->leftChild = nullptr;
parent->rightChild = nullptr;
}
else { //pezeszukiwanie
if (value >= parent->data) add(parent->rightChild, value);
else add(parent->leftChild, value);
}
}
void inOrder(DataTrees *parent) { //sosrtowaanioe
if (parent) {
inOrder(parent->leftChild);
cout << parent->data << " ";
inOrder(parent->rightChild);
}
}
void find(DataTrees *parent, DataTrees *&element, int value) { //poszukiwanie danej wartosci i ustawianie wskaznika na odpowiedni obiekt
if (!parent) { //jezeli nie znaleziono i nie ma juzz wiecej elementow
cout << "error" << endl;
}
else if (parent->data == value) { //jezeli znaleziono
element = parent;
cout << "is good! " << endl;
}
else { //poszukiwanie binarne
if (value < parent->data) find(parent->leftChild,element,value);
else find(parent->rightChild, element, value);
}
}
void deleteTree(DataTrees *&element) { //usowanie drzewa , element w nagłówku to korzen drzewa
if(element)deleteTree(element->leftChild); //usuwamy dla lewego poddrzewa
if(element)deleteTree(element->rightChild); //usuwamy dla prawego poddrzewa
element = nullptr; //takie proto usuwanie elemntów (kiedy dam po ludzku delete to nie działa)
}
int main()
{
DataTrees *root = nullptr;
DataTrees *element = nullptr;
while (true) {
cout << "---MENU---" << endl;
cout << "1. add" << endl;
cout << "2. inOrder" << endl;
cout << "3. find" << endl;
cout << "4. show find element" << endl;
cout << "5. delete tree" << endl;
cout << "----------" << endl;
char z = _getch();
switch (z) {
case '1': {
cout << "value: ";
int v; cin >> v;
add(root, v);
break;
}
case '2': {
if (root) {
cout << "sort: ";
if(root) inOrder(root);
else cout << 0;
}
else cout << 0 << endl;
_getch();
break;
}
case '3': {
cout << "value: ";
int v; cin >> v;
find(root, element, v);
_getch();
break;
}
case '4': {
if (element) {
cout << "value: " << element->data << endl;
}
else cout << 0 << endl;
_getch();
break;
}
case '5': {
deleteTree(root);
break;
}
}
system("cls");
}
return 0;
}
Jak wspomniałem pytanie dotyczy funkcji deleteTree ,oczywiście działa jak najbardziej ok,tyle że gdyby wniknąć głębiej w pamięć komputera to nie usuwa drzewa :/ . Dzieje się tak dlatego że ustawiamy elementy drzewa na null a tak naprawdę nie usuwamy ich z pamięci ,co prawda w programie tego nie widać ale dla większych baz danych może powodować problemy .Jeżeli jednak zrobię tak :
void deleteTree(DataTrees *&element) {
if(element)deleteTree(element->leftChild);
if(element)deleteTree(element->rightChild);
delete element; //no... teraz nie zadaziała
}
Chociaż wydaje mi się że delete jest bardziej poprawnym rozwiązaniem to po jego użyciu program często się wysypuje ,zwłaszcza po ponownym dodaniu elementów do drzewa . W czym może być problem? A może tak naprawdę nullptr usuwa element i nie zostawia zbędnych rzeczy w pamięci RAM? Z góry dziękuje za pomoc i pozdrawiam :D
