Usuwanie elementu z drzewa(klasy) BST

Question

Mam do zaprojektowania i zaimplementowania klase BST jak w temacie. Udalo mi sie zrobic dodawanie elementu do drzewa i wyswietlanie, co nie bylo takie trudne.Problem pojawia sie jednak przy probach usuwania elementu z drzewa.W jaki sposob mogłaby wyglądac przykladowa implementacja?Mam tez do zrobienia obsługę błędów, ale z tym mysle, ze sobie poradzę.

class BuildandReconstructBST
{
	BuildandReconstructBST *left, *right;
	int value;
public:
	BuildandReconstructBST();
	~BuildandReconstructBST();
	void AddElement(int);
	void deleteElement(int);
	BuildandReconstructBST* FindMin(BuildandReconstructBST*);
	
	void PrintTree();
};

BuildandReconstructBST::BuildandReconstructBST() { this->value = 0; this->left = nullptr; this->right = nullptr; };
BuildandReconstructBST::~BuildandReconstructBST() {};
void BuildandReconstructBST::AddElement(int value)
{
	
	if (this->value != 0)
	{
		if (this->value > value)
		{
			if (this->value == value)
			{
				std::string wyjatek = "BLAD:Istnieje juz taki element na drzewie\n"; throw wyjatek;
			}
			else 
			if (this->left == nullptr)
				this->left = new BuildandReconstructBST();
			this->left->AddElement(value);
		}
		else
		{
			if (this->value == value)
			{
				std::string wyjatek = "BLAD:Istnieje juz taki element na drzewie\n"; throw wyjatek;
			}
			else 
			if (this->right == nullptr)
				this->right = new BuildandReconstructBST();
			this->right->AddElement(value);
		}
	}
	else
		 this->value = value;
}
void BuildandReconstructBST::PrintTree()
{
	if (this->left != nullptr)
		this->left->PrintTree();
	std::cout << this->value << std::endl;
	if (this->right != nullptr)
		this->right->PrintTree();
}

 

Comments

BuildandReconstructBST* BuildandReconstructBST::deleteElement(BuildandReconstructBST* root, int key)
{
	if (root == NULL) return root;
	if (key < root->value)
		root->left = deleteElement(root->left, value);

	else if (key > root->value)
		root->right = deleteElement(root->right, value);
	else
	{
		if (root->left == NULL)
		{
			struct BuildandReconstructBST *temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL)
		{
			struct BuildandReconstructBST *temp = root->left;
			free(root);
			return temp;
		}
		BuildandReconstructBST *temp = FindMin(root->right);
		root->value = temp->value;
		root->right = deleteElement(root->right, temp->value);
	}
	return root;
}

Tak wyglada.

---

Pomysl fajny i doceniam wysilek w to wlozony, program sie kompiluje ale nie usuwa zadanego elementu.

---

Wysiłek żaden, Pokaż kod.

 

PS. pisz w komentarzu mojej odpowiedzi.

---

Funkcja main.

BuildandReconstructBST bst;
	int wybor;
	do
	{
		std::cout << "Prosze wybrac ktoras z ponizszych opcji: ";
		std::cout << "\n'1'-dodawanie do drzewa\n'2'-usuwanie z drzewa\n'3'-Wyswietlanie drzewa";
		std::cin >> wybor;
		switch (wybor)
		{
		case 1:
		{
			try {
				int y;
				std::cout << "Wpisz element do drzewa: ";
				std::cin >> y;
				try { bst.AddElement(y); }catch(std::string x) { std::cout << x;};
			}
			catch(std::string x){std::cout << x; };
			break;
		}
		case 2:
		{
			bst.deleteElement(2);
		}
		case 3:
		{
			bst.PrintTree();
			break;
		}
		}
	} while (wybor != 0);

plik .hpp

class BuildandReconstructBST
{
	BuildandReconstructBST *left, *right;
	int value;
	BuildandReconstructBST* delete_element(BuildandReconstructBST* root, int key)
	{
		if (root == nullptr) return root;
		if (key < root->value)
		{
			root->left = delete_element(root->left, value);
		}
		else if (key > root->value)
		{
			root->right = delete_element(root->right, value);
		}
		else
		{
			if (root->left == nullptr)
			{
				BuildandReconstructBST *temp = root->right;
				delete root;
				return temp;
			}
			else if (root->right == nullptr)
			{
				BuildandReconstructBST *temp = root->left;
				delete root;
				return temp;
			}

			BuildandReconstructBST *temp = FindMin(root->right);
			root->value = temp->value;
			root->right = delete_element(root->right, temp->value);
		}
		return root;
	}
	BuildandReconstructBST* root_node;
public:
	BuildandReconstructBST();
	~BuildandReconstructBST();
	void AddElement(int);
	void deleteElement(int key);
	BuildandReconstructBST* FindMin(BuildandReconstructBST*);
	void PrintTree();
};

A nie wiem czy ja mialem stworzyc druga klase i po prostu zastosowac dziedziczenie czy zrobic tak jak zrobilem?

 

---

Nie. Ja zmieniłem kod. Patrz poniższa odpowiedź.

Answer 1

@Zielony12,  Ta funkcja musi mieć dwa parametry, bo jest wywoływana rekurencyjnie. Dodatkowo ta funkcja może usunąć obiekt root, więc nie powinna być metodą klasy BuildandReconstructBST.

 

Tak bym zrobił:

class BSTTree
{
private:
	BuildandReconstructBST* delete_element(BuildandReconstructBST* root, int key)
	{
		if (root == NULL) return root;
		if (key < root->value)
		{
			root->left = delete_element(root->left, value);
		}
		else if (key > root->value)
		{
			root->right = delete_element(root->right, value);
		}
		else
		{
			if (root->left == NULL)
			{
				BuildandReconstructBST *temp = root->right;
				delete root;
				return temp;
			}
			else if (root->right == NULL)
			{
				BuildandReconstructBST *temp = root->left;
				delete root;
				return temp;
			}

			BuildandReconstructBST *temp = FindMin(root->right);
			root->value = temp->value;
			root->right = delete_element(root->right, temp->value);
		}
		return root;
	}

	BuildandReconstructBST* root_node;

public:

	...

	void deleteElement(int key)
	{
		root_node = delete_element(root_node, key);
	}

};

 

PS. przeniosłem posta z komentarza, bo w zasadzie to odpowiedź :)

Comments

@j23, Co to jest za klasa ta BSTTree?

---

Klasa, która reprezentuje drzewo.

---

Tyle to sie zdolalem domyslic, mialem na mysli czy to jest dodatkowa klasa?

---

No tak. Skoro się domyśliłeś, to powinieneś to wiedzieć ;) Powinieneś dodać do niej resztę niezbędnych metod.