SHARE
TWEET

Untitled

a guest May 22nd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <cstdlib>
  5. #include <fstream>
  6.  
  7.  
  8. using namespace std;
  9.  
  10. // Definicja typu węzłów drzewa AVL
  11. //---------------------------------
  12. struct AVLNode
  13. {
  14.   AVLNode * up, * left, * right;
  15.   int key, bf;
  16. };
  17.  
  18. // Zmienne globalne
  19. //-----------------
  20.  
  21. string cr,cl,cp;      // łańcuchy do znaków ramek
  22.  
  23. // Procedura wypisuje drzewo
  24. //--------------------------
  25. void printBT(string sp, string sn, AVLNode * v)
  26. {
  27.   string s;
  28.  
  29.   if(v)
  30.   {
  31.     s = sp;
  32.     if(sn == cr) s[s.length() - 2] = ' ';
  33.     printBT(s + cp, cr, v->right);
  34.  
  35.     s = s.substr(0,sp.length()-2);
  36.     cout << s << sn << v->key << ":" << v->bf << endl;
  37.  
  38.     s = sp;
  39.     if(sn == cl) s[s.length() - 2] = ' ';
  40.     printBT(s + cp, cl, v->left);
  41.   }
  42. }
  43.  
  44. // Procedura DFS:postorder usuwająca drzewo
  45. //-----------------------------------------
  46. void DFSRelease(AVLNode * v)
  47. {
  48.   if(v)
  49.   {
  50.     DFSRelease(v->left);   // usuwamy lewe poddrzewo
  51.     DFSRelease(v->right);  // usuwamy prawe poddrzewo
  52.     delete v;              // usuwamy sam węzeł
  53.   }
  54. }
  55.  
  56. // Rotacja RR
  57. //-----------
  58. void RR(AVLNode * & root, AVLNode * A)
  59. {
  60.   AVLNode * B = A->right, * p = A->up;
  61.  
  62.   A->right = B->left;
  63.   if(A->right) A->right->up = A;
  64.  
  65.   B->left = A;
  66.   B->up = p;
  67.   A->up = B;
  68.  
  69.   if(p)
  70.   {
  71.     if(p->left == A) p->left = B; else p->right = B;
  72.   }
  73.   else root = B;
  74.  
  75.   if(B->bf == -1) A->bf = B->bf = 0;
  76.   else
  77.   {
  78.     A->bf = -1; B->bf = 1;
  79.   }
  80. }
  81.  
  82. // Rotacja LL
  83. //-----------
  84. void LL(AVLNode * & root, AVLNode * A)
  85. {
  86.   AVLNode * B = A->left, * p = A->up;
  87.  
  88.   A->left = B->right;
  89.   if(A->left) A->left->up = A;
  90.  
  91.   B->right = A;
  92.   B->up = p;
  93.   A->up = B;
  94.  
  95.   if(p)
  96.   {
  97.     if(p->left == A) p->left = B; else p->right = B;
  98.   }
  99.   else root = B;
  100.  
  101.   if(B->bf == 1) A->bf = B->bf = 0;
  102.   else
  103.   {
  104.     A->bf = 1; B->bf = -1;
  105.   }
  106. }
  107.  
  108. // Rotacja RL
  109. //-----------
  110. void RL(AVLNode * & root, AVLNode * A)
  111. {
  112.   AVLNode * B = A->right, * C = B->left, * p  = A->up;
  113.  
  114.   B->left = C->right;
  115.   if(B->left) B->left->up = B;
  116.  
  117.   A->right = C->left;
  118.   if(A->right) A->right->up = A;
  119.  
  120.   C->left = A;
  121.   C->right = B;
  122.   A->up = B->up = C;
  123.   C->up = p;
  124.  
  125.   if(p)
  126.   {
  127.     if(p->left == A) p->left = C; else p->right = C;
  128.   }
  129.   else root = C;
  130.  
  131.   if(C->bf == -1) A->bf =  1; else A->bf = 0;
  132.   if(C->bf ==  1) B->bf = -1; else B->bf = 0;
  133.  
  134.   C->bf = 0;
  135. }
  136.  
  137. // Rotacja LR
  138. //-----------
  139. void LR(AVLNode * & root, AVLNode * A)
  140. {
  141.   AVLNode * B = A->left, * C = B->right, * p = A->up;
  142.  
  143.   B->right = C->left;
  144.   if(B->right) B->right->up = B;
  145.  
  146.   A->left = C->right;
  147.   if(A->left) A->left->up = A;
  148.  
  149.   C->right = A;
  150.   C->left = B;
  151.   A->up = B->up = C;
  152.   C->up = p;
  153.  
  154.   if(p)
  155.   {
  156.     if(p->left == A) p->left = C; else p->right = C;
  157.   }
  158.   else root = C;
  159.  
  160.   if(C->bf ==  1) A->bf = -1; else A->bf = 0;
  161.   if(C->bf == -1) B->bf =  1; else B->bf = 0;
  162.  
  163.   C->bf = 0;
  164. }
  165.  
  166. // Wstawia nowy węzeł do drzewa AVL
  167. // root - referencja korzenia
  168. // k    - klucz nowego węzła
  169. //---------------------------------
  170. void insertAVL(AVLNode * & root, int k)
  171. {
  172.   AVLNode * w,* p,* r;
  173.   bool t;
  174.  
  175.   w = new AVLNode;        // tworzymy dynamicznie nowy węzeł
  176.   w->left = w->right = w->up = NULL;
  177.   w->key  = k;
  178.   w->bf  = 0;
  179.  
  180.   //----------------------------------------
  181.   // FAZA 1 - wstawienie węzła do drzewa AVL
  182.   //----------------------------------------
  183.  
  184.   p = root;              // rozpoczynamy od korzenia
  185.  
  186.   if(!p) root = w;       // jeśli drzewo jest puste, to węzeł w umieszczamy w korzeniu
  187.   else
  188.   {                      // inaczej szukamy miejsce dla w
  189.     while(true)
  190.       if(k < p->key)     // porównujemy klucze
  191.       {
  192.         if(!p->left)     // jeśli p nie posiada lewego syna, to
  193.         {
  194.           p->left = w;   // lewym synem p staje się węzeł w
  195.           break;         // wychodzimy z pętli
  196.         }
  197.         p = p->left;     // inaczej przechodzimy do lewego syna
  198.       }
  199.       else
  200.       {
  201.         if(!p->right)    // jeśli p nie posiada prawego syna, to
  202.         {
  203.           p->right = w;  // prawym synem staje się węzeł w
  204.           break;         // wychodzimy z pętli
  205.         }
  206.         p = p->right;    // inaczej przechodzimy do prawego syna
  207.       }
  208.  
  209.     w->up = p;           // ojcem w jest p
  210.  
  211.     //---------------------------------
  212.     // FAZA 2 - równoważenie drzewa AVL
  213.     //---------------------------------
  214.  
  215.     if(p->bf) p->bf = 0; // UWAGA NR 1
  216.     else
  217.     {
  218.       if(p->left == w)   // UWAGA NR 2
  219.         p->bf = 1;
  220.       else
  221.         p->bf = -1;
  222.  
  223.       r = p->up;        // będziemy szli w górę drzewa w kierunku korzenia
  224.                         // r i p wskazują ojca i syna na tej ścieżce
  225.       t = false;
  226.       while(r)
  227.       {
  228.         if(r->bf)
  229.         {
  230.           t = true;     // ustalamy wynik pętli
  231.           break;        // przerywamy pętlę
  232.         };
  233.                         // inaczej modyfikujemy r.bf
  234.         if(r->left == p) r->bf =  1;
  235.         else             r->bf = -1;
  236.  
  237.         p = r;          // przechodzimy w górę na wyższy poziom
  238.         r = r->up;
  239.       }
  240.  
  241.       if(t)             // jeśli r.bf = +/- 1, to musimy
  242.       {                 // równoważyć drzewo
  243.         if(r->bf == 1)
  244.         {
  245.           if(r->right == p) r->bf = 0;  // gałęzie się równoważą
  246.           else if(p->bf == -1) LR(root,r);
  247.           else                 LL(root,r);
  248.         }
  249.         else
  250.         {              // r.bf = -1
  251.           if(r->left == p) r->bf = 0;  // gałęzie się równoważą
  252.           else if(p->bf == 1) RL(root,r);
  253.           else                RR(root,r);
  254.         }
  255.       }
  256.     }
  257.   }
  258. }
  259.  
  260. // Funkcja znajduje poprzednik węzła p
  261. //------------------------------------
  262. AVLNode * predAVL(AVLNode * p)
  263. {
  264.   AVLNode * r;
  265.  
  266.   if(p)
  267.   {
  268.     if(p->left)
  269.     {
  270.       p = p->left;
  271.       while(p->right) p = p->right;
  272.     }
  273.     else
  274.       do
  275.       {
  276.         r = p;
  277.         p = p->up;
  278.       } while(p && p->right != r);
  279.   }
  280.   return p;
  281. }
  282.  
  283. // Funkcja szuka w drzewie AVL węzła o zadanym kluczu.
  284. // Jeśli go znajdzie, zwraca jego wskazanie. Jeżeli nie,
  285. // to zwraca wskazanie puste.
  286. // Parametrami są:
  287. // p - wskazanie korzenia drzewa AVL
  288. // k - klucz poszukiwanego węzła
  289. //----------------------------------------------------
  290. AVLNode * findAVL(AVLNode * p, int k)
  291. {
  292.   while(p && p->key != k)
  293.     p = (k < p->key) ? p->left: p->right;
  294.  
  295.   return p;
  296. }
  297.  
  298. // Funkcja usuwa rekurencyjnie węzeł x
  299. // root - referencja do zmiennej z adresem korzenia
  300. // x - wskazanie usuwanego węzła
  301. //-------------------------------------------------
  302. AVLNode * removeAVL(AVLNode * & root, AVLNode * x)
  303. {
  304.   AVLNode  *t,*y,*z;
  305.   bool nest;
  306.  
  307.   if(x->left && x->right)
  308.   {
  309.     y    = removeAVL(root,predAVL(x));
  310.     nest = false;
  311.   }
  312.   else
  313.   {
  314.     if(x->left)
  315.     {
  316.       y = x->left; x->left = NULL;
  317.     }
  318.     else
  319.     {
  320.       y = x->right; x->right = NULL;
  321.     }
  322.     x->bf = 0;
  323.     nest  = true;
  324.   }
  325.  
  326.   if(y)
  327.   {
  328.     y->up    = x->up;
  329.     y->left  = x->left;  if(y->left)  y->left->up  = y;
  330.     y->right = x->right; if(y->right)  y->right->up = y;
  331.     y->bf    = x->bf;
  332.   }
  333.  
  334.   if(x->up)
  335.   {
  336.     if(x->up->left == x) x->up->left = y; else x->up->right = y;
  337.   }
  338.   else root = y;
  339.  
  340.   if(nest)
  341.   {
  342.     z = y;
  343.     y = x->up;
  344.     while(y)
  345.     {
  346.       if(!y->bf)
  347.       {              // Przypadek nr 1
  348.         if(y->left == z)  y->bf = -1; else y->bf = 1;
  349.         break;
  350.       }
  351.       else
  352.       {
  353.         if(((y->bf == 1) && (y->left == z)) || ((y->bf == -1) && (y->right == z)))
  354.         {           // Przypadek nr 2
  355.           y->bf = 0;
  356.           z = y; y = y->up;
  357.         }
  358.         else
  359.         {
  360.           if(y->left == z)  t = y->right; else t = y->left;
  361.           if(!t->bf)
  362.           {         // Przypadek 3A
  363.             if(y->bf == 1) LL(root,y); else RR(root,y);
  364.             break;
  365.           }
  366.           else if(y->bf == t->bf)
  367.           {         // Przypadek 3B
  368.             if(y->bf == 1) LL(root,y); else RR(root,y);
  369.             z = t; y = t->up;
  370.           }
  371.           else
  372.           {         // Przypadek 3C
  373.             if(y->bf == 1) LR(root,y); else RL(root,y);
  374.             z = y->up; y = z->up;
  375.           }
  376.         }
  377.       }
  378.     }
  379.   }
  380.   return x;
  381. }
  382.  
  383. //Inorder
  384. void inorder(AVLNode * root)
  385. {
  386.   if(root)
  387.   {
  388.     inorder(root->left);
  389.     cout << root->key << endl;  // tutaj przetwarzamy bieżący węzeł
  390.     inorder(root->right);
  391.   }
  392. }
  393. //preoder
  394. void preorder(AVLNode * root){
  395.   {
  396.       if(root == NULL)
  397.         return;
  398.  
  399.     cout << root->key << endl;  // tutaj przetwarzamy bieżący węzeł
  400.     preorder(root->left);
  401.     preorder(root->right);
  402.   }
  403.  
  404. }
  405. //rekurencyjnie wywolanie
  406. void postorder(AVLNode * root){
  407.     if(root)
  408.   {
  409.     postorder(root->left);
  410.     postorder(root->right);
  411.     cout << root->key << endl;  // tutaj przetwarzamy bieżący węzeł
  412.   }
  413.  
  414. }
  415.  
  416.  
  417.  
  418.  
  419.  
  420.  
  421.  
  422.  
  423.  
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430. int main()
  431. {
  432.     int n,m=0;
  433.     cout<<"Podaj ilosc elementow w drzewie albo ile liczb wczytac z pliku\n";
  434.     cin>>n;
  435.   int Tk[n];   // tablica kluczy wezlow
  436.   int i,x,i1,y,temp=1;
  437. int    Td[temp+100]; //dodaktowa tabluca na dodane wezly
  438.   fstream plik1;
  439.   string linia;
  440.  
  441.   AVLNode * root = NULL;
  442.  
  443.  
  444.  
  445.   cr = cl = cp = "  ";
  446.   cr[0] = 218; cr[1] = 196;
  447.   cl[0] = 192; cl[1] = 196;
  448.   cp[0] = 179;
  449.   //symbole ascii polaczen
  450.  
  451. int tmp=-1;
  452. int choose=-1;
  453.     do{
  454.         cout<<"\n 1.Podaj wartosci do drzewa z klawaitury\n";
  455.         cout<<" 2.Dane do drzewa z pliku\n";
  456.         cout<<" 3.Zrob drzewo z danych\n";
  457.         cout<<" 4. Pokaz drzewo\n";
  458.         cout<<" 5. Dodaj wezel drzewa\n";
  459.         cout<<" 6. Usun klucz drzewa\n";
  460.         cout<<" 7. Usun drzewo\n";
  461.         cout<<" 8. Kolejnosc Inorder\n";
  462.         cout<<" 9. Kolejnosc preorder\n";
  463.         cout<<" 10. Kolejnosc postorder\n";
  464.         cout<<" 0. Zamknij program\n";
  465.         cin>>tmp;
  466.         system("cls");
  467.  
  468. switch (tmp){
  469. case 1:
  470.     cout<<"\nPodawaj"<<n<<"  wartosci do drzewa z klatwiatury\n";
  471.     for( int i = 0; i <n; i++)   // Tablicê wypelniamy wartoœciami kluczy
  472.   {
  473.       cin>>i1;              //podawanie wartosci z klawiatury
  474.     Tk[i] =i1;
  475.   }
  476.     break;
  477. case 2:
  478.  
  479.     cout<<"\nDane do drzewa zostaly zaladowane z pliku\n";
  480.     plik1.open("dane.txt", ios::in);
  481.             for(int i = 0; i < n; i++){
  482.             plik1 >> Tk[i];
  483.             cout<<"\n"<<Tk[i];
  484.             }
  485.         plik1.close();
  486.  
  487.     break;
  488. case 3:
  489.   for(int i = 0; i < n; i++)   // Na podstawie tablicy tworzymy drzewo AVL
  490.   {
  491.     cout << Tk[i] << " ";
  492.     insertAVL(root,Tk[i]);
  493.   }
  494.  
  495.   cout << endl << endl;
  496.     break;
  497. case 4:
  498.      printBT("","",root);      // Wyświetlamy zawartość drzewa AVL
  499.  
  500.     break;
  501. case 5:
  502.     cout<<"Podaj wartosc wezla\n";
  503.     cin>>y;
  504.     for(int i=0 ;i<temp;i++){
  505.         Td[i]=y;
  506.     }
  507.     insertAVL(root,y);
  508.     temp++;
  509.     m++;
  510.     break;
  511. case 6:
  512.     cout<<"Podaj wartosc wezla ktory chcesz usunac\n";
  513.     cin>>y;
  514.      removeAVL(root,findAVL(root,y));
  515.  
  516.     break;
  517.  
  518. case 7:
  519.     cout<<"Usunieto cale dzrzewo\n";
  520.     for(int y=0;y<temp+n;y++){
  521.     removeAVL(root,findAVL(root,Tk[y]));
  522.     removeAVL(root,findAVL(root,Td[y]));
  523.     }
  524.  
  525.     break;
  526.  
  527. case 8:
  528.     cout<<"Kolejnosc inorder\n";
  529.     inorder(root);
  530.     break;
  531. case 9:
  532.     cout<<"Kolejnosc preorder\n";
  533.     preorder(root);
  534.     break;
  535. case 10:
  536.      cout<<"Kolejnosc postorder\n";
  537.     postorder(root);
  538.      break;
  539.  
  540. case 0:
  541.     exit(0);
  542.     break;
  543.  
  544. }
  545.  }while(choose);
  546. return 0;
  547. }
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