- // 1 zadanko to podzielić na 50 list według wartości: 1-10 do nr 1 11-20 do nr 2 itp, potem posortować, i scalić
- // 2 podzielić na 50 list, wyjąć element najbliższy średniej z danej listy, i dać go do nowej listy, potem z tej listy nowej zrobić drzewo i usunąć z niego liście
- #include <iostream>
- #include <string>
- #include <cstdlib>
- #include <ctime>
- #include <fstream>
- #include <cmath>
- using namespace std;
- struct node
- {
- int val;
- node *next;
- };
- struct BSTNode
- {
- BSTNode *up, *left, *right;
- int key;
- };
- string cr, cl, cp;
- void printBT(string sp, string sn, BSTNode * v)
- {
- string s;
- if (v)
- {
- s = sp;
- if (sn == cr) s[s.length() - 2] = ' ';
- printBT(s + cp, cr, v->right);
- s = s.substr(0, sp.length() - 2);
- cout << s << sn << v->key << endl;
- s = sp;
- if (sn == cl) s[s.length() - 2] = ' ';
- printBT(s + cp, cl, v->left);
- }
- }
- void insert(node *&H, int x);
- void remove(node *&H);
- void show(node *H);
- int* ReadDataFromFile(int &size);
- void swap(node *&H, node *x)
- {
- if (x == NULL)
- {
- node *p = H;
- node *tmp = H->next;
- p->next = tmp->next;
- H = tmp;
- tmp->next = p;
- }
- else
- {
- node *p = x->next;
- node *tmp = p->next;
- p->next = tmp->next;
- tmp->next = p;
- x->next = tmp;
- }
- }
- void bubble(node *&H)
- {
- bool flag = true;
- while (flag)
- {
- node *p = H;
- node *tmp = NULL;
- flag = false;
- if (p->val > p->next->val)
- {
- node *pusty = NULL;
- swap(H, pusty);
- flag = true;
- }
- while (p->next->next != tmp)
- {
- if (p->next->val > p->next->next->val)
- {
- swap(H, p);
- flag = true;
- }
- p = p->next;
- }
- tmp = p;
- }
- }
- int average(node *p)
- {
- int suma = 0;
- int licznik = 0;
- if (p)
- {
- while (p)
- {
- suma = suma + p->val;
- licznik++;
- p = p->next;
- }
- }
- return (suma / licznik);
- }
- int najblizszySredniej(node *p, int srednia)
- {
- if (!p)
- return false;
- int najblizej = p->val;
- int ABS = abs(p->val - srednia);
- while (p->next)
- {
- if ( ABS < (abs(p->next->val - srednia)))
- p = p->next;
- else
- {
- najblizej = p->next->val;
- ABS = abs(p->next->val - srednia);
- p = p->next;
- }
- }
- return najblizej;
- }
- void insertBST(BSTNode *&root, int x)
- {
- BSTNode *nowy = new BSTNode;
- nowy->left = nowy->right = NULL;
- nowy->key = x;
- BSTNode *p = root;
- if (!p)
- root = nowy;
- else while (true)
- {
- if (x < p->key)
- {
- if (!p->left)
- {
- p->left = nowy;
- break;
- }
- else p = p->left;
- }
- else
- {
- if (!p->right)
- {
- p->right = nowy;
- break;
- }
- else p = p->right;
- }
- }
- nowy->up = p;
- }
- bool isLeaf(BSTNode *p)
- {
- if (p)
- {
- if (!p->left && !p->right)
- return true;
- else return false;
- }
- }
- void deleteLeaf(BSTNode *&root)
- {
- if (root)
- {
- if (isLeaf(root))
- {
- if (root->up)
- {
- if (root->up->left == root)
- root->up->left = NULL;
- else root->up->right = NULL;
- delete root;
- root = NULL;
- }
- }
- else
- {
- deleteLeaf(root->left);
- deleteLeaf(root->right);
- }
- }
- }
- int main()
- {
- cr = cl = cp = " ";
- cr[0] = 218; cr[1] = 196;
- cl[0] = 192; cl[1] = 196;
- cp[0] = 179;
- node *H = NULL;
- BSTNode *root = NULL;
- int size = 0;
- int *t = ReadDataFromFile(size);
- node *listy[50];
- for (int i = 0; i < 50; i++)
- listy[i] = NULL;
- int i = 0;
- for (int j = 0; j < 50; j++)
- for (int k = 0; k < 10; k++)
- {
- insert(listy[j], t[i]);
- i++;
- }
- int srednie[50];
- for (int i = 0; i < 50; i++)
- {
- show(listy[i]);
- srednie[i] = average(listy[i]);
- cout << "Srednia elementow listy nr " << i + 1 << " wynosi " << srednie[i] << endl;
- int y = najblizszySredniej(listy[i], srednie[i]);
- cout << "Najblizszy sredniej: " << y << endl;
- insert(H, y);
- insertBST(root, y);
- cout << endl;
- }
- cout << "Nowa lista: " << endl;
- show(H);
- cout << endl;
- cout << "Drzewo z nowej listy: " << endl;
- printBT("", "", root);
- cout << "Po obcieciu lisci: " << endl;
- deleteLeaf(root);
- printBT("", "", root);
- system("PAUSE");
- return 0;
- }
- int* ReadDataFromFile(int &size)
- {
- fstream czytaj;
- czytaj.open("liczby.txt");
- czytaj >> size;
- int*Data = new int[size];
- for (int i = 0; i<size; i++)
- czytaj >> Data[i];
- czytaj.close();
- return Data;
- }
- void insert(node *&H, int x)
- {
- node *pom;
- pom = new node;
- pom->val = x;
- pom->next = H;
- H = pom;
- }
- void remove(node *&H)
- {
- if (H != NULL)
- {
- node *pom = H;
- H = pom->next;
- delete pom;
- }
- }
- void show(node *H)
- {
- node *pom = H;
- cout << "H->";
- while (pom != NULL)
- {
- cout << pom->val << "->";
- pom = pom->next;
- }
- cout << "NULL" << endl;
- }