Cześć, mam problem z implementacją drzewa binarnego.
#include <iostream>
using namespace std;
struct binarySearchTree {
int value;
binarySearchTree *left;
binarySearchTree *right;
};
binarySearchTree *root = NULL;
void insertNode(binarySearchTree *newNode) {
//jeżeli dodajemy pierwszy element do drzewa to musi być to oddzielna instrukcja
if(root == NULL) {
root = newNode;
}
//jeżeli dodajemy element przynajmniej drugi to ...
else {
//dodatkowy wskaźnik do poruszania się po wartościach w drzewie i porównywania ich z nowo dokładanym elementem
binarySearchTree *temp = root;
//porównujemy elementy znajdujące się w drzewie z nowo wsadzanym elementem, dopóki nie osiągniemy dna drzewa (nowy elementem musi stać się liściem drzewa)
while(temp != NULL)
{
//Pierwszy przypadek - nowo dodany element jest równy elementowi porównywanemu
if(newNode->value == temp->value) {
cout << "Drzewo binarne nie moze posiadac duplikatow c:" << endl;
exit(0);
}
//Drugi przypadek - nowo dodany element jest mniejszy od elementu, z którym go porównujemy i miejsce na lewo jest puste, więc możemy tam go wstawić
//drugi warunek jest konieczny, aby porównywać kolejne elementy (gdyby go nie było to nadpisywalibyśmy elementy)
else if(newNode->value < temp->value) {
if(temp->left == NULL) {
temp->left = newNode;
break;
}
else {
temp = temp->left;
}
}
//Drugi warunek - nowo dodany element jest większy od elementu, z którym go porównujemy i miejsce na prawo jest puste, więc możemy tam go wstawić
//drugi warunek jest konieczny, aby porównywać kolejne elementy (gdyby go nie było to nadpisywalibyśmy elementy)
else if(newNode->value > temp->value) {
if(temp->right == NULL) {
temp->right = newNode;
break;
}
else {
temp = temp->right;
}
}
}
}
}
//1. Sprawdź, czy istnieje lewy
//2. Wypisz
//3. Sprawdź, czy istnieje prawy
void printInorder(binarySearchTree *node)
{
//dno rekurencji - jeśli nie ma ani lewego, ani prawego to cofnij się
if(node == NULL)
return;
//sprawdzam, czy istnieje lewy
printInorder(node->left);
//wypisuje wartość
cout << node->value << ' ';
//sprawdzam, czy istnieje prawy
printInorder(node->right);
}
//1. wypisz
//2. Sprawdź, czy lewy istnieje
//3. Sprawdź, czy prawy istnieje
void printPreorder(binarySearchTree *node)
{
//dno rekurencji - jeśli nie ma ani lewego, ani prawego to cofnij się
if(node == NULL)
return;
//wypisuje
cout << node->value << ' ';
//sprawdzam, czy istnieje lewy
printPreorder(node->left);
//sprawdzam, czy istnieje prawy
printPreorder(node->right);
}
//1. Sprawdź, czy lewy istnieje
//2. Sprawdź, czy prawy istnieje
//3. wypisuje
void printPostorder(binarySearchTree *node)
{
//dno rekurencji - jeśli nie ma ani lewego, ani prawego to cofnij się
if(node == NULL)
return;
//sprawdzam, czy istnieje lewy
printPostorder(node->left);
//sprawdzam, czy istnieje prawy
printPreorder(node->right);
//wypisuje
cout << node->value << ' ';
}
int main()
{
binarySearchTree *newNode = new binarySearchTree;
int input;
while(input != -999)
{
cin >> input;
newNode->value = input;
insertNode(newNode);
}
printInorder(root);
printPreorder(root);
printPostorder(root);
//1.inorder
//2.preorder
//3.postorder
return 0;
}
Problem jest zdefiniowany tak:
Inspirowałem się rozwiązaniem algorytmu z tego filmu:
Funkcje wypisujące drzewo są chyba okej. Z tego co widzę to jest jakiś problem ze wskaźnikiem na korzeń drzewa ale nie jestem pewien i nie wiem jak ten problem rozwiązać.
Potrafiłby mi to ktoś wyjaśnić i ewentualnie poprawić ? Z góry dzięki