Delete nie działa w implementacji drzewa binarnego

0

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.

1

Zamiast czterokrotnie przepisywać jedną funkcję, użyj jeden raz debuggera ;]

0

A co, Tobie się udało znaleźć to za pomocą debuggera ?

0

A co Tobie udało się znaleźć za pomocą debuggera? I czy w ogóle spróbowałeś?

0

Wydaje mi się, że problem występuje w linii tmp->left = wezelek->left; natomiast nie mam zielonego pojęcia co jest nie tak. Tutaj segmentation fault dostaje według debuggera ;<

0

No cóż poradziłem sobie sam. Problem leży w funkcji dodawania która zapomina ustawić rodziców.

1 użytkowników online, w tym zalogowanych: 0, gości: 1