/*
	Дано число N(>0) и набор из N чисел.
	1) Отсортировать по возрастанию.
	2) Создать функцию добавления элемента в дерево.
	3) Реализовать обходы:
	3.1 - Прямой
	3.2 - Симметричный
	3.3 - Обратный
*/


#include <iostream>
#include <Windows.h>
#include <cmath>

using namespace std;

struct Tree
{
	int val;
	Tree* left;
	Tree* right;
};

Tree* makenode(int val)
{
	Tree *tempTree = new Tree;
	tempTree->left = tempTree->right = nullptr;
	tempTree->val = val;
	return tempTree;
}

void setLeft(Tree* aTree, int val) {
	aTree->left = makenode(val);

}


void setRight(Tree* aTree, int val) {
	aTree->right = makenode(val);

}

void insert(Tree *aTree, int val)
{
	while (true) {
		if (val <= aTree->val) {
			if (aTree->left != nullptr) {
				aTree = aTree->left;
			}
			else {
				setLeft(aTree, val);
				break;
			}
		}
		else {
			if (aTree->right != nullptr) {
				aTree = aTree->right;
			}
			else {
				setRight(aTree, val);
				break;
			}
		}
	}
}

void inTrav(Tree * aTree) {
	if (aTree->left != nullptr) {
		inTrav(aTree->left);
	}
	cout << "()==[:::::::::::::>" << aTree->val << endl;
	if (aTree->right != nullptr) inTrav(aTree->right);
}

void inTheIiteral(Tree *tree)//в прямом
{
	if (NULL == tree)    return;    //Если дерева нет, выходим

	cout << "()==[:::::::::::::>" << tree->val << endl; //Посетили узел
	inTheIiteral(tree->left); //Обошли левое поддерево
	inTheIiteral(tree->right); //Обошли правое поддерево
}

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

	symmetry(tree->left); //Обошли левое поддерево
	cout << "()==[:::::::::::::>" << tree->val << endl; //Посетили узел
	symmetry(tree->right); //Обошли правое поддерево
}

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

	reverse(tree->left); //Обошли левое поддерево
	reverse(tree->right); //Обошли правое поддерево

	cout << "()==[:::::::::::::>" << tree->val << endl; //Посетили узел
}


int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);

	int N;
	cout << "Введите число N вершин бинарного дерева: ";
	cin >> N;

	Tree* myTree = makenode(65);
	for (int i = 0; i < N - 1; i++) {
		insert(myTree, rand() % 100);
	}

	cout << "Сортировка элементов: " << endl;
	inTrav(myTree);
	cout << "-----------------------------------------------" << endl;
	cout << "Обход в прямом порядке: " << endl;
	inTheIiteral(myTree);
	cout << "-----------------------------------------------" << endl;
	cout << "Симметричный обход: " << endl;
	symmetry(myTree);
	cout << "-----------------------------------------------" << endl;
	cout << "Обратный обход: " << endl;
	reverse(myTree);

	return 0;
}