#define _CRT_SECURE_NO_WARNINGS
#define LINE_WIDTH 70
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <iostream>
#include <math.h>


struct tree {
	int key;
	char fullName[100];
	tree *left, *right;
};


void printLevelOrder(tree *, int);
tree *makeTree(tree*);
tree *list(int, char*);
tree *makeNode(tree*, int, char*);
tree *find(tree*, int);
tree *del(tree**, int);
void exercise(tree**);
void printNode(tree*);
void dellAll(tree*);
void menu();
int countLevels(tree*);
int countNodes(tree*);
int countLeaves(tree*);
void nachaloraboty();



int main()
{
	menu();
	nachaloraboty();
}

int maxLevel = 0;
int curLevel = 0;

void menu() {
	printf("1) Make tree\n"
		"2) Enter new note\n"
		"3) Find a note\n"
		"4) Del the note\n"
		"5) Print the tree\n"
		"6) Do the exercise\n"
		"7) Exit\n");
}

void nachaloraboty()
{
	tree *root = NULL;
	int choice, k;
	char fN[100];
	printf("Enter your choice: ");
	scanf("%i", &choice);
	while (choice != 7) {
		switch (choice) {
		case 1:
			system("cls");
			menu();
			root = makeTree(root);
			break;
		case 2:
			system("cls");
			menu();
			if (root == NULL) {
				printf("\nThe tree isn't exist\n");
				break;
			}
			else {
				printf("\nEnter key: ");
				scanf("%i", &k);
				getchar();
				printf("Enter fullname: ");
				gets_s(fN);
				makeNode(root, k, fN);
			}
			break;
		case 3:
			system("cls");
			menu();
			if (root != NULL) {
				printf("\nEnter the search key: ");
				scanf("%i", &k);
				find(root, k);
			}
			else
				printf("\nThe tree isn't exist\n");
			break;
		case 4:
			system("cls");
			menu();
			if (root != NULL) {
				printf("\nEnter the key of the note to be deleted: ");
				scanf("%i", &k);
				del(&root, k);
			}
			else
				printf("\nThe tree isn't exist\n");
			break;
		case 5:
			system("cls");
			menu();
			curLevel = 0;
			maxLevel = 0;
			if (root != NULL) {
				printLevelOrder(root, countLevels(root));
			}
			else printf("\nThe tree isn't exist\n");
			break;
		case 6:
			system("cls");
			menu();
			if (root != NULL)
				printf("%d\n", countLeaves(root));
			else
				printf("\nThe tree isn't exist\n");
			break;
		default:
			printf("Invalid choice\n");
			break;
		}
		printf("\nEnter your choice: ");
		scanf("%i", &choice);
	}
	dellAll(root);

}

tree *makeTree(tree *rootNode)
{
	int inf;
	char choice = 'y';
	char fullName[100];
	if (rootNode == NULL) {
		printf("\nInput root:\n");
		printf("Key: ");
		scanf("%i", &inf);
		getchar();
		printf("Fullname: ");
		gets_s(fullName);
		rootNode = list(inf, fullName);
	}
	while (1) {
		printf("Do you want enter the new info(y/n)?\n");
		scanf("%c", &choice);
		if (choice != 'y' && choice != 'Y') break;
		printf("\nInput leaf:\n");
		printf("Key: ");
		scanf("%i", &inf);
		printf("Fullname: ");
		getchar();
		gets_s(fullName);
		makeNode(rootNode, inf, fullName);
	}
	return rootNode;
}

tree *list(int value1, char *value2)
{
	tree *newNode = (tree *)malloc(sizeof(tree));// выделяем память для нового узла дерева и инициализируем его.
	newNode->key = value1;
	strcpy(newNode->fullName, value2);// инициализируем его поля
	newNode->left = newNode->right = NULL;// устанавливаем указатели на левое и правое деревья NULL
	return newNode;
}

tree *makeNode(tree *r, int val1, char *val2)
{
	tree *cur = r, *prev = NULL;
	int find = 0;
	while (cur && !find) {
		prev = cur;
		if (cur->key == val1) {
			printf("The note with key(%i) already exist\n", val1);
			find = 1;
		}
		else
		if (val1 < cur->key) cur = cur->left;
		else cur = cur->right;
	}
	if (!find) {
		cur = list(val1, val2);
		if (val1 < prev->key) prev->left = cur;
		else prev->right = cur;
	}
	return cur;
}

