Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- #include <time.h>
- /*
- Zacznę od tego, że zadanie jest zrobione w C++, według wymagań zadania jest to dozwolone.
- Jest to spowodowane tym, że jednym z wymogów strukturalnego C jest brak globalnej zmiennej na roota.
- Generalnie przekazywanie za każdym razem korzenia jest problematyczne, więc wolałem to zrobić obiektowo w C++. Sorry
- */
- using namespace std; // określenie przestrzeni nazwy
- class Tree;
- // klasa węzła drzewa, na podstawie której tworzone są obiekty węzła
- class TreeNode
- {
- int key; // klucz węzla
- char tab[10]; // tablica znaków
- TreeNode* left; // wskaźnik na lewego potomka
- TreeNode* right; // wskaźnik na prawego potomka
- TreeNode(int); // konstruktor, czyli funkcja, na podstawie której jest tworzony obiekt
- friend class Tree; // to jest po to, żeby klasa Tree mogła korzystać ze składników tej klasy
- };
- class Tree
- {
- int count; // zmienna przechowująca ilość elementów w drzewie
- TreeNode* root; // wskaźnik na korzeń drzewa
- public:
- Tree(); // konstruktor drzewa, czyli jego inicjalizacja
- ~Tree(); // destruktor drzewa, który wypierdala z pamięci wszystkie
- void addNode(int); // dodawanie elementu do drzewa
- void fillTree(int); // zapełnianie drzewa losowymi elementami
- TreeNode* search(int); // szukanie elementu po kluczu podanym w parametrze
- TreeNode* findParent(TreeNode*); // szukanie rodzica elementu
- TreeNode* findSuccessor(TreeNode*); // szukanie nastepnika elementu
- void deleteNode(int); // wypierdalanie elementu z drzewa
- void clearTree(); // wypierdolenie wszystkich elementów z drzewa
- void preOrder(TreeNode*); // wyświetlanie w trybie preorder
- void inOrder(TreeNode*); // wyświetlanie w trybie inorder
- void postOrder(TreeNode*); // domyśl się
- void printPreOrder();
- void printInOrder();
- void printPostOrder();
- };
- int main()
- {
- srand((unsigned int) time(NULL)); // inicjalizacja generatora pseudolosowości
- FILE* file = fopen("inlab03.txt", "r"); // to już było
- // to też
- if (!file)
- {
- cerr << "Niepowodzenie przy otwarciu pliku!" << endl << endl;
- exit(EXIT_FAILURE);
- }
- // tu również bez niespodzianek
- int X, k1, k2, k3, k4;
- fscanf(file, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);
- fclose(file);
- clock_t start = clock();
- Tree* tree = new Tree(); // tu jest inicjalizacja
- tree->deleteNode(k1);
- tree->deleteNode(k1);
- tree->fillTree(X);
- tree->printInOrder();
- tree->printPreOrder();
- tree->addNode(k2);
- tree->printInOrder();
- tree->addNode(k3);
- tree->addNode(k4);
- tree->deleteNode(k1);
- tree->printPreOrder();
- tree->search(k1);
- tree->deleteNode(k2);
- tree->printInOrder();
- tree->deleteNode(k3);
- tree->deleteNode(k4);
- clock_t stop = clock();
- cout << fixed << "Time spent: " << (double) (stop - start) / CLOCKS_PER_SEC << endl << endl;
- delete tree; // porządki
- }
- // konstruktor, który jest wywoływany przy tworzeniu nowego elementu drzewa
- TreeNode::TreeNode(int key)
- {
- this->key = key;
- sprintf(this->tab, "%d", key); // ta funkcja tworzy do tablicy znaków ciąg znaków na podstawie keya
- // każdy nowy element nie ma dzieci
- this->left = NULL;
- this->right = NULL;
- }
- // konstruktor drzewa
- Tree::Tree()
- {
- root = NULL;
- }
- void Tree::addNode(int key)
- {
- // jeżeli w drzewie nic nie ma, to root jest nowym elementem
- if (!root)
- {
- root = new TreeNode(key); // tak tworzy się nowy element
- return; // kończymy zabawę w tej funkcji
- }
- TreeNode* temp = root; // ustawiamy się na rootcie
- // szukanie miejsca na nowy element
- while (temp)
- {
- // jeżeli klucz jest już w drzewie, to kończymy się bawić tą funkcją
- if (temp->key == key)
- return;
- // jeżeli klucz jest mniejszy od klucza tempa, to idziemy na lewo, jak nie, to na prawo
- if (key < temp->key)
- // jeżeli nie ma lewego potomka, to znaleźliśmy miejsce na nowy element
- if (temp->left)
- temp = temp->left;
- else
- break;
- else
- // analogicznie w przypadku prawego potomka
- if (temp->right)
- temp = temp->right;
- else
- break;
- }
- TreeNode* newNode = new TreeNode(key); // tworzymy nowy węzeł
- // wkładamy element do drzewa w taki sposób
- if (key < temp->key)
- temp->left = newNode;
- else
- temp->right = newNode;
- }
- void Tree::fillTree(int X)
- {
- // tu bez niespodzianek
- for (int i = 0; i < X; i++)
- addNode(10 + rand()%9990); // zakres podałem własny, ponieważ w dokumencie był podany od 10000 do 10000. Uznałem to za błąd, więc jak się ktoś przyczepi, zamień zakres tutaj
- }
- TreeNode* Tree::search(int key)
- {
- if (!root)
- return NULL;
- TreeNode* temp = root; // ustawiamy się standardowo na rootcie
- // szukamy elementu, jeżeli znajdziemy, to zwracamy wskaźnik, jeśli nie, to zwracamy nulla
- while (temp)
- {
- if (temp->key == key)
- return temp;
- if (key < temp->key)
- temp = temp->left;
- else
- temp = temp->right;
- }
- return NULL;
- }
- TreeNode* Tree::findParent(TreeNode* child)
- {
- //chyba nie muszę tłumaczyć
- if (!root)
- return NULL;
- if (!child)
- return NULL;
- if (child == root)
- return NULL;
- TreeNode* temp = root;
- /// jeżeli lewy potomek, lub prawy jest jest naszym childem, to zwracamy ten wskaźnik
- while (temp)
- {
- if (temp->left == child || temp->right == child)
- return temp;
- if (child->key < temp->key)
- temp = temp->left;
- else
- temp = temp->right;
- }
- return NULL; // to się wykona, jeżeli nie znajdziemy rodzica, czyli roota
- }
- TreeNode* Tree::findSuccessor(TreeNode* target)
- {
- if (!root)
- return NULL;
- // żeby znaleźć następnika, trzeba iść na prawo, potem do oporu w lewo
- TreeNode* temp = target->right;
- while (temp->left)
- temp = temp->left;
- return temp;
- }
- void Tree::deleteNode(int key)
- {
- if (!root)
- {
- cout << "Drzewo jest puste" << endl;
- return;
- }
- // szukamy węzła docelowego oraz jego rodzica
- TreeNode* temp = search(key);
- TreeNode* parent = findParent(temp);
- // jeżeli parent jest nullem, to znaczy, że musimy usunąć roota
- if (!parent)
- {
- // jeżeli root nie ma potomków, to po prostu kasujemy roota i wyjebane
- if (!root->left && !root->right)
- {
- delete root;
- root = NULL;
- return;
- }
- // jeżeli root ma tylko lewego potomka, to kasujemy roota i podciągamy jego lewego potomka na miejsce roota
- if (root->left && !root->right)
- {
- TreeNode* left = root->left;
- delete root;
- root = left;
- return;
- }
- // analogicznie, jeżeli root ma tylko prawego potomka
- if (!root->left && root->right)
- {
- TreeNode* right = root->right;
- delete root;
- root = right;
- return;
- }
- // pobieramy sobie następnika i rodzica następnika
- TreeNode* successor = findSuccessor(root);
- TreeNode* parentSuccessor = findParent(successor);
- // jeżeli rodzic następnika jest rootem, to znaczy, że wystarczy tylko wstawić następnika na miejsce roota i podpiąć lewe poddrzewo roota do lewego wskaźnika successora
- if (parentSuccessor == root)
- {
- TreeNode* rootLeft = successor->left;
- delete root;
- root = successor;
- root->left = rootLeft;
- }
- else // w przeciwnym wypadku pod następnika podpinamy lewe i prawe poddrzewo roota, a prawe podrzewo nastepnika podpinamy pod lewy wskaźnik rodzica następnika
- {
- TreeNode* successorRight = successor->right;
- successor->left = root->left;
- successor->right = root->right;
- delete root;
- root = successor;
- parentSuccessor->left = successorRight;
- }
- return;
- }
- // w przypadku innego węzła, niż roota, musimy też następnik podpiąć pod lewe lub prawe poddrzewo rodzica usuwanego węzła w zależności od sytuacji. Reszta jest taka sama
- if (!temp->left && !temp->right)
- {
- // tutaj następuje sprawdzenie
- if (parent->left == temp)
- parent->left = NULL;
- else
- parent->right = NULL;
- delete temp;
- return;
- }
- if (temp->left && !temp->right)
- {
- TreeNode* child;
- child = temp->left;
- delete temp;
- if (parent->left == temp)
- parent->left = child;
- else
- parent->right = child;
- return;
- }
- if (!temp->left && temp->right)
- {
- TreeNode* child;
- child = temp->right;
- delete temp;
- if (parent->left == temp)
- parent->left = child;
- else
- parent->right = child;
- return;
- }
- TreeNode* successor = findSuccessor(temp);
- TreeNode* parentSuccessor = findParent(successor);
- if (parentSuccessor == temp)
- {
- successor->left = temp->left;
- if (parent->left == temp)
- parent->left = successor;
- else
- parent->right = successor;
- }
- else
- {
- TreeNode* successorRight = successor->right;
- successor->left = temp->left;
- successor->right = temp->right;
- parentSuccessor->left = successorRight;
- if (parent->left == temp)
- parent->left = successor;
- else
- parent->right = successor;
- }
- delete temp;
- }
- void Tree::preOrder(TreeNode* node)
- {
- if (node)
- {
- count++;
- cout << node->key << endl;
- preOrder(node->left);
- preOrder(node->right);
- }
- }
- void Tree::inOrder(TreeNode* node)
- {
- if (node)
- {
- inOrder(node->left);
- count++;
- cout << node->key << endl;
- inOrder(node->right);
- }
- }
- void Tree::postOrder(TreeNode* node)
- {
- if (node)
- {
- postOrder(node->left);
- postOrder(node->right);
- count++;
- cout << node->key << endl;
- }
- }
- void Tree::printPreOrder()
- {
- preOrder(root);
- cout << endl << "Total elements: " << count << endl;
- count = 0;
- }
- void Tree::printInOrder()
- {
- inOrder(root);
- cout << endl << "Total elements: " << count << endl;
- count = 0;
- }
- void Tree::printPostOrder()
- {
- postOrder(root);
- cout << endl << "Total elements: " << count << endl;
- count = 0;
- }
- void Tree::clearTree()
- {
- while (root)
- deleteNode(root->key);
- }
- Tree::~Tree()
- {
- clearTree();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement