Cześć.
Mam problem z algorytmem usuwającym elementy drzewa BST. Otóż po usunięciu elementu nie działa funkcja wypisująca elementy drzewa. Co ciekawe jeśli wypisze je ręcznie to nie ma problemu. Z góry dzięki za poświęcony czas i pomoc ;)
#include<iostream>
using namespace std;
class Element {
public:
int value;
Element* father;
Element* left;
Element* right;
Element(int d) {
value = d;
left = NULL;
right = NULL;
}
};
class BSTtree {
private:
Element* root;
void goPrivate(Element* apex);
void remove_no_child(Element* temp);
void remove_one_child(Element* temp);
void remove_two_children(Element* temp);
public:
void add(int data); // dodaj do drzewa nowy wiezcholek
void remove(int data);
void go_in_order();
void balance();
BSTtree() {
root = NULL;
}
};
void BSTtree::goPrivate(Element* apex) {
if (apex == NULL) return;
// cout << "apex-> value:"<< apex->value << endl;
goPrivate(apex->left);
cout << "Element drzewa: " << apex->value << endl;
goPrivate(apex->right);
}
void BSTtree::add(int data) {
Element* newElement = new Element(data);
// puste drzewo
if (root == NULL) {
root = newElement;
return;
}
Element* temp = root;
while ((temp->left != NULL && data < temp->value) || (temp->right != NULL && data >= temp->value)) { // przechodzimy dopoki nie znajdziemy pustego miejsca
if (data < temp->value) {
temp = temp->left;
}
else if(data >= temp->value){
temp = temp->right;
}
}
if (data < temp->value) {
temp->left = newElement;
newElement->father = temp;
}
else if (data >= temp->value) {
temp->right = newElement;
newElement->father = temp;
}
}
void BSTtree::remove(int data) {
Element* temp = root;
while (temp != NULL && temp->value != data) { // przechodzimy dopoki nie znajdziemy delikwenta
if (data < temp->value) {
temp = temp->left;
}
else {
temp = temp->right;
}
}
if (temp == NULL) {
cout << "Nie ma takiego wiezcholka" << endl;
return;
}
if (temp->left == NULL && temp->right == NULL) {
remove_no_child(temp);// Przypadek A - brak potomkow
}
if (temp->left != NULL && temp->right == NULL) {
remove_one_child(temp);// Przypadek B - jeden potomek
}
if (temp->left == NULL && temp->right != NULL) {
remove_one_child(temp);// Przypadek B - jeden potomek
}
if (temp->left != NULL && temp->right != NULL) {
remove_two_children(temp); // Przypadek C - dwoch potomkow
}
delete temp;
}
void BSTtree::remove_no_child(Element* temp){
// Przypadek A - brak potomkow
// usuwany jest korzeniem
if (temp->father == NULL) {
return;
}
// usuwany jest prawym potomkiem
if (temp->father->right == temp) {
temp->father->right = NULL;
return;
}
// usuwany jest lewym potomkiem
if (temp->father->left == temp) {
temp->father->left == NULL;
return;
}
}
void BSTtree::remove_one_child(Element* temp){
// Przypadek B - jeden potomek
Element* child = NULL;
if (temp->left == NULL) child = temp->right;
if (temp->right == NULL) child = temp->left;
if (temp->father == NULL) {
root = child;
return;
}
// usuwany jest lewym potomkiem
if (temp->father->left == temp) {
temp->father->left = child;
return;
}
// usuwany jest prawym potomkiem
if (temp->father->right == temp) {
temp->father->right = child;
return;
}
}
void BSTtree::remove_two_children(Element* temp) {
// Przypadek C usuwany ma dwoch potomkow
Element *ptr, *suc;
ptr = temp->right;
while (ptr->left != NULL) {
ptr = ptr->left;
}
// teraz ptr to pierwszy wiekszy element od usuwanego; usuwamy go
suc = ptr;
if (suc->left == NULL && suc->right == NULL) {
remove_no_child(suc);
}
else {
remove_one_child(suc);
}
if (temp->father == NULL) {
root = suc;
}
else {
if (temp == temp->father->left) {
temp->father->right = suc;
}
else {
temp->father->left = suc;
}
suc->left = temp->left;
suc->right = temp->right;
suc->father = temp->father;
}
}
void BSTtree::go_in_order() {
if (root == NULL) cout << "Drzewo jest puste :)" << endl;
goPrivate(root);
}
int main() {
BSTtree* one = new BSTtree;
one->add(20);
one->add(5);
one->add(4);
one->add(3);
one->add(6);
one->add(7);
one->add(10);
one->add(8);
one->go_in_order();
cout<<"Usuwam 5 (dwoje dzieci):"<<endl;
one->remove(5);
one->go_in_order();
/* one->remove(6);
cout << "Po usunieciu 6:" << endl;
one->go_in_order();
one->remove(8);
one->remove(5);
one->remove(4);
one->remove(3);
one->remove(7);
one->go_in_order();
*/ system("pause");
return 0;
}