Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- q// wezel ktory nie ma rodzica jest korzeniem
- // wezel ktory nie ma dziecka jest liściem
- // dzielimy drzewo na poziomy
- // preorder (root, left, right)
- // inorder (left, root, right)
- // postorder (left, right, root)
- #include <iostream>
- #include <fstream>
- #include <cstdlib>
- #include <string>
- using namespace std;
- class node // sam w sobie węzeł
- {
- public:
- int value;
- node* left;
- node* right;
- node();
- };
- node::node()
- {
- value = 0;
- left = nullptr;
- right = nullptr;
- }
- class binaryTree // klasa obsługująca funkcje drzewa
- {
- private:
- node* root;
- void inOrderPrint(node* element);
- void postOrderPrint(node* element);
- void preOrderPrint(node* element);
- void destroyTree(node* element);
- void insert(int key, node* element);
- public:
- binaryTree();
- ~binaryTree();
- void readDataOfADataFromFile();
- void insert(int key); // dodanie elementu do drzewa
- void destroyTree(); // kasowanie drzewa
- void inOrderPrint();
- void postOrderPrint();
- void preOrderPrint();
- };
- binaryTree::binaryTree() // na samym początku drzewo będzie puste więc root będzie nullptr
- {
- root = nullptr;
- }
- binaryTree::~binaryTree() // podczas uruchomienia destruktora kasowana jest cała zawartość sterty (czyli tam gdzie są węzły drzewa)
- {
- destroyTree();
- cout << "Usuwanie drzewa..." << endl;
- }
- void binaryTree::destroyTree()
- {
- destroyTree(root);
- }
- void binaryTree::destroyTree(node* element)
- {
- if (element != nullptr)
- {
- destroyTree(element->left);
- destroyTree(element->right);
- delete element;
- }
- }
- void binaryTree::insert(int key, node* element)
- {
- if (key < element->value) // elementy mniejsze lądują na lewej stronie, a większą bądź równe na prawej
- {
- if (element->left != nullptr) // jeżeli mamy wartość mniejszą i chcemy ją zapisać jako nowy węzeł
- { // ale okaże się, że wskaźnik do następnego elementu istnieje i ma wartość to musimy jeszcze raz wywołać funkcje rekursywnie aby przejść do następnego elementu i od niego stworzyć nowy węzeł
- insert(key, element->left); // tutaj rekursywne przejście do następnego elementu drzewa
- }
- else
- {
- element->left = new node(); // tworzymy nowy węzeł
- element->left->value = key;
- element->left->left = nullptr;
- element->left->right = nullptr;
- }
- }
- else if (key >= element->value) // analogicznie jak dla if(key < element>value)
- {
- if (element->right != nullptr)
- {
- insert(key, element->right);
- }
- else
- {
- element->right = new node();
- element->right->value = key;
- element->right->right = nullptr;
- element->right->left = nullptr;
- }
- }
- }
- void binaryTree::insert(int key) // funkcja do ogarnięcia czy drzewo jest puste czy nie
- {
- if (root != nullptr)
- {
- insert(key, root); // jeżeli nie jest pusta to lecimy z prywatną metodą insert(int key, node* element), która leci po całym drzewie szukając odpowiedniego węzła do stworzenia drzewa
- }
- else // jeżeli drzewo jest puste to tworzymy pierwszy węzeł drzewa (korzeń)
- {
- root = new node();
- root->value = key;
- root->left = nullptr;
- root->right = nullptr;
- }
- }
- void binaryTree::inOrderPrint(node* element) // (left, root, right)
- {
- if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
- {
- return;
- }
- inOrderPrint(element->left);
- cout << element->value << endl;
- inOrderPrint(element->right);
- }
- void binaryTree::inOrderPrint() // (left, root, right)
- {
- inOrderPrint(root);
- cout << endl;
- }
- void binaryTree::postOrderPrint(node* element) // (left, right, root)
- {
- if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
- {
- return;
- }
- postOrderPrint(element->left);
- postOrderPrint(element->right);
- cout << element->value << endl;
- }
- void binaryTree::postOrderPrint() // (left, right, root)
- {
- postOrderPrint(root);
- cout << endl;
- }
- void binaryTree::preOrderPrint(node* element) // (root, left, right)
- {
- if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
- {
- return;
- }
- cout << element->value << endl;
- preOrderPrint(element->left);
- preOrderPrint(element->right);
- }
- void binaryTree::preOrderPrint() // (root, left, right)
- {
- preOrderPrint(root);
- cout << endl;
- }
- void binaryTree::readDataOfADataFromFile()
- {
- string line;
- int number;
- fstream plik;
- plik.open("lista.txt", ios::in); // powiązanie strumienia z plikiem
- if (plik.good() == false) // jezeli jest zamkniety to error
- {
- cout << "Plik nie istnieje" << endl;
- exit(EXIT_FAILURE);
- }
- else // jezeli nie lecimy
- {
- while (!plik.eof()) // działa dopóty, dopóki coś sie nie "zepsuje"
- {
- getline(plik, line, ' ');
- number = atoi(line.c_str());
- insert(number); // funkcja zrobi z tego co wczytalismy liste
- }
- }
- plik.close(); // zamykanie
- }
- int main()
- {
- binaryTree* tree = new binaryTree();
- tree->readDataOfADataFromFile();
- tree->preOrderPrint(); // (root, left, right), 15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20 (ok, dobrze działa) (poza zerem)
- //tree->inOrderPrint(); // (left, root, right), 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 (ok, dobrze działa) (poza zerem)
- //tree->postOrderPrint(); // (left, right, root), 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15 (ok, dobrze działa) (poza zerem)
- delete tree; // trzeba to jawnie zainicjować ponieważ wtedy wywoła się domyślny destruktor bez ciała
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement