Advertisement
marius7122

Untitled

May 20th, 2022
799
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <stack>
  4.  
  5. struct Nod
  6. {
  7.     int info;
  8.     Nod* st, *dr, *parinte;
  9.     Nod(int info)
  10.     {
  11.         this->info = info;
  12.         st = dr = parinte = nullptr;
  13.     }
  14. };
  15.  
  16. class searchTree
  17. {
  18. public:
  19.     Nod* rad;
  20.  
  21.     searchTree()
  22.     {
  23.         rad = nullptr;
  24.     }
  25.  
  26.  
  27.     void insert(int cheie)
  28.     {
  29.         if (rad == nullptr)
  30.         {
  31.             rad = new Nod(cheie);
  32.         }
  33.  
  34.         else
  35.         {
  36.             Nod* x = rad;
  37.             Nod* parinteNodNou = nullptr;
  38.             while (x != nullptr)
  39.             {
  40.                 parinteNodNou = x;
  41.                 if (cheie < x->info)
  42.                     x = x->st;
  43.                 else
  44.                     x = x->dr;
  45.             }
  46.  
  47.             Nod* z = new Nod(cheie);
  48.             z->parinte = parinteNodNou;
  49.             if (z->info < parinteNodNou->info)
  50.                 parinteNodNou->st = z;
  51.             else
  52.                 parinteNodNou->dr = z;
  53.         }
  54.     }
  55.  
  56.     Nod* minim(Nod* x)
  57.     {
  58.         Nod* y = x;
  59.         while (y->st != nullptr)
  60.             y = y->st;
  61.         return y;
  62.     }
  63.  
  64.     Nod* maxim(Nod* x)
  65.     {
  66.         Nod* y = x;
  67.         while (y->dr != nullptr)
  68.             y = y->dr;
  69.         return y;
  70.     }
  71.  
  72.     Nod* succesor(Nod* x)
  73.     {
  74.         Nod* y;
  75.         if (x->dr != nullptr)
  76.             y = minim(x->dr);
  77.         else
  78.         {
  79.             y = x->parinte;
  80.             while (y != nullptr && x == y->dr)
  81.             {
  82.                 x = y;
  83.                 y = y->parinte;
  84.             }
  85.  
  86.         }
  87.         return y;
  88.     }
  89.  
  90.     Nod* predecesor(Nod* x)
  91.     {
  92.         Nod* y;
  93.         if (x->st != nullptr)
  94.             y = minim(x->st);
  95.         else
  96.         {
  97.             y = x->parinte;
  98.             while (y != nullptr && x == y->st)
  99.             {
  100.                 x = y;
  101.                 y = y->parinte;
  102.             }
  103.  
  104.         }
  105.         return y;
  106.     }
  107.  
  108.     Nod* find(int cheie)
  109.     {
  110.         Nod* x = rad;
  111.         while (x != nullptr && x->info != cheie)
  112.         {
  113.             if (cheie < x->info)
  114.                 x = x->st;
  115.             else
  116.                 x = x->dr;
  117.         }
  118.         return x;
  119.     }
  120.  
  121.  
  122.     void deleteNode(int cheie)
  123.     {
  124.         Nod* nodCurent = rad;
  125.         Nod* prev = NULL;
  126.  
  127.         while (nodCurent != NULL && nodCurent->info != cheie)
  128.         {
  129.             prev = nodCurent;
  130.             if (cheie < nodCurent->info)
  131.                 nodCurent = nodCurent->st;
  132.             else
  133.                 nodCurent = nodCurent->dr;
  134.         }
  135.  
  136.         if (nodCurent == NULL)
  137.         {
  138.             std::cout << "Nodul cu cheia  " << cheie << " nu exista in arbore";
  139.             return;
  140.         }
  141.  
  142.         if (nodCurent->st == NULL || nodCurent->dr == NULL)
  143.         {
  144.             Nod* newCurr;
  145.  
  146.             if (nodCurent->st == NULL)
  147.                 newCurr = nodCurent->dr;
  148.             else
  149.                 newCurr = nodCurent->st;
  150.  
  151.             if (prev == NULL)
  152.                 return;
  153.  
  154.             if (nodCurent == prev->st)
  155.                 prev->st = newCurr;
  156.             else
  157.                 prev->dr = newCurr;
  158.  
  159.             free(nodCurent);
  160.         }
  161.  
  162.         //daca nodul curent are doi copii
  163.         else
  164.         {
  165.             Nod* p = succesor(rad);
  166.             Nod* temp;
  167.  
  168.             temp = nodCurent->dr;
  169.             while (temp->dr != NULL) {
  170.                 p = temp;
  171.                 temp = temp->st;
  172.             }
  173.  
  174.  
  175.             if (p != NULL)
  176.                 p->st = temp->dr;
  177.             else
  178.                 nodCurent->dr = temp->dr;
  179.  
  180.             nodCurent->info = temp->info;
  181.             free(temp);
  182.         }
  183.  
  184.         return;
  185.     }
  186.  
  187.     void erase(Nod* x)
  188.     {
  189.         if (find(x->info))
  190.             deleteNode(find(x->info)->info);
  191.     }
  192.  
  193.     void print_tree(int opt)
  194.     {
  195.         //afisare in preordine
  196.         if (opt == 1)
  197.             preordine(rad);
  198.         if (opt == 2)
  199.             inordine(rad);
  200.         if (opt == 3)
  201.             postordine(rad);
  202.         std::cout << '\n';
  203.     }
  204.  
  205.    
  206.     void construct()
  207.     {
  208.  
  209.     }
  210.  
  211.     void empty()
  212.     {
  213.         if (rad->st == nullptr && rad->dr == nullptr)
  214.             std::cout << "arborele este vid";
  215.         else std::cout << "arborele nu este vid";
  216.     }
  217.  
  218.     void clear()
  219.     {
  220.         if (rad == nullptr)
  221.             return;
  222.  
  223.         std::queue<Nod*> coada;
  224.         coada.push(rad);
  225.  
  226.         Nod* front = nullptr;
  227.  
  228.         while (!coada.empty())
  229.         {
  230.  
  231.             front = coada.front();
  232.             deleteNode(front->info);
  233.         }
  234.     }
  235.  
  236. private:
  237.     void preordine(Nod* nod)
  238.     {
  239.         if (nod == nullptr)
  240.             return;
  241.         preordine(nod->st);
  242.         preordine(nod->dr);
  243.         std::cout << nod->info << ' ';
  244.     }
  245.  
  246.     void inordine(Nod* nod)
  247.     {
  248.         if (nod == nullptr)
  249.             return;
  250.         preordine(nod->st);
  251.         std::cout << nod->info << ' ';
  252.         preordine(nod->dr);
  253.     }
  254.  
  255.     void postordine(Nod* nod)
  256.     {
  257.         if (nod == nullptr)
  258.             return;
  259.         std::cout << nod->info << ' ';
  260.         preordine(nod->st);
  261.         preordine(nod->dr);
  262.     }
  263.  
  264. };
  265.  
  266. int main()
  267. {
  268.     searchTree a;
  269.     bool continua = true;
  270.     while (continua)
  271.     {
  272.         std::cout << "1. insert(cheie)\n";
  273.         std::cout << "2. print_tree(opt)\n";
  274.  
  275.         int alegere, cheie;
  276.         Nod* rad;
  277.         std::cin >> alegere;
  278.         switch (alegere)
  279.         {
  280.         case 1:
  281.             std::cout << "cheie = ";
  282.             std::cin >> cheie;
  283.             a.insert(cheie);
  284.             break;
  285.         case 2:
  286.             a.print_tree(1);
  287.             break;
  288.         }
  289.     }
  290.     return 0;
  291. }
Advertisement
RAW Paste Data Copied
Advertisement