/*генерируем 22 уникальных 4-х значных числа представляем их в виде поискового
бинарного дерева и выводим прямой порядок прохождения построенного дерева
*/

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <time.h>
#include <set>
#include <iomanip>


const int N = 22;
int elements[N];
using namespace std;

int tabs = 0; //Для создания отступов
			  //Кол-во отступов высчитывается по кол-ву рекурсивного вхождения при выводе в фукцию print

			  //Структура ветки
struct Branch
{
	int Data; //Поле данных
	Branch *LeftBranch; //УКАЗАТЕЛИ на соседние веточки
	Branch *RightBranch;
};


//Функция внесения данных
void Add(int aData, Branch *&aBranch)
{
	//Если ветки не существует
	if (!aBranch)
	{ //создадим ее и зададим в нее данные
		aBranch = new Branch;
		aBranch->Data = aData;
		aBranch->LeftBranch = 0;
		aBranch->RightBranch = 0;
		return;
	}
	else //Иначе сверим вносимое
		if (aBranch->Data>aData)
		{ //Если оно меньше того, что в этой ветке - добавим влево
			Add(aData, aBranch->LeftBranch);
		}
		else
		{ //Иначе в ветку справа
			Add(aData, aBranch->RightBranch);
		};
}

//Функция вывода дерева
void print(Branch *aBranch)
{
	if (!aBranch) return; //Если ветки не существует - выходим. Выводить нечего
	tabs++; //Иначе увеличим счетчик рекурсивно вызванных процедур
			//Который будет считать нам отступы для красивого вывода

	print(aBranch->LeftBranch); //Выведем ветку и ее подветки слева

	for (int i = 0; i<tabs; i++) cout << "    "; //Потом отступы
	cout << aBranch->Data << endl; //Данные этой ветки


	print(aBranch->RightBranch);//И ветки, что справа

	tabs--; //После уменьшим кол-во отступов
	return;
}

void FreeTree(Branch *aBranch)
{
	if (!aBranch) return;
	FreeTree(aBranch->LeftBranch);
	FreeTree(aBranch->RightBranch);
	delete aBranch;
	return;
}

/*void Show(Branch *aBranch)
{
	if (aBranch == NULL)    return;    //Если дерева нет, выходим

	cout<< (aBranch -> Data); //Посетили узел
	Show(aBranch->LeftBranch); //Обошли левое поддерево
	Show(aBranch->RightBranch); //Обошли правое поддерево
}
*/

int main()
{
	Branch *Root = 0;
	set <int> check;
	setlocale(LC_ALL, "Russian");

	//генерируем числа и записываем их в массив
	for (int i = 0; i < N; ++i) {
		elements[i] = rand() % 9000 + 10000;
		while (check.count(elements[i]))
			elements[i] = rand() % 90000 + 10000;
		check.insert(elements[i]);
	}
	//вывод сгенерированных чисел
	cout << "Генерация неповторяющихся чисел:" << endl;
	for (int i = 0; i < N; ++i)
		cout << setw(2) << setw(4) << elements[i] << "          " << endl;
	cout << " Поисковое дерево:" << endl;
	for (int i = 0; elements[i] ; i++)
	{
		Add(elements[i] , Root);
	}

	print(Root);
	FreeTree(Root);
	cout << "Прямой обход:" << endl;
	//Show(Root); //Обошли дерево и показали его звенья в линейном порядке
	cin.get();
	return 0;
}