tree *find(tree *rootPtr, int keyF)
{
	while (rootPtr != NULL && rootPtr->key != keyF) {
		if (keyF > rootPtr->key) rootPtr = rootPtr->right;
		else rootPtr = rootPtr->left;
	}
	if (rootPtr != NULL) {
		printf("Key: %i\n", rootPtr->key);
		printf("Fullname: ");
		puts(rootPtr->fullName);
	}
	else
		printf("The note with key(%i) isn't find\n", keyF);
	return rootPtr;
}

void dellAll(tree *delNode)
{
	if (delNode != NULL) {
		dellAll(delNode->left);
		dellAll(delNode->right);
		free(delNode);
	}
}

tree *del(tree **search_tree, int item)
{
	tree *delNode, *prevDel, *cur, *prevCur;
	delNode = *search_tree;
	prevDel = NULL;
	while (delNode != NULL && delNode->key != item) {
		prevDel = delNode;
		if (item > delNode->key) delNode = delNode->right;
		else delNode = delNode->left;
	}
	if (delNode == NULL) {
		printf("\nNo note with this key(%i)\n", item);
		return *search_tree;
	}
	else if (delNode->right == NULL) cur = delNode->left;
	else if (delNode->left == NULL) cur = delNode->right;
	else {
		prevCur = delNode;
		cur = delNode->left;
		while (cur->right != NULL) {
			prevCur = cur;
			cur = cur->right;
		}
		if (prevCur == delNode) cur->right = delNode->right;
		else {
			cur->right = delNode->right;
			prevCur->right = cur->left;
			cur->left = delNode->left;
		}
	}
	if (delNode == *search_tree) {
		printf("\nThe note is deleted:\n");
		printNode(*search_tree);
		*search_tree = cur;
		return *search_tree;
	}
	else if (delNode->key < prevDel->key) prevDel->left = cur;
	else prevDel->right = cur;
	printf("\nThe note is deleted:\n");
	printNode(delNode);
	free(delNode);
	return cur;
}

void printNode(tree *node)
{
	printf("Key: %i\n", node->key);
	printf("Fullname: ");
	puts(node->fullName);
}

int countLeaves(tree *node)
{
	if (!node)
		return 0;
	if (!node->left && !node->right)
		return 1;
	return countLeaves(node->left) + countLeaves(node->right);
}


int countLevels(tree *root)
{
	if (root) {
		curLevel++;
		countLevels(root->left);
		if (curLevel > maxLevel) maxLevel = curLevel;
		countLevels(root->right);
		if (curLevel > maxLevel) maxLevel = curLevel;
		curLevel--;
	}
	return maxLevel;
}

void printLevelOrder(tree *root, int mLevel)
{

	tree *tmp = (tree *)malloc(sizeof(tree));
	tmp->key = 0;
	tmp->fullName[0] = '\0';
	tmp->left = NULL;
	tmp->right = NULL;
	int nNodes = 0;
	for (int i = 0; i < mLevel; i++)
		nNodes += (int)pow(2, i);
	int *ar = (int *)malloc(nNodes*sizeof(int));
	char **ar2 = (char **)malloc(nNodes*sizeof(char*));
	for (int i = 0; i < nNodes; i++)
		ar2[i] = (char*)malloc(100 * sizeof(char));
	if (root == NULL) return;
	std::queue<tree *> q;
	q.push(root);
	int v = 0, lv = 1;
	while (1) {

		int nodeCount = q.size();
		if (nodeCount == 0) break;

		while (nodeCount > 0) {
			tree *node = q.front();
			ar[v] = node->key;
			ar2[v] = node->fullName;
			v++;
			q.pop();
			if (node->left != NULL)
				q.push(node->left);
			else if (lv != mLevel)
				q.push(tmp);
			if (node->right != NULL)
				q.push(node->right);
			else if (lv != mLevel)
				q.push(tmp);
			nodeCount--;
		}
		lv++;
	}


	int *print_pos = (int *)malloc(nNodes*sizeof(int));
	int i, j, k, pos, x = 1, level = 0;
	print_pos[0] = 0;
	for (i = 0, j = 1; i<v; i++, j++) {
		pos = (int)(print_pos[((i - 1) / 2)] + (i % 2 ? -1 : 1)*(LINE_WIDTH / (pow(2, level + 1)) + 1));//считаем, скольо нужно пробелов

		for (k = 0; k < pos - x; k++) printf("%c", i == 0 || i % 2 ? ' ' : '-');//печатать пробел или -?
		if (ar[i])
			printf("%d %s", ar[i], ar2[i]);

		print_pos[i] = x = pos + 1;
		if (j == pow(2, level)) {
			printf("\n");
			level++;
			x = 1;
			j = 0;
		}
	}
}