Facebook
From ana, 4 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 192
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct node {
  5.     node *p;
  6.     node *l;
  7.     node *r;
  8.     int val;
  9. };
  10.  
  11. void insert(node *&root, int x, node *p = NULL) {  //dodawawanie elementu
  12.     if (root == NULL) {
  13.         root = new node;
  14.         root->val = x;
  15.         root->l = root->r = NULL;
  16.         root->p = p;
  17.         cout << "wstawiamy: " << root->val << endl;
  18.     }
  19.     else if (x < root->val) {
  20.         insert(root->l, x, root);
  21.     }
  22.     else {
  23.         insert(root->r, x, root);
  24.     }
  25. }
  26.  
  27. void inorder(node *&root) {  //przeszukiwanie (ciag niemalejacy)
  28.     if (root != NULL) {
  29.         inorder(root->l);
  30.         cout << root->val << " ";
  31.         inorder(root->r);
  32.     }
  33. }
  34.  
  35. node* search_rec(node *&root, int x) { //wyszukiwanie rekurencyjne
  36.     if (root != NULL) {
  37.         if (x == root->val) {
  38.             cout << "wartosc znaleziona: " << root->val << endl;
  39.             return root;
  40.         }
  41.         else if (x < root->val) {
  42.             search_rec(root->l, x);
  43.         }
  44.         else {
  45.             search_rec(root->r, x);
  46.         }
  47.     }
  48.    
  49. }
  50.  
  51.  
  52. node* min(node *root) { //najmniejsza wartosc
  53.     if (root != NULL) {
  54.         while (root->l) {
  55.             root = root->l;
  56.         }
  57.  
  58.         //cout << "minimalna wartosc to: " << root->val << endl;
  59.         return root;
  60.     }
  61. }
  62.  
  63. node* max(node *root) {  //najwieksza wartosc
  64.     if (root != NULL) {
  65.         while (root->r) {
  66.             root = root->r;
  67.         }
  68.  
  69.         //cout << "maksymalna wartosc to: " << root->val << endl;
  70.         return root;
  71.     }
  72.  
  73. }
  74.  
  75. node* prev(node *root, int liczba) { //znajdowanie poprzednika
  76.     root = search_rec(root, liczba);
  77.     if (root->l != NULL) {
  78.         cout << "poprzednik to: " << (max(root->l))->val << endl;
  79.         return max(root->l);
  80.     }
  81.     else {
  82.         while (root->p) {
  83.             if (root->p->r == root) {
  84.                 cout << "poprzednik to: " << root->p->val << endl;
  85.                 return root->p;
  86.             }
  87.             else root = root->p;
  88.         }
  89.         cout << "nie ma poprzednika " << endl;
  90.         return 0;
  91.     }
  92. }
  93.  
  94. int counter(node *&root) {
  95.     int i = 0;
  96.     if (root == NULL) {
  97.         return i;
  98.     }
  99.     else{
  100.         i = 1;
  101.         if (root->l) {
  102.             i = i + counter(root->l);
  103.         }
  104.         if (root->r) {
  105.             i = i + counter(root->r);
  106.         }
  107.     }
  108.     return i;
  109. }
  110.  
  111. float avg1(node *&root) {
  112.     float average = 0;
  113.     //average = root->val;
  114.     if (root != NULL) {
  115.             average = root->val;
  116.             if (root->l) {
  117.                 average = average + avg1(root->l);
  118.             }
  119.             if (root->r) {
  120.                 average = average + avg1(root->r);
  121.             }
  122.     }
  123.     return average;
  124. }
  125.  
  126. float avg2(node *&root) {
  127.     float i = float(counter(root));
  128.     float average = (avg1(root)) / i;
  129.     return average;
  130. }
  131.  
  132. void deleaves(node *&root) {
  133.     if (root) {
  134.         if ((root->l || root->r) == NULL) {
  135.             if (root->p->l == root) {
  136.                 root->p->l = NULL;
  137.             }
  138.             else if (root->p->r == root) {
  139.                 root->p->r = NULL;
  140.             }
  141.             delete root;
  142.         }
  143.         else {
  144.             deleaves(root->l);
  145.             deleaves(root->r);
  146.         }
  147.     }
  148. }
  149.  
  150. node* del(node *root, int x)
  151. {
  152.     if (root==NULL) return root;
  153.     else if (x < root->val)
  154.         root->l = del(root->l, x);
  155.    
  156.     else if (x > root->val) {
  157.         root->r = del(root->r, x);
  158.     }
  159.     else{
  160.         if (root->r == NULL && root->l == NULL){
  161.             delete root;
  162.             root = NULL;
  163.         }
  164.         else if (root->r == NULL){
  165.             node *pom = root;
  166.             root = root->l;
  167.             delete pom;
  168.         }
  169.         else if (root->l == NULL){
  170.             node *pom = root;
  171.             root = root->r;
  172.             delete pom;
  173.         }
  174.         else{
  175.             node *pom = prev(root, x);
  176.             root->val = pom->val;
  177.             root->l = del(root->l, pom->val);
  178.         }
  179.     }
  180.     return root;
  181. }
  182.  
  183.  
  184. int main() {
  185.     node *root = NULL;
  186.     node *p = NULL;
  187.     insert(root, 4);
  188.     insert(root, 2);
  189.     insert(root, 14);
  190.     insert(root, 0);
  191.     insert(root, 3);
  192.     insert(root, 11);
  193.     insert(root, 6);
  194.     insert(root, 15);
  195.     insert(root, 7);
  196.     insert(root, 8);
  197.     inorder(root);
  198.     cout << endl;
  199.     del(root, 4);
  200.     inorder(root);
  201.     cout << endl;
  202.     //cout << "srednia: " << avg2(root) << endl;
  203.     //cout << "ilosc: " << counter(root) << endl;
  204.     //max(root);
  205.     //prev(root, 0);
  206.    
  207.     system("PAUSE");
  208.     return 0;
  209. }