define _CRT_SECURE_NO_WARNI NGS include stdafx include conio include i

#define _CRT_SECURE_NO_WARNINGS
#include "stdafx.h"
#include <conio.h> 
#include <iostream>
#include <windows.h>

int lvl=0;//количество уровней
int added=0;//сколько элементов уже добавленно на этом уровне
int z = 1;//переменная для добавления после последнего уровня
int count=0;//Количество элементов в левом поддереве

struct tree
{
	int koren;
	tree* left;
	tree* right;
};

tree* NewTree(int info)//Добавление элемента
{
	tree* Elem = new tree;
	Elem->koren = info;
	added++;//говорим что добавлен элемент на уровень
	int j=1;
	for (int i = 1; i < lvl; i++)
		j *= 2;
	if (added == j) { added = 0; lvl++; }//кол-во добавлений = кол-ву элементов по расчету по переход на след уровень
	Elem->left = NULL;
	Elem->right = NULL;
	return Elem;
}

void print_Tree(tree* p, int lvl)//вывод дерева
{
	if (p)//Если дерево есть то выводим
	{
		print_Tree(p->right, lvl + 1);
		for (int i = 0; i< lvl; i++) printf( "   ");
		printf("%d\n",p->koren);
		print_Tree(p->left, lvl + 1);
	}
}

void Dobavit(int info,int N1,int N2,tree* derevo)//поиск места для добавления
{
	z++;
	int G = N2-(N2-N1)/2-0.0001;//поиск середины с округлением ВНИЗ
	if ((N1 == added + 1) && (z==lvl)) { derevo->left = NewTree(info); return; };
	if ((N2 == added + 1) && (z == lvl)) { derevo->right = NewTree(info); return; };
	if (((added + 1) < G+1) || ((added + 1) == G)) { Dobavit(info, N1, G, derevo->left); }
	else { Dobavit(info, G+1, N2, derevo->right); };
	return;
}

void Resh(tree* derevo)//Определение для каждой вершины числа вершин в левом поддереве
{
		if (derevo != NULL)
		{
			Resh(derevo->left);
			Resh(derevo->right);
			count++;
		}
}

void straight(tree* derevo)//Прямой обход
{
	if (derevo != NULL)
	{
		printf("%d ", derevo->koren);
		straight(derevo->left);
		straight(derevo->right);
	}
 }

void symetric(tree* derevo)//Симетричный обход
{
	if (derevo != NULL)
	{
		symetric(derevo->left);
		printf("%d ", derevo->koren);
		symetric(derevo->right);
	}
}

void reverse(tree* derevo)//Обратный обход
{
	if (derevo != NULL)
	{
		reverse(derevo->left);
		reverse(derevo->right);
		printf("%d ", derevo->koren);
	}
}

tree* del_tree(tree *derevo, int val) //удалить элемент из дерева
{
	if (NULL == derevo) return NULL;

	if (derevo->koren == val) {
		if (NULL == derevo->left && NULL == derevo->right) { // если лист 
			free(derevo); 
			return NULL;
		}
		if (NULL == derevo->right && derevo->left != NULL) { 
			tree *temp = derevo->left;
			free(derevo);
			return temp;
		}
		if (NULL == derevo->left && derevo->right != NULL) { 
			tree *temp = derevo->right;
			free(derevo);
			return temp;
		}
		derevo->left = del_tree(derevo->left, derevo->koren);
		return derevo;
	}

	// поиск нужного элемента
	if (val < derevo->koren) {
		derevo->left = del_tree(derevo->left, val);
		return derevo;
	}

	if (val > derevo->koren) {
		derevo->right = del_tree(derevo->right, val);
		return derevo;
	}
	return derevo;
}



int main()
{
	int info=0;//значение текущего элемента
	tree* derevo=NULL;
	printf("LR#4. Derevo. Var13.\nVvedite koren dereva: ");
	if (scanf("%d", &info) != 1) {
		printf("Vvedeno ne koren. Nevernii symbol.\n"); 
		return 0; 
		}
	added = 0; //кол-во добавленных элементов
	lvl = 1; //текущий уровень дерева
	derevo = NewTree(info); //создаем новое дерево с введенным корнем
	char ch1=' ';//переменная для ввода кода операции
	int N2=1;//количество заполненных уровней
	int n;

	while (ch1 != 'e')//Вывод меню для работы с деревом
	{
		fflush(stdin);
		printf("_____________________________________________");
		printf("\nVvedite opperatiy: \n d-dobavit elementi\n v-vivod dereva\n o-obhod\n r-Vipolnenie zadania. Kol-vo vershin v levom poddereve. \n u - Udalit derevo\n e-EXIT\n");
		ch1=getchar();
		switch (ch1){

		case 'd'://добавить элементы
			fflush(stdin);
			printf("Vvedite colichestvo: ");
			if (scanf("%d", &n) != 1) 
				{ 
					printf("Vvedeno ne chislo\n");
					break; 
				}
			printf("Vvedite elementi(razdelitel - enter):\n");
			for (int i = 0; i < n; i++)
				{
					if (scanf("%d", &info) != 1) 
						{ 
							printf("Vvedeno ne chislo\n");
							break; 
						}
					for (int i = 1; i < lvl; i++)
						N2 *= 2;
					Dobavit(info, 1, N2, derevo);
					N2 = 1;
					z = 1;
				}
			break;

		case 'v':
			print_Tree(derevo,0);
			break;

		case 'o':
			printf("\nKLR: ");
			straight(derevo);
			printf("\nLKR: ");
			symetric(derevo);
			printf("\nLRK: ");
			reverse(derevo);
			printf("\n");
			break;

		case 'r':
			count = 0;
			Resh(derevo->left);
			printf("Kolichestvo vershin v levom poddereve = %d\n", count);
			count = 0;
			break;

		case 'u': 
			printf("\n Vvedite udal element: ");
			int t;
			if (scanf("%d", &t) != 1) 
				{ 
					printf("Vvedeno ne chislo\n");
					break; 
				}
			fflush(stdin);
			derevo = del_tree(derevo, t);
			break;
		}
	}
	return 0;
}