// Primer.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

struct tree
{
	int info;
	tree*l, *r;
};
tree*create(tree*, int);
void print(tree*);
void delTree(tree*&);
tree*task(tree*);
tree*balance(tree*, tree*);
int*zapis(tree*, int*, int&);
tree*create2(int, int, int*);
void count(tree*, int&);
void shell(int*, int);
int _tmain(int argc, _TCHAR* argv[])
{
	int c = 0, el;
	tree*root = NULL;
	do
	{
		cout << "Vvedite element ";
		cin >> el;
		root = create(root, el);
		cout << "Vvedite 0 dlya zaversheniya ";
		cin >> c;
	} while (c != 0);
	cout << "Ishodnoe derevo ";
	print(root);
	cout << endl;
	root = task(root);
	cout << "Novoe derevo ";
	print(root);
	cout << endl;
	char ch = 'n';
	cout << "Vediye (y) dlya balansirovki i (n) inache ";
	cin >> ch;
	tree*broot = NULL;
	if (ch == 'y')
	{
		broot = balance(broot, root);
		cout << "Balance tree" << endl;
		print(broot);
		cout << endl;
		delTree(broot);
	}
	delTree(root);
	system("pause");
	return 0;
}
tree*create(tree*root, int el)
{
	tree*tmp, *prev = NULL;
	tree*t = new tree;
	if (root == NULL)
	{
		t->info = el;
		t->r = t->l = NULL;
		return t;
	}
	else
	{
		tmp = root;
		while (tmp != NULL)
		{
			prev = tmp;
			if (el>tmp->info)
				tmp = tmp->r;
			else tmp = tmp->l;
		}
		if (el > prev->info)
		{
			t->info = el;
			t->r = t->l = NULL;
			prev->r = t;
		}
		else
		{
			t->info = el;
			t->r = t->l = NULL;
			prev->l = t;
		}
	}
	return root;
}
void print(tree*root)
{
	if (root == NULL)
		return;
	print(root->l);
	cout << root->info << " ";
	print(root->r);
}
void delTree(tree*&root)
{
	if (root != NULL)
	{
		delTree(root->l);
		delTree(root->r);
		delete root;
		root = NULL;
	}
}
tree*task(tree*root)
{
	tree*t, *prev=NULL, *tmp;
	if (root->info == 5)
	{
		delTree(root->r);
		root->r = NULL;
		return root;
	}
	else
	{
		if (root->info>5)
		{
			delTree(root->r);
			t = root->l;
			delete root;
			root = NULL;
			root = task(t);
			return root;
		}
		if (root->info<5)
		{
			t = root;
			while (t->info<5 && t != NULL)
			{
				prev = t;
				t = t->r;
			}
			tmp = task(t);
			prev->r = tmp;
			return root;
		}
	}
}
void count(tree*root, int&n)
{
	if (root == NULL)
		return;
	count(root->l, n);
	n++;
	count(root->r, n);
}
tree*balance(tree*broot, tree*root)
{
	int n = 0;
	count(root, n);
	int*arr = new int[n];
	int i = 0;
	zapis(root, arr, i);
	shell(arr, n);
	broot = create2(0, n - 1, arr);
	return broot;
}
int*zapis(tree*root, int*arr, int&i)
{
	if (root != NULL)
	{
		zapis(root->l, arr, i);
		arr[i] = root->info;
		i++;
		zapis(root->r, arr, i);
		return arr;
	}
}
tree*create2(int left, int right, int*arr)
{
	if (left>right)
		return NULL;
	int m = (left + right) / 2;
	tree*t = new tree;
	t->info = arr[m];
	t->l = create2(left, m - 1, arr);
	t->r = create2(m + 1, right, arr);
	return t;
}
void shell(int*arr, int n)
{
	int tmp, j;
	for (int step = n / 2; step>0; step /= 2)
	{
		for (int i = step; i<n; i++)
		{
			tmp = arr[i];
			j = i - step;
			while (j >= 0 && tmp<arr[j])
			{
				arr[j + step] = arr[j];
				j -= step;
			}
			arr[j + step] = tmp;
		}
	}
}