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

#include "stdafx.h"
# include "iostream"
using namespace std;
struct tree
{
	int inf;
	tree *left;
	tree *right;
};
tree*create(tree*, int);
void output(tree*);
void delTree(tree*&);
bool task(tree*, int);
tree*balance(tree*, tree*);
int*zapis(tree*, int*, int&);
tree*create2(int, int, int*);
void count(tree*, int&);
void shell(int*, int);
int main()
{
	setlocale(LC_ALL, "rus");
	int k, n, el;
	tree *t = NULL;
	do
	{
		cout << "Введите элемент: ";
		cin >> n;
		t = create(t, n);
		cout << "Продолжить? (1 - да , 0 - нет): ";
		cin >> k;
	} while (k != 0);
	cout << "Исходное дерево:" << endl;
	output(t);
	cout << endl;
	cout << endl;
	tree *broot = NULL;
	int num;
	cout << "Сбалансировать? (1 - да , 0 - нет): ";
	cin >> num;
	if (num == 1)
	{
		broot = balance(broot, t);
		cout << "Сбалансировано!" << endl;
		output(broot);
		cout << endl;
		delTree(broot);
	}
	cout << "el = ";
	cin >> el;
	if (task(t, el))
		cout << "Элемент есть!" << endl;
	else cout << "Элемента нету!" << endl;
	system("pause");
	delTree(t);
	return 0;
}
tree*create(tree*root, int el)
{
	tree*tmp, *prev = NULL;
	tree*t = new tree;
	if (root == NULL)
	{
		t->inf = el;
		t->right = t->left = NULL;
		return t;
	}
	else
	{
		tmp = root;
		while (tmp != NULL)
		{
			prev = tmp;
			if (el>tmp->inf)
				tmp = tmp->right;
			else tmp = tmp->left;
		}
		if (el > prev->inf)
		{
			t->inf = el;
			t->right = t->left = NULL;
			prev->right = t;
		}
		else
		{
			t->inf = el;
			t->right = t->left = NULL;
			prev->left = t;
		}
	}
	return root;
}
void count(tree*root, int &n)
{
	if (root == NULL)
		return;
	count(root->left, n);
	n++;
	count(root->right, n);
}
int*zapis(tree*root, int*arr, int &i)
{
	if (root != NULL)
	{
		zapis(root->left, arr, i);
		arr[i] = root->inf;
		i++;
		zapis(root->right, 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->inf = arr[m];
	t->left = create2(left, m - 1, arr);
	t->right = 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;
		}
	}
}
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;
}


void output(tree *root)
{
	if (root == NULL)
		return;

	//cout << "/ \\" << endl;
	output(root->left);
	//cout << " ";
	cout << root->inf << " ";
	output(root->right);
}
void delTree(tree*&root)
{
	if (root != NULL)
	{
		delTree(root->left);
		delTree(root->right);
		delete root;
		root = NULL;
	}
}
bool task(tree *root, int n)
{
	if (root == NULL)
		return false;
	if (root->inf == n)
		return true;
	if (n <= root->inf)
	{
		if (root->left != NULL)
			return task(root->left, n);
		else
			return false;
	}
	else
	{
		if (root->right)
			return task(root->right, n);
		else return false;
	}
}