Witam wszystkich. Stworzyłem klasę reprezentującą drzewo binarne i posiadającą podstawowe operacje na nim, problem w tym, że wszystko działa do momentu kiedy spróbuję usunąć jakiś element. Wtedy wszystko się sypie i zwyczajnie nie działa (chociaż kompiluje się i odpala). Cztery razy przepisywałem od nowa funkcję Delete i cały czas to samo. Poniżej zamieszczam kod:
Node.h
#ifndef NODE_H_
#define NODE_H_
#include <stdlib.h>
template <class T>
class Node
{
public:
Node(T key2) {
this->key = key2;
this->left = NULL;
this->right = NULL;
this->parent = NULL;
};
Node<T> *right;
Node<T> *left;
Node<T> *parent;
T key;
};
#endif
Tree.h
#ifndef TREE_H_
#define TREE_H_
#include <stdlib.h>
#include "Node.h"
#include <iostream>
template <class T>
class Tree
{
public:
Node<T> *root;
Tree() {
this->root = NULL;
};
//-----------------------------------------------------INSERT--------------------------------------------------------
bool Insert(T keyToInsert) {
if(this->root == NULL) {
this->root = new Node<T>(keyToInsert);
return true;
}
else {
Node<T> *tmp = this->root;
while(tmp != NULL) {
if(keyToInsert < tmp->key) {
if(tmp->left != NULL) {
tmp = tmp->left;
}
else {
tmp->left = new Node<T>(keyToInsert);
return true;
}
}
else if(keyToInsert > tmp->key) {
if(tmp->right != NULL) {
tmp = tmp->right;
}
else {
tmp->right = new Node<T>(keyToInsert);
return true;
}
}
else return false;
}
}
return true;
};
//-----------------------------------------------------SEARCH--------------------------------------------------------
Node<T> *Search(T key, Node<T> *start) {
if(start == NULL || key == start->key) return start;
else if(key < start->key) return Search(key, start->left);
else return Search(key, start->right);
};
//--------------------------------------------------------MIN--------------------------------------------------------
Node<T> *Min(Node<T> *start) {
while(start->left != NULL) {
start = start->left;
}
return start;
};
//----------------------------------------------------NASTEPNIK-----------------------------------------------------
Node<T> *Nastepnik(Node<T> *start) {
if( start->right != NULL ) return Min( start->right );
else
{
Node<T> *tmp = start->parent;
while( tmp != NULL && start != tmp->right )
{
start = tmp;
tmp = tmp->parent;
}
return tmp;
}
};
//-----------------------------------------------------DELETE-------------------------------------------------------
Node<T> *Delete(T key) {
Node<T> *wezelek = Search(key, this->root);
Node<T> *rodzicek = wezelek->parent;
Node<T> *tmp;
if(wezelek->left != NULL && wezelek->right != NULL) {
tmp = Delete(Nastepnik(Search(key, this->root))->key);
tmp->left = wezelek->left;
if(tmp->left != NULL) tmp->left->parent = tmp;
if(tmp->right != NULL) tmp->right->parent = tmp;
}
else tmp = (wezelek->left != NULL) ? wezelek->left : wezelek->right;
if(tmp != NULL) tmp->parent = rodzicek;
if(rodzicek == NULL) this->root = tmp;
else if(rodzicek->left == wezelek) rodzicek->left = tmp;
else rodzicek->right = tmp;
return rodzicek;
};
//-----------------------------------------------------PRINT------------------------------------------------------------
void PrintInOrder(Node<T> *start) {
if(start != NULL) {
PrintInOrder(start->left);
std::cout << start->key << "->";
PrintInOrder(start->right);
}
};
};
#endif
main.cpp
#include "Tree.h"
#include <iostream>
#include <string>
int main() {
Tree<std::string> *Drzewko = new Tree<std::string>();
Drzewko->Insert("Ala");
Drzewko->Insert("Tomek");
Drzewko->Insert("Monika");
Drzewko->Insert("Adam");
Drzewko->Insert("Daniel");
Drzewko->Insert("Zdzislaw");
Drzewko->Insert("Michal");
Drzewko->Insert("Tadeusz");
Drzewko->Insert("Wieslaw");
//Drzewko->Delete("Tomek");
Drzewko->PrintInOrder(Drzewko->root);
std::cout << Drzewko->Search("Tomek", Drzewko->root)->key;
return 0;
};
Z góry dzięki za pomoc.