SHARE
TWEET

BST

matogens Nov 14th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. q// wezel ktory nie ma rodzica jest korzeniem
  2. // wezel ktory nie ma dziecka jest liściem
  3. // dzielimy drzewo na poziomy
  4.  
  5. // preorder (root, left, right)
  6. // inorder (left, root, right)
  7. // postorder (left, right, root)
  8.  
  9. #include <iostream>
  10. #include <fstream>
  11. #include <cstdlib>
  12. #include <string>
  13. using namespace std;
  14.  
  15. class node // sam w sobie węzeł
  16. {
  17. public:
  18.  
  19.     int value;
  20.     node* left;
  21.     node* right;
  22.  
  23.     node();
  24. };
  25.  
  26. node::node()
  27. {
  28.     value = 0;
  29.     left = nullptr;
  30.     right = nullptr;
  31. }
  32.  
  33. class binaryTree // klasa obsługująca funkcje drzewa
  34. {
  35. private:
  36.  
  37.     node* root;
  38.  
  39.     void inOrderPrint(node* element);
  40.     void postOrderPrint(node* element);
  41.     void preOrderPrint(node* element);
  42.     void destroyTree(node* element);
  43.     void insert(int key, node* element);
  44.    
  45.  
  46. public:
  47.  
  48.     binaryTree();
  49.     ~binaryTree();
  50.  
  51.     void readDataOfADataFromFile();
  52.     void insert(int key); // dodanie elementu do drzewa
  53.     void destroyTree(); // kasowanie drzewa
  54.     void inOrderPrint();
  55.     void postOrderPrint();
  56.     void preOrderPrint();
  57. };
  58.  
  59.  
  60.  
  61. binaryTree::binaryTree() // na samym początku drzewo będzie puste więc root będzie nullptr
  62. {
  63.     root = nullptr;
  64. }
  65.  
  66. binaryTree::~binaryTree() // podczas uruchomienia destruktora kasowana jest cała zawartość sterty (czyli tam gdzie są węzły drzewa)
  67. {
  68.     destroyTree();
  69.     cout << "Usuwanie drzewa..." << endl;
  70. }
  71.  
  72.  
  73. void binaryTree::destroyTree()
  74. {
  75.     destroyTree(root);
  76. }
  77.  
  78. void binaryTree::destroyTree(node* element)
  79. {
  80.     if (element != nullptr)
  81.     {
  82.         destroyTree(element->left);
  83.         destroyTree(element->right);
  84.         delete element;
  85.     }
  86. }
  87.  
  88. void binaryTree::insert(int key, node* element)
  89. {
  90.     if (key < element->value) // elementy mniejsze lądują na lewej stronie, a większą bądź równe na prawej
  91.     {
  92.         if (element->left != nullptr) // jeżeli mamy wartość mniejszą i chcemy ją zapisać jako nowy węzeł
  93.         {                             // 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ł
  94.             insert(key, element->left); // tutaj rekursywne przejście do następnego elementu drzewa
  95.         }
  96.         else
  97.         {
  98.             element->left = new node(); // tworzymy nowy węzeł
  99.             element->left->value = key;
  100.             element->left->left = nullptr;
  101.             element->left->right = nullptr;
  102.         }
  103.     }
  104.     else if (key >= element->value) // analogicznie jak dla if(key < element>value)
  105.     {
  106.         if (element->right != nullptr)
  107.         {
  108.             insert(key, element->right);           
  109.         }
  110.         else
  111.         {
  112.             element->right = new node();
  113.             element->right->value = key;
  114.             element->right->right = nullptr;
  115.             element->right->left = nullptr;
  116.         }
  117.     }
  118. }
  119.  
  120. void binaryTree::insert(int key) // funkcja do ogarnięcia czy drzewo jest puste czy nie
  121. {
  122.     if (root != nullptr)
  123.     {
  124.         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
  125.     }
  126.     else // jeżeli drzewo jest puste to tworzymy pierwszy węzeł drzewa (korzeń)
  127.     {
  128.         root = new node();
  129.         root->value = key;
  130.         root->left = nullptr;
  131.         root->right = nullptr;
  132.     }
  133. }
  134.  
  135. void binaryTree::inOrderPrint(node* element) // (left, root, right)
  136. {
  137.  
  138.     if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
  139.     {
  140.         return;
  141.     }
  142.     inOrderPrint(element->left);
  143.     cout << element->value << endl;
  144.     inOrderPrint(element->right);
  145. }
  146.  
  147. void binaryTree::inOrderPrint() // (left, root, right)
  148. {
  149.     inOrderPrint(root);
  150.     cout << endl;
  151. }
  152.  
  153.  
  154. void binaryTree::postOrderPrint(node* element) // (left, right, root)
  155. {
  156.     if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
  157.     {
  158.         return;
  159.     }
  160.     postOrderPrint(element->left);
  161.     postOrderPrint(element->right);
  162.     cout << element->value << endl;
  163.  
  164.  
  165. }
  166.  
  167. void binaryTree::postOrderPrint() // (left, right, root)
  168. {
  169.     postOrderPrint(root);
  170.     cout << endl;
  171. }
  172.  
  173. void binaryTree::preOrderPrint(node* element) // (root, left, right)
  174. {
  175.     if (element == nullptr) // jeżeli drzewo jest puste, przy okazji warunek wyjścia z rekursji
  176.     {
  177.         return;
  178.     }
  179.     cout << element->value << endl;
  180.     preOrderPrint(element->left);
  181.     preOrderPrint(element->right);
  182. }
  183.  
  184. void binaryTree::preOrderPrint() // (root, left, right)
  185. {
  186.     preOrderPrint(root);
  187.     cout << endl;
  188. }
  189.  
  190. void binaryTree::readDataOfADataFromFile()
  191. {
  192.     string line;
  193.     int number;
  194.     fstream plik;
  195.  
  196.     plik.open("lista.txt", ios::in); // powiązanie strumienia z plikiem
  197.  
  198.     if (plik.good() == false) // jezeli jest zamkniety to error
  199.     {
  200.         cout << "Plik nie istnieje" << endl;
  201.         exit(EXIT_FAILURE);
  202.     }
  203.     else // jezeli nie lecimy
  204.     {
  205.         while (!plik.eof()) // działa dopóty, dopóki coś sie nie "zepsuje"
  206.         {
  207.             getline(plik, line, ' ');
  208.             number = atoi(line.c_str());
  209.  
  210.             insert(number); // funkcja zrobi z tego co wczytalismy liste
  211.         }
  212.     }
  213.     plik.close(); // zamykanie
  214. }
  215.  
  216.  
  217. int main()
  218. {  
  219.     binaryTree* tree = new binaryTree();
  220.  
  221.     tree->readDataOfADataFromFile();
  222.  
  223.     tree->preOrderPrint(); // (root, left, right), 15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20 (ok, dobrze działa) (poza zerem)
  224.     //tree->inOrderPrint(); // (left, root, right), 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 (ok, dobrze działa) (poza zerem)
  225.     //tree->postOrderPrint(); // (left, right, root), 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15 (ok, dobrze działa) (poza zerem)
  226.  
  227.     delete tree; // trzeba to jawnie zainicjować ponieważ wtedy wywoła się domyślny destruktor bez ciała
  228.  
  229.  
  230.     return 0;
  231. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top