// 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)
{
	node *tmp = p;
	int najblizej =tmp->val;
	int roznica, roznicaN;
	while (tmp->next)
	{
	
		if (abs(srednia - tmp->val) < abs(srednia - tmp->next->val))
		{
			najblizej = tmp->val;
			tmp = tmp->next;
		}
		else tmp = tmp->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;
		insertBST(root, y);
		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 << "HEAD ->";
	while (pom != NULL)
	{
		cout << pom->val << "->";
		pom = pom->next;
	}
	cout << "NULL" << endl;
}