API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 26th, 2018
72
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.58 KB | None | 0 0
raw download clone embed print report
  1. #include<iostream>
  2. #include<fstream>
  3. #include <string>
  4. using namespace std;
  5. int poziom = 0;
  6. string cr, cl, cp;
  7. struct AVLnode
  8. {
  9.     AVLnode *left;
  10.     AVLnode *right;
  11.     AVLnode *parent;
  12.     int key;
  13.     int bf;
  14. };
  15. void printBT(string sp, string sn, AVLnode * v)
  16. {
  17.     string s;
  18.  
  19.     if (v)
  20.     {
  21.         s = sp;
  22.         if (sn == cr) s[s.length() - 2] = ' ';
  23.         printBT(s + cp, cr, v->right);
  24.  
  25.         s = s.substr(0, sp.length() - 2);
  26.         cout << s << sn << v->key <<v->bf<< endl;
  27.  
  28.         s = sp;
  29.         if (sn == cl) s[s.length() - 2] = ' ';
  30.         printBT(s + cp, cl, v->left);
  31.     }
  32. }
  33.  
  34.  
  35. void save(AVLnode *root)
  36. {
  37.  
  38.     fstream fout;
  39.     fout.open("Drzewo.txt", ios::out | ios::app);
  40.  
  41.     if (root->left)
  42.         save(root->left);
  43.     fout << root->key << " "<<root->parent->key;
  44.     if (root->right)
  45.         save(root->right);
  46.     fout << endl;
  47.     fout.close();
  48.  
  49.  
  50.  
  51. }
  52.  
  53. void printf(AVLnode *root)
  54. {
  55.     if (root->left)
  56.         printf(root->left);
  57.     cout << root->key << " o adresie: " << root << " i o rodzicu " << root->parent<<endl;
  58.     if (root->right)
  59.         printf(root->right);
  60. }
  61.  
  62.  
  63.  
  64.  
  65. void addnode(AVLnode **root, int data)
  66. {
  67.     int x=1;
  68.     AVLnode *temp = (*root);
  69.     AVLnode *temp2 = NULL;
  70.     if (*root == NULL)
  71.     {
  72.         (*root) = new AVLnode;
  73.         (*root)->key = data;
  74.         (*root)->left = NULL;
  75.         (*root)->right = NULL;
  76.         (*root)->parent = NULL;
  77.         (*root)->bf = 0;
  78.     }
  79.     else
  80.     {
  81.         while(temp)
  82.         {
  83.             if (data > temp->key)
  84.             {
  85.                 temp2 = temp;
  86.                 temp = temp->right;
  87.             }
  88.             else if (data < temp->key)
  89.             {
  90.                 temp2 = temp;
  91.                 temp = temp->left;
  92.             }
  93.             else {
  94.                 cout << "Taka liczba juz jest";
  95.                 x = 0;
  96.                 break;
  97.             }
  98.         }
  99.         if (x)
  100.         {
  101.             AVLnode *a = new AVLnode;
  102.             a->key = data;
  103.             a->left = NULL;
  104.             a->right = NULL;
  105.             a->parent = temp2;
  106.             a->bf = 0;
  107.             if (temp2->key > data)
  108.                 temp2->left = a;
  109.             else
  110.                 temp2->right = a;
  111.         }
  112.     }
  113. }
  114.  
  115.  
  116.  
  117. void addtxt(AVLnode **root)
  118. {
  119.     int a;
  120.     ifstream fin;
  121.     fin.open("temp.txt");
  122.     while (!fin.eof())
  123.     {
  124.         fin >> a;
  125.         addnode(root, a);
  126.     }
  127.  
  128. }
  129.  
  130. void min(AVLnode **root)
  131. {
  132.     AVLnode *temp = (*root);
  133.     while (temp->left)
  134.         temp = temp->left;
  135.     cout << "Minimalna to: " << temp->key << endl;
  136. }
  137. void max(AVLnode **root)
  138. {
  139.     AVLnode *temp = (*root);
  140.     while (temp->right)
  141.         temp = temp->right;
  142.     cout << "Maksymalna to: " << temp->key << endl;
  143. }
  144.  
  145. AVLnode *search(AVLnode *root, int data)
  146. {
  147.     while (root)
  148.     {
  149.         if (root->key>data)
  150.             root = root->left;
  151.         if (root->key<data)
  152.             root = root->right;
  153.         if (root->key == data)
  154.             return root;
  155.     }
  156.     return 0;
  157.  
  158. }
  159.  
  160. void LL(AVLnode **root, AVLnode *a)
  161. {
  162.     AVLnode *b=a->left;
  163.     AVLnode *p = a->parent;
  164.     if (a == *root)
  165.         *root = b;
  166.     if (b)
  167.         a->left = b->right;
  168.     else
  169.         a->left = NULL;
  170.     if (a->left)
  171.     {
  172.         a->left->parent = a;
  173.     }
  174.     if (b)
  175.     {
  176.         b->right = a;
  177.         b->parent = p;
  178.     }
  179.     a->parent = b;
  180.     if (p == NULL)
  181.         (*root) = b;
  182.     if (p->left == a)
  183.         p->left = b;
  184.     else
  185.         p->right = b;
  186.     if (b)
  187.     {
  188.         if (b->bf == 1) {
  189.             a->bf = 0;
  190.             b->bf = 0;
  191.         }
  192.         else
  193.         {
  194.             a->bf = 0;
  195.             b->bf = -1;
  196.         }
  197.         if (a->parent->parent)
  198.             a->parent->parent->bf = a->parent->parent->bf - 1;
  199.     }
  200.  
  201. }
  202. void RL(AVLnode **root, AVLnode *a)
  203. {
  204.     AVLnode *b = a->right;
  205.     AVLnode *p = a->parent;
  206.     AVLnode *c = b->left;
  207.     if (a == *root)
  208.         *root = b;
  209.     if (b)
  210.         b->left = c->right;
  211.     else
  212.         b->right = NULL;
  213.     if (b->left)
  214.     {
  215.         b->left->parent = b;
  216.     }
  217.     if(c)
  218.     a->right = c->left;
  219.     if (a->right)
  220.     {
  221.         a->right->parent = a;
  222.     }
  223.     c->left = a;
  224.     c->right = b;
  225.     a->parent = c;
  226.     b->parent = c;
  227.     c->parent = p;
  228.     if (p == NULL)
  229.         (*root) = c;
  230.     if (p->left == a)
  231.         p->left = c;
  232.     else
  233.         p->right = c;
  234.     if (c)
  235.     {
  236.         if (c->bf == -1) {
  237.             a->bf = 1;
  238.         }
  239.         else
  240.         {
  241.             a->bf = 0;
  242.         }
  243.         if (c->bf == 1) {
  244.             b->bf = -1;
  245.         }
  246.         else
  247.         {
  248.             b->bf = 0;
  249.         }
  250.         if (a->parent->parent)
  251.             a->parent->parent->bf = a->parent->parent->bf + 1;
  252.     }
  253.  
  254. }
  255. void LR(AVLnode **root, AVLnode *a)
  256. {
  257.     AVLnode *b = a->left;
  258.     AVLnode *p = a->parent;
  259.     AVLnode *c = b->right;
  260.     if (a == *root)
  261.         *root = b;
  262.     if (b)
  263.         b->right = c->left;
  264.     else
  265.         b->right = NULL;
  266.     if (b->right)
  267.     {
  268.         b->right->parent = b;
  269.     }
  270.     if (c)
  271.         a->left = c->right;
  272.     if (a->left)
  273.     {
  274.         a->left->parent = a;
  275.     }
  276.     c->right = a;
  277.     c->left = b;
  278.     a->parent = c;
  279.     b->parent = c;
  280.     c->parent = p;
  281.     if (p == NULL)
  282.         (*root) = c;
  283.     if (p->left == a)
  284.         p->left = c;
  285.     else
  286.         p->right = c;
  287.     if (c)
  288.     {
  289.         if (c->bf == 1) {
  290.             a->bf = -1;
  291.         }
  292.         else
  293.         {
  294.             a->bf = 0;
  295.         }
  296.         if (c->bf == -1) {
  297.             b->bf = -1;
  298.         }
  299.         else
  300.         {
  301.             b->bf = 0;
  302.         }
  303.         if (a->parent->parent)
  304.             a->parent->parent->bf = a->parent->parent->bf - 1;
  305.     }
  306.  
  307. }
  308.  
  309. void RR(AVLnode **root, AVLnode *a)
  310. {
  311.     AVLnode *b = a->right;
  312.     AVLnode *p = a->parent;
  313.     if (a == *root)
  314.         *root = b;
  315.     if (b)
  316.         a->right = b->left;
  317.     else
  318.         a->right = NULL;
  319.     if (a->right)
  320.     {
  321.         a->right->parent = a;
  322.     }
  323.     if (b)
  324.     {
  325.         b->left = a;
  326.         b->parent = p;
  327.     }
  328.     a->parent = b;
  329.     if (p == NULL)
  330.         (*root) = b;
  331.     if (p->left == a)
  332.         p->left = b;
  333.     else
  334.         p->right = b;
  335.     if (b)
  336.     {
  337.         if (b->bf == -1) {
  338.             a->bf = 0;
  339.             b->bf = 0;
  340.         }
  341.         else
  342.         {
  343.             a->bf = -1;
  344.             b->bf = 1;
  345.         }
  346.         if (a->parent->parent)
  347.             a->parent->parent->bf = a->parent->parent->bf + 1;
  348.     }
  349.  
  350. }
  351. void bf(AVLnode *root, AVLnode *temp)
  352. {
  353.    
  354.     while (temp->parent)
  355.     {
  356.         AVLnode *temp2 = temp->parent;
  357.         if (temp->parent->left == temp)
  358.         {
  359.             if (temp->parent->right == NULL)
  360.             {
  361.                 temp->parent->bf = (temp->parent->bf)+1;
  362.                
  363.             }
  364.             else
  365.                 while (temp2->parent)
  366.                 {
  367.                     temp2->bf = temp2->bf + 1;
  368.                     temp2 = temp2->parent;
  369.                 }
  370.  
  371.         }
  372.         else
  373.         {
  374.             if (temp->parent->left == NULL)
  375.             {
  376.                 temp->parent->bf = (temp->parent->bf)-1;
  377.                
  378.             }
  379.             else
  380.                 while (temp2->parent)
  381.                 {
  382.                     temp2->bf = temp2->bf - 1;
  383.                     temp2 = temp2->parent;
  384.                 }
  385.         }
  386.         temp = temp->parent;
  387.     }
  388. }
  389. void addAVL(AVLnode **root, int data)
  390. {
  391.     addnode(root, data);
  392.     AVLnode *temp = search(*root, data);
  393.     bf(*root, temp);
  394.     if(temp->parent)
  395.     while (temp->parent)
  396.     {
  397.  
  398.         AVLnode *temp2 = temp;
  399.         if (temp->parent->parent)
  400.         {
  401.             if (temp->bf == 0 && temp->parent->bf == 1 && temp->parent->parent->bf == 2) {
  402.                 LL(root, temp2->parent->parent);
  403.             }
  404.             if (temp->bf == 0 && temp->parent->bf == -1 && temp->parent->parent->bf == -2)
  405.                 RR(root, temp->parent->parent);
  406.             if (temp->bf == 0 && temp->parent->bf == 1 && temp->parent->parent->bf == -2)
  407.                 RL(root, temp->parent->parent);
  408.             if (temp->bf == 0 && temp->parent->bf == -1 && temp->parent->parent->bf == 2)
  409.                 LR(root, temp->parent->parent);
  410.         }
  411.         temp = temp->parent;
  412.  
  413.     }
  414.    
  415. }
  416.  
  417.  
  418. int main()
  419. {
  420.     int pyt = 1, nr;
  421.     AVLnode * root = NULL;
  422.     root = NULL;
  423.     cr = cl = cp = "  ";
  424.     cr[0] = 218; cr[1] = 196;
  425.     cl[0] = 192; cl[1] = 196;
  426.     cp[0] = 179;
  427.     while (pyt != 0)
  428.     {
  429.         cout << "1. Dodaj element do drzewa" << endl;
  430.         cout << "2. Wyswietl w pliku" << endl;
  431.         cout << "3. Wyszukaj min" << endl;
  432.         cout << "4. Wyszukaj mix" << endl;
  433.         cout << "5. Wyszukaj czegos" << endl;
  434.         cout << "6. Dodaj wartosci z pliku" << endl;
  435.         cin >> pyt;
  436.         switch (pyt) {
  437.         case 1:
  438.             cout << "Podaj liczbe:" << endl;
  439.             cin >> nr;
  440.             addnode(&root, nr);
  441.             break;
  442.         case 2:
  443.             save(root);
  444.             break;
  445.         case 3:
  446.             min(&root);
  447.             break;
  448.         case 4:
  449.             max(&root);
  450.             break;
  451.         case 5:
  452.             cout << "Co chcesz znalezc: ";
  453.             cin >> nr;
  454.             cout << "Szukane to: " << search(root, nr) << endl;
  455.             break;
  456.         case 6:
  457.             addtxt(&root);
  458.             break;
  459.         case 7:
  460.             cout << "Podaj liczbe:" << endl;
  461.             cin >> nr;
  462.             addAVL(&root, nr);
  463.                 break;
  464.         case 0:
  465.             break;
  466.         default:
  467.             cout << "Zly nr" << endl;
  468.             break;
  469.         }
  470.         printBT("", "", root);
  471.         cout << endl;
  472.     }
  473.     system("pause");
  474.     return 0;
  475. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!