SHARE
TWEET

Untitled

a guest Dec 8th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ALGO2 N1 20B LAB04
  2. //Maciej Baraniecki
  3. //bm35988@zut.edu.pl
  4.  
  5.  
  6. #include <iostream>
  7. #include <string>
  8. #include <cstdlib>
  9. #include <ctime>
  10. #include <stdio.h>
  11.  
  12. using namespace std;
  13.  
  14. struct BSTNode
  15. {
  16.     int klucz;
  17.     struct BSTNode *left, *right;
  18.     char tab[10];
  19.  
  20. };
  21.  
  22. /*BSTNode* newNode(int klucz)
  23. {
  24.         BSTNode* temp = new BSTNode;
  25.         temp->klucz = klucz;
  26.         temp->left=temp->right = NULL;
  27.         return temp;
  28. }*/
  29.  
  30.  
  31. bool dodaj(BSTNode* root, int klucz)
  32. {
  33.         BSTNode* p = root;
  34.         BSTNode* prev=nullptr;
  35.        
  36.         while(p!=nullptr)
  37.         {
  38.                 prev=p;
  39.                 if(p->klucz<klucz)
  40.                 {
  41.                         p=p->right;
  42.                 }
  43.                 else
  44.                 {
  45.                         p=p->left;
  46.                 }
  47.                
  48.         }
  49.        
  50.         if(root->klucz==0)
  51.         {
  52.                 //root=new BSTNode;
  53.                 root->klucz=klucz;
  54.                 root->left=nullptr;
  55.                 root->right=nullptr;
  56.                 cout<<"Dodano korzen"<<endl;
  57.                 return true;
  58.         }
  59.         else if(prev->klucz<klucz)
  60.         {
  61.                 prev->right=new BSTNode;
  62.                 (prev->right)->klucz=klucz;
  63.                 (prev->right)->left=nullptr;
  64.                 (prev->right)->right=nullptr;
  65.                 cout<<"Dodano wezel prawy"<<endl;
  66.                 return true;
  67.         }
  68.         else if(prev->klucz>klucz)
  69.         {
  70.                 prev->left=new BSTNode;
  71.                 (prev->left)->klucz=klucz;
  72.                 (prev->left)->left=nullptr;
  73.                 (prev->left)->right=nullptr;
  74.                 cout<<"Dodano wezel lewy"<<endl;
  75.                 return true;
  76.         }
  77.         else
  78.         {
  79.                 return false;
  80.         }
  81.        
  82.    
  83. };
  84.  
  85. void wstawianie(BSTNode* root, int X)
  86. {
  87.         int klucz;
  88.     for (int i = 0; i < X; i++)
  89.     {
  90.             do
  91.             {
  92.                 klucz = (rand() % 20000) - 1000;
  93.             }while(dodaj(root,klucz)!=true);
  94.     }
  95. }
  96.  
  97. BSTNode* search(BSTNode* root, int klucz)
  98. {
  99.     BSTNode* p = root;
  100.     if(!p)
  101.     {
  102.             cout<<"Drzewo puste!"<<endl;
  103.             return nullptr;
  104.     }
  105.     while((p==nullptr)&(klucz==p->klucz))
  106.     {
  107.             if(p->klucz<klucz)
  108.             {
  109.                     cout<<"NIE"<<endl;
  110.                     p=p->right;
  111.             }
  112.             else
  113.             {
  114.                     cout<<"TAK"<<endl;
  115.                     p=p->left;
  116.             }
  117.     }
  118.     cout<<"ZNaleziono"<<endl;
  119.     return(p);
  120.    
  121. }
  122.  
  123. BSTNode* minValueNode(BSTNode* node)
  124. {
  125.     BSTNode* current = node;
  126.  
  127.     /* loop down to find the leftmost leaf */
  128.     while (current->left != nullptr)
  129.         current = current->left;
  130.  
  131.     return current;
  132. }
  133.  
  134.  
  135. BSTNode* usun(BSTNode* root, int klucz)
  136. {
  137.         if(root == NULL)
  138.         {
  139.                 return root;
  140.         }
  141.        
  142.         if(klucz < root->klucz)
  143.         {
  144.                 root->left = usun(root->left,klucz);
  145.         }
  146.         else if(klucz > root->klucz)
  147.         {
  148.                 root->right = usun(root->right, klucz);
  149.         }
  150.         else
  151.         {
  152.                 if(root->left == NULL)
  153.                 {
  154.                         BSTNode* temp = root->right;
  155.                         delete(root);
  156.                         return temp;
  157.                 }
  158.                 else if(root->right == NULL)
  159.                 {
  160.                         BSTNode* temp = root->left;
  161.                         delete(root);
  162.                         return temp;
  163.                 }
  164.                
  165.                 BSTNode* temp=minValueNode(root->right);
  166.                
  167.                 root->klucz = temp->klucz;
  168.                
  169.                 root->right = usun(root->right, temp->klucz);
  170.                
  171.         }
  172.         return root;
  173.        
  174.        
  175.        
  176. }
  177.  
  178. BSTNode* usuwaj(BSTNode* root){ //pierwszy argument to head
  179.     if (root->left)
  180.         usuwaj(root->left);
  181.     if (root->right)
  182.         usuwaj(root->right);
  183.     delete(root);
  184.     if (root)
  185.         root = NULL;
  186.    
  187.    
  188.     return NULL;
  189. }
  190.  
  191.  
  192.  
  193.  
  194. void preorder(BSTNode* root)
  195. {
  196.     int liczba = 0;
  197.     {
  198.         if (root == NULL)
  199.             return;
  200.         cout << "PREORDER--------------------------   ";
  201.         cout << root->klucz << " "<<endl;
  202.         liczba++;
  203.        
  204.         preorder(root->left);
  205.         preorder(root->right);
  206.     }
  207.  
  208. }
  209.  
  210.  
  211. void inorder(BSTNode * root)
  212. {
  213.     if (root)
  214.     {
  215.             inorder(root->left);
  216.             cout << "INORDER------------------------   ";
  217.             cout << root->klucz << endl;  // tutaj przetwarzamy bieżący węzeł
  218.             inorder(root->right);
  219.     }
  220. }
  221.  
  222.  
  223. void postorder(BSTNode* root)
  224. {
  225.     if (root == NULL)
  226.         return;
  227.     postorder(root->left);
  228.     postorder(root->right);
  229.     cout << root->klucz << " ";
  230. }
  231.  
  232.  
  233. BSTNode* rotate_right(BSTNode* root, BSTNode* grandfather, BSTNode* parent, BSTNode* child)
  234. {
  235.     BSTNode* tmp;
  236.     if (grandfather){
  237.         if (grandfather->right == parent){
  238.             grandfather->right = child;
  239.         }
  240.         else{
  241.             grandfather->left = child;
  242.         }
  243.     }
  244.     else
  245.         root = child;
  246.  
  247.     if (parent->left == child){
  248.         tmp = child->right;
  249.         child->right = parent;
  250.         parent->left = tmp;
  251.     }
  252.     else{
  253.         tmp = child->right;
  254.         child->left = parent;
  255.         parent->right = tmp;
  256.     }
  257.  
  258.     return root;
  259.  
  260.  
  261. }
  262.  
  263. BSTNode* rotate_left(BSTNode* root, BSTNode* grandfather, BSTNode* parent, BSTNode* child)
  264. {
  265.         BSTNode* tmp;
  266.     if (grandfather){
  267.         if (grandfather->right == parent){
  268.             grandfather->right = child;
  269.         }
  270.         else{
  271.             grandfather->left = child;
  272.         }
  273.     }
  274.     else
  275.         root = child;
  276.  
  277.     if (parent->right == child){
  278.         tmp = child->left;
  279.         child->left = parent;
  280.         parent->right = tmp;
  281.     }
  282.     else{
  283.         tmp = child->left;
  284.         child->right = parent;
  285.         parent->left = tmp;
  286.     }
  287.  
  288.     return root;
  289. }
  290.  
  291. BSTNode* make_backbone(BSTNode* root)
  292. {
  293.         BSTNode* grandfather=NULL;
  294.         BSTNode* tmp=root;
  295.         while(tmp!=NULL)
  296.         {
  297.                 if((tmp->left)!=NULL)
  298.                 {
  299.                         BSTNode* tmp2 = tmp->left;
  300.                         root=rotate_right(root,grandfather,tmp,tmp->left);
  301.                         tmp=tmp2;
  302.                 }
  303.                 else
  304.                 {
  305.                         grandfather=tmp;
  306.                         tmp=tmp->right;
  307.                 }
  308.         }
  309.         return root;
  310. }
  311.  
  312. BSTNode* make_perfect_tree(BSTNode* root,int N)
  313. {
  314.         BSTNode* grandfather=NULL;
  315.         BSTNode* tmp=root;
  316.         BSTNode* tmp2;
  317.         int m=1;
  318.         while(m<=N)
  319.         {
  320.                 m=2*m+1;
  321.         }
  322.         m=m/2;
  323.         for(int i=0;i<(N-m);i++)
  324.         {
  325.                 tmp2=tmp->right;
  326.                 if(tmp2!=NULL)
  327.                 {
  328.                         root=rotate_left(root, grandfather,tmp,tmp->right);
  329.                         grandfather=tmp2;
  330.                         tmp=tmp2->right;
  331.                 }
  332.         }
  333.         while(m>1)
  334.         {
  335.                 m=m/2;
  336.                 grandfather=NULL;
  337.                 tmp=root;
  338.                 for(int j=0;j<m;j++)
  339.                 {
  340.                         tmp2=tmp->right;
  341.                         root=rotate_left(root, grandfather,tmp,tmp->right);
  342.                         grandfather=tmp2;
  343.                         tmp=tmp2->right;
  344.                 }
  345.         }
  346.         return root;
  347. }
  348.  
  349. int maxDepth(BSTNode* root)  
  350. {  
  351.     if (root == NULL)  
  352.         return 0;  
  353.     else
  354.     {  
  355.         int lDepth = maxDepth(root->left);  
  356.         int rDepth = maxDepth(root->right);  
  357.         if (lDepth > rDepth)  
  358.             return(lDepth + 1);  
  359.         else return(rDepth + 1);  
  360.     }  
  361. }  
  362.  
  363.  
  364. int main()
  365. {
  366.     int k1, k2, k3, k4;
  367.     int X;
  368. /*#pragma warning(disable : 4996)
  369.     FILE* fp = fopen("inlab03.txt", "r");
  370.     if (fp == NULL)
  371.         return -1;
  372.     fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);  // wczytanie pliku
  373.     fclose(fp);*/
  374.    
  375.     k1=45;
  376.     k2=245;
  377.     k3=1;
  378.     k4=4;
  379.     X=400;
  380.     int N;
  381.  
  382.  
  383. //czas start
  384.  
  385.     clock_t begin, end;
  386.     double time_spent;
  387.     srand((unsigned int)time(NULL));
  388.     begin = clock();
  389.     BSTNode* root=new BSTNode;
  390.    
  391.     /*dodaj(root,15);
  392.         dodaj(root,10);
  393.         dodaj(root,25);
  394.         dodaj(root,5);
  395.         dodaj(root,13);
  396.         dodaj(root,20);
  397.         dodaj(root,33);
  398.         dodaj(root,22);
  399.         dodaj(root,24);
  400.         inorder(root);
  401.        
  402.         usun(root,33);
  403.         //cout << "root:" << root << "  " << root->klucz<<endl;
  404.         inorder(root);
  405.        
  406.         int wysokosc=maxDepth(root);
  407.         cout<<"Wysokosc drzewa:"<<wysokosc<<endl;*/
  408.  
  409.    
  410.  
  411.     //inicjacja pustego drzewa
  412.         //BSTNode* root=new BSTNode;// = new BSTNode;
  413.         //root->right=nullptr;
  414.         //root->left=nullptr;
  415.         //root=dodaj(root,((rand() % 20000) - 1000));
  416.        
  417.     //usuń element o wartości klucza k1;
  418.     cout << "Usuwanie elementu o wartosci klucza k1..." << endl;
  419.     usun(root, k1);
  420.     //wstaw element o wartości klucza k1;
  421.     cout << "Dodawanie elementu o wartosci klucza k1..." << endl;
  422.    
  423.     dodaj(root, k1);
  424.     //cout << root << endl;
  425.     //wstaw X elementów do drzewa;
  426.     cout << "Wstawianie X elementow do drzewa..." << endl;
  427.     wstawianie(root, X);
  428.     //wyświetl wszystkie klucze w trybie inorder;
  429.     cout << "Przejscie w trybie inorder..." << endl;
  430.     //inorder(root);
  431.     //wyświetl wszystkie klucze w trybie preorder;
  432.     cout << "Przejscie w trybie preorder..." << endl;
  433.     //preorder(root);
  434.     //wstaw element o wartości klucza k2;
  435.     cout << "Dodawanie elementu o wartosci klucza k2..." << endl;
  436.     dodaj(root, k2);
  437.     //wyświetl wszystkie klucze w trybie inorder;
  438.     cout << "Przejscie w trybie inorder..." << endl;
  439.     //inorder(root);
  440.     //wstaw element o wartości klucza k3;
  441.     cout << "Dodawanie elementu o wartosci klucza k3..." << endl;
  442.     dodaj(root, k3);
  443.     //wstaw element o wartości klucza k4;
  444.     cout << "Dodawanie elementu o wartosci klucza k4..." << endl;
  445.     dodaj(root, k4);
  446.     //usuń element o wartości klucza k1;
  447.     cout << "Usuwanie elementu o wartosci klucza k1..." << endl;
  448.     inorder(root);
  449.     usun(root, k1);
  450.     //wyświetl wszystkie klucze w trybie preorder;
  451.     cout << "Przejscie w trybie preorder..." << endl;
  452.     preorder(root);
  453.     //wyszukaj element o wartości k1;
  454.     cout << "Wyszukanie elementu o wartosci klucza k1..." << endl;
  455.     search(root, k1);
  456.     //usuń element o wartości klucza k2;
  457.     cout << "Usuwanie elementu o wartosci klucza k2..." << endl;
  458.     usun(root, k2);
  459.     //wyświetl wszystkie klucze w trybie inorder;
  460.     cout << "Przejscie w trybie inorder" << endl;
  461.     //inorder(root);
  462.     //usuń element o wartości klucza k3;
  463.     cout << "Usuwanie elementu o wartosci klucza k3..." << endl;
  464.     usun(root, k3);
  465.     //usuń element o wartości klucza k4;
  466.     cout << "Usuwanie elementu o wartosci klucza k4..." << endl;
  467.     usun(root, k4);
  468.         inorder(root);
  469.         cout<<endl;
  470.         //dodaj(root,4);
  471.         //dodaj(root,4);
  472.     inorder(root);
  473.     int wysokosc=maxDepth(root);
  474.         cout<<"Wysokosc drzewa:"<<wysokosc<<endl;
  475.         root=make_backbone(root);
  476.         wysokosc=maxDepth(root);
  477.         cout<<"Wysokosc drzewa (lista):"<<wysokosc<<endl;
  478.         root=make_perfect_tree(root,wysokosc);
  479.         wysokosc=maxDepth(root);
  480.         cout<<"Wysokosc drzewa po DSW:"<<wysokosc<<endl;
  481.     usuwaj(root);
  482.     root=new BSTNode;
  483.  
  484.     //czas stop;
  485.  
  486.     end = clock();
  487.     time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  488.  
  489. //wypisz czas wykonania;
  490.     cout << "Czas wykonania:" << time_spent << endl;
  491.    
  492.     //cout << "root:" << root << "  " << root->klucz<<endl;
  493.    
  494.     }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top