Facebook
From Matyo, 2 Weeks ago, written in C++.
Embed
Download Paste or View Raw
Hits: 174
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct elem
  5. {
  6.     int key;
  7.     elem* left, * right;
  8. } *root = NULL;
  9.  
  10. void add1(int n, elem* &t)
  11. {
  12.   if (t == NULL)
  13.   {
  14.    t = new elem;  t->key = n;
  15.    t->left = t->right = NULL;
  16.   }
  17.   else
  18.   {
  19.    if (t->key < n)
  20.      add1(n, t->right);  
  21.    else
  22.         add1(n, t->left);
  23.   }
  24. }
  25.  
  26. void add(int n)
  27. {
  28.  add1(n, root);
  29. }
  30.  
  31. void pre_order(elem* t)
  32. {
  33.     if (t)
  34.     {
  35.      cout << t->key << " ";
  36.         pre_order(t->left);
  37.         pre_order(t->right);
  38.     }
  39. }
  40.  
  41. void in_order(elem* t)
  42. {
  43.     if (t)
  44.     {
  45.         in_order(t->left);
  46.         cout << t->key << " ";
  47.         in_order(t->right);
  48.     }
  49. }
  50.  
  51. void post_order(elem* t)
  52. {
  53.     if (t)
  54.     {
  55.         post_order(t->left);
  56.         post_order(t->right);
  57.         cout << t->key << " ";
  58.     }
  59. }
  60.  
  61. void Order(int ord)
  62. {
  63.     switch (ord)
  64.     {
  65.      case 1: { pre_order(root); break; }
  66.      case 2: { in_order(root); break; }
  67.      case 3: { post_order(root); break; }
  68.      default: cout << "Izbrana e nevalidna opciq";
  69.     }
  70. }
  71.  
  72. elem* search(elem* t, int k)
  73. {
  74.     while ((t != NULL) && (t->key != k))  
  75.         if (t->key < k)
  76.             t = t->right;  
  77.         else
  78.             t = t->left;  
  79.     return t;
  80. }
  81.  
  82. elem* search_parent(elem* t, int k)
  83. {
  84.     elem *p = NULL;
  85.     while ((t != NULL) && (t->key != k))
  86.     {
  87.         p = t;
  88.         if (t->key < k)
  89.         {
  90.            // parent = t;
  91.             t = t->right;
  92.         }
  93.         else
  94.         {
  95.             //parent = t;
  96.             t = t->left;
  97.         }
  98.     }
  99.     return p;
  100. }
  101.  
  102. bool del(int k)
  103. {
  104.     elem* p = search(root, k);  
  105.     elem *q = search_parent(root, k), ** qq;
  106.     if (p == NULL)
  107.     {
  108.         return false;  //Възелът не е намерен
  109.     }
  110.     if ((p->right == NULL))
  111.     {
  112.         if (q->left == p)
  113.             q->left = p->left;
  114.         else
  115.             q->right = p->left;
  116.         delete p;
  117.     }
  118.     else
  119.         if (p->left == NULL)
  120.         {
  121.             if (q->left == p)
  122.                 q->left = p->right;
  123.             else
  124.                 q->right = p->right;
  125.             delete p;
  126.         }
  127.         else
  128.         {
  129.             qq = &p->left;
  130.             while ((*qq)->right)  
  131.                 qq = &(*qq)->right;
  132.             p->key = (*qq)->key;
  133.             q = *qq;
  134.             *qq = q->left;  
  135.             delete q;
  136.         }
  137.     return true;
  138. }
  139.  
  140. int main()
  141. {
  142.     add(17);
  143.     add(11);
  144.     add(23);
  145.     add(13);
  146.     add(12);
  147.     add(19);
  148.     add(20);
  149.    //Order(2);
  150.     int order;
  151.     cout << " Izberi vid obhojdane:" << endl;
  152.     cout << " izberi 1 za prefiksno obhojdane" << endl;
  153.     cout << " Izberi 2 za infiksno obhojdane:" << endl;
  154.     cout << " Izberi 3 za postfiksno obhojdane:" << endl;
  155.     cin >> order;
  156.     Order(order);
  157.     bool result = del(17);
  158.     if (result)
  159.         cout << " Vrahat e uspeshno iztrit";
  160.     else
  161.         cout << " Varhat ne e iztrit";
  162.     cout << endl;
  163.     Order(2);
  164.     cout <<endl<< root->key<< " e noviq koren";
  165.   return 0;
  166. }