SHARE
TWEET

Untitled

a guest Jan 21st, 2020 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <fstream>
  4. using namespace std;
  5.  
  6. class Node
  7. {
  8. public:
  9. string pol;
  10. string eng;
  11. Node *left;
  12. Node *right;
  13. int height;
  14. };
  15.  
  16.  
  17. Node* newNode(string pol_,string eng_)
  18. {
  19.         Node* node = new Node();
  20.         node->pol = pol_;
  21.         node->eng = eng_;
  22.         node->left = NULL;
  23.         node->right = NULL;
  24.         node->height = 1; //lisc
  25.  
  26.         return(node);
  27. }
  28. int height(Node *N)
  29. {
  30.         if (N == NULL)
  31.                 return 0;
  32.         return N->height;
  33. }
  34. Node *rotacjaPrawo(Node *y)
  35. {
  36.         Node *x = y->left;
  37.         Node *T2 = x->right;
  38.  
  39.         // Perform rotation
  40.         x->right = y;
  41.         y->left = T2;
  42.  
  43.         // Update heights
  44.         y->height = max(height(y->left),
  45.                         height(y->right)) + 1;
  46.         x->height = max(height(x->left),
  47.                         height(x->right)) + 1;
  48.  
  49.         // Return new root
  50.         return x;
  51. }
  52. Node *rotacjaLewo(Node *x)
  53. {
  54.         Node *y = x->right;
  55.         Node *T2 = y->left;
  56.  
  57.         // Perform rotation
  58.         y->left = x;
  59.         x->right = T2;
  60.  
  61.         // Update heights
  62.         x->height = max(height(x->left),
  63.                         height(x->right)) + 1;
  64.         y->height = max(height(y->left),
  65.                         height(y->right)) + 1;
  66.  
  67.         // Return new root
  68.         return y;
  69. }
  70. int getBalance(Node *N)
  71. {
  72.         if (N == NULL)
  73.                 return 0;
  74.         return height(N->left) -
  75.                height(N->right);
  76. }
  77. Node* dodajNode(Node* node, string pol,string eng)
  78. {
  79.         /* 1. Perform the normal BST rotation */
  80.         if (node == NULL)
  81.                 return(newNode(pol,eng));
  82.  
  83.         if (pol < node->pol)
  84.                 node->left = dodajNode(node->left, pol,eng);
  85.         else if (pol > node->pol)
  86.                 node->right = dodajNode(node->right, pol,eng);
  87.         else // Equal pols not allowed
  88.                 return node;
  89.  
  90.         /* 2. Update height of this ancestor node */
  91.         node->height = 1 + max(height(node->left),
  92.                                height(node->right));
  93.  
  94.         /* 3. Get the balance factor of this
  95.            ancestor node to check whether
  96.            this node became unbalanced */
  97.         int balance = getBalance(node);
  98.  
  99.         // If this node becomes unbalanced,
  100.         // then there are 4 cases
  101.  
  102.         // Left Left Case
  103.         if (balance > 1 && pol < node->left->pol)
  104.                 return rotacjaPrawo(node);
  105.  
  106.         // Right Right Case
  107.         if (balance < -1 && pol > node->right->pol)
  108.                 return rotacjaLewo(node);
  109.  
  110.         // Left Right Case
  111.         if (balance > 1 && pol > node->left->pol)
  112.         {
  113.                 node->left = rotacjaLewo(node->left);
  114.                 return rotacjaPrawo(node);
  115.         }
  116.  
  117.         // Right Left Case
  118.         if (balance < -1 && pol < node->right->pol)
  119.         {
  120.                 node->right = rotacjaPrawo(node->right);
  121.                 return rotacjaLewo(node);
  122.         }
  123.  
  124.         /* return the (unchanged) node pointer */
  125.         return node;
  126. }
  127. void przejKlp(Node *root)
  128. {
  129.         if(root != NULL)
  130.         {
  131.                 cout << root->pol << " " << root->eng << " ";
  132.                 przejKlp(root->left);
  133.                 przejKlp(root->right);
  134.         }
  135. }
  136.  
  137.  
  138. Node * minWartoscNode(Node* node)
  139. {
  140.         Node* current = node;
  141.  
  142.  
  143.         while (current->left != NULL)
  144.                 current = current->left;
  145.  
  146.         return current;
  147. }
  148. Node * maxWartoscNode(Node* node)
  149. {
  150.         Node* current = node;
  151.  
  152.  
  153.         while (current->right != NULL)
  154.                 current = current->right;
  155.  
  156.         return current;
  157. }
  158.  
  159. Node* usuwanie(Node* root, string pol)
  160. {
  161.  
  162.         //zaczynam zwykle usuwanie bst
  163.         if (root == NULL)
  164.                 return root;
  165.  
  166.         // jesli polskie slowo ktore usuwam mniejsze od korzenia ide w lewo
  167.         if ( pol < root->pol )
  168.                 root->left = usuwanie(root->left, pol);
  169.  
  170.         // jesli polskie slowo ktore usuwam wieksze od korzenia ide w prawo
  171.  
  172.         else if( pol > root->pol )
  173.                 root->right = usuwanie(root->right, pol);
  174.  
  175.         // jesli takie samo jak korzen to wlasnie jego szukam
  176.         else
  177.         {
  178.                 // wezly z jednym synem lub zadnym
  179.                 if( (root->left == NULL) ||
  180.                     (root->right == NULL) )
  181.                 {
  182.                         Node *temp = root->left ?
  183.                                      root->left :
  184.                                      root->right;
  185.  
  186.                         // No child case
  187.                         if (temp == NULL)
  188.                         {
  189.                                 temp = root;
  190.                                 root = NULL;
  191.                         }
  192.                         else // przypadek gdy jeden syn
  193.                                 *root = *temp; // przechowanie zawartosci syna
  194.                         free(temp);
  195.                 }
  196.                 else
  197.                 {
  198.                         // wezel z dwoma synami , maxWartoscNode szukam najwieksego elementu lewego poddrezwa
  199.                         Node* temp = maxWartoscNode(root->left);
  200.  
  201.  
  202.                         root->pol = temp->pol;
  203.                         root->eng = temp->eng;
  204.  
  205.                         root->left = usuwanie(root->left,
  206.                                               temp->pol);
  207.                 }
  208.         }
  209.  
  210.         //drzewo mialo tylko jeden wezel
  211.         if (root == NULL)
  212.                 return root;
  213.  
  214.         // aktualizacja wysokosci obecnego wezla
  215.         root->height = 1 + max(height(root->left),
  216.                                height(root->right));
  217.  
  218.         // sprawdzanie bilansu wysokosci
  219.         int balance = getBalance(root);
  220.  
  221.         // rozwiazanie problemow gdy wezel nie jest zbliansowany
  222.  
  223.         // lewo lewo
  224.         if (balance > 1 &&
  225.             getBalance(root->left) >= 0)
  226.                 return rotacjaPrawo(root);
  227.  
  228.         // lewo prawo ( podwojna rotacja )
  229.         if (balance > 1 &&
  230.             getBalance(root->left) < 0)
  231.         {
  232.                 root->left = rotacjaLewo(root->left);
  233.                 return rotacjaPrawo(root);
  234.         }
  235.  
  236.         // prawo prawo
  237.         if (balance < -1 &&
  238.             getBalance(root->right) <= 0)
  239.                 return rotacjaLewo(root);
  240.  
  241.         // prawo lewo ( podwojna rotacja )
  242.         if (balance < -1 &&
  243.             getBalance(root->right) > 0)
  244.         {
  245.                 root->right = rotacjaPrawo(root->right);
  246.                 return rotacjaLewo(root);
  247.         }
  248.  
  249.         return root;
  250. }
  251.  
  252. // pomaga ustawiac wartosci alfabetycznie poprez porownywanie dwoch stringow
  253. string max(string a,string b){
  254.         if(a>b) return a;
  255.         else return b;
  256. }
  257.  
  258. // zapis do pliku
  259. void savetotxt(Node *root,fstream &plik){
  260.         if(root != NULL)
  261.         {
  262.                 plik << root->pol << " " << root->eng << " ";
  263.                 savetotxt(root->left,plik);
  264.                 savetotxt(root->right,plik);
  265.         }
  266. }
  267. // zapis do pliku
  268. void saveavl(Node *root)
  269. {
  270.         fstream plik;
  271.         plik.open("OUTAVL.txt",ios::out);
  272.         savetotxt(root,plik);
  273.  
  274.         plik.close();
  275. }
  276.  
  277. Node* wyszukiwanie(string pol, Node* node);
  278. int main(int argc, char const *argv[]) {
  279.         Node *root = NULL;
  280.  
  281.         // odczytanie danych z pliku
  282.         ifstream infile("INAVL.txt");
  283.         string a,b;
  284.         if(infile.fail())
  285.                 cout << "error" << endl;
  286.         while(!infile.eof()) {
  287.                 infile>>a>>b;
  288.                 root = dodajNode (root,a,b);
  289.         }
  290.         infile.close();
  291.  
  292.         cout<<endl;
  293.         cout << "Przejscie KLP\n";
  294.         przejKlp(root);
  295.         cout<<endl;
  296.  
  297.         root = usuwanie(root,"FSI");
  298.         cout<<endl;
  299.         cout << "Przejscie KLP\n";
  300.         przejKlp(root);
  301.         root = usuwanie(root,"COT");
  302.         cout << "Przejscie KLP\n";
  303.         przejKlp(root);
  304.         cout<<endl;
  305.         // wyszukiwanie słowa polskiego i jego tłumaczenia
  306.         wyszukiwanie("A",root);
  307.         // zapisz przejscie KLP do pliku
  308.         saveavl(root);
  309.         return 0;
  310. }
  311. Node* wyszukiwanie(string pol, Node* node) {
  312.         if(node == nullptr) return nullptr;
  313.  
  314.         if(pol < node->pol)  {
  315.                 node->left = wyszukiwanie(pol, node->left);
  316.         }
  317.         else if(pol > node->pol) {
  318.                 node->right = wyszukiwanie(pol, node->right);
  319.         }
  320.         else if(node->pol == pol)  {
  321.                 cout << node->pol << " " << node->eng << endl;
  322.         }
  323.         else {
  324.                 cout << "Takie słowo nie istnieje" << endl;
  325.         }
  326.         return node;
  327. }
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