#include <iostream>
#include <ctime>

using namespace std;

// Вероятность создания очередного узла (для ограничения количества сгенерированных элементов и глубины дерева), в процентах.
#define CHANCE_TO_BIRTH_CHILD_NODE 60
// Максимальная глубина вложенности дерева (во избежание переполнения стека из-за сверхглубокой рекурсии)
#define MAX_DEPTH 5

// Структура, описывающая узел (ветку или лист) бинарного дерева.
struct TreeNode {
	TreeNode *parent; // ссылка на родительский узел. У корневого узла эта ссылка равна NULL
	TreeNode *left, *right; // ссылки на левое и правое поддеревья. Для листьев эти ссылки равны NULL. Для многодетного дерева вместо этих переменных можно объявить массив
	int value; // содержимое узла
	int level; // уровень узла в глубине дерева
};

int LAST_VAL = 0; // последнее использованное значение узла; каждый новый узел получает значение на 1 больше предыдущего; этим реализуется уникальность значений

/* ======================= Вспомогательные функции ======================= */
// Функция для генерации потомка узла бинарного дерева.
// Вероятность появления потомка определяется шансом, равным CHANCE_TO_BIRTH_CHILD_NODE.
TreeNode *TryGenerateChild(TreeNode *parent) {
	if (parent->level >= MAX_DEPTH) return NULL; // если добрались до максимальной глубины - отменить создание потомка
	TreeNode *node; // ссылка на этот узел
	int gamble; // расчет попытки рождения этого потомка
	// Пробуем создать этот узел-потомок. В случае ошибки элемент будет равен NULL.
	try
	{
		gamble = rand() % 100; // генерируем случайное число 0-99
		if (gamble <= CHANCE_TO_BIRTH_CHILD_NODE) { // если это число попадает в вероятность рождения - этот потомок рождается
			node = new TreeNode();
			node->parent = parent;
			node->value = ++LAST_VAL;
			node->level = parent->level + 1;
			node->left = TryGenerateChild(node); // рожденному потомку создаем его левого потомка
			node->right = TryGenerateChild(node); // рожденному потомку создаем его правого потомка
		}
		else { // если у этого потомка НЕ получилось родиться
			node = NULL;
		}
	}
	catch (const std::exception&)
	{
		node = NULL;
	}
	return node;
}

// Функция для генерации бинарного дерева.
TreeNode *GenerateTree() {
	TreeNode *treeRoot = new TreeNode(); // создание ссылки на корень дерева
	treeRoot->parent = NULL; // выше корневого узла ничего нет
	treeRoot->value = ++LAST_VAL; // значение узла
	treeRoot->level = 1;
	treeRoot->left = TryGenerateChild(treeRoot); // создаем левое поддерево
	treeRoot->right = TryGenerateChild(treeRoot); // создаем правое поддерево
	return treeRoot;
}

/* ======================= Основные функции ======================= */
// Точка входа в программу.
void main() {
	system("cls"); // очистка окна консоли
	//setlocale(0, "rus"); // для корректного отображения кириллицы в консоли
	srand((int)time(0)); // инициализация ГПСЧ (генератора псевдослучайных чисел)
	TreeNode *tree = GenerateTree(); // генерируем бинарное дерево
	system("pause");
}