#include <stdio.h>
#include <stdlib.h>

typedef enum{
	ZERO, ONE, TWO, THREE, FOR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN
} MyEnum;

typedef struct NODE{  //Структура для узла
	struct NODE * LeftNode;
	struct NODE * RightNode;
	MyEnum Value;
	int CountOfValues;
} Node;

typedef struct TREE{ //Структура для дерева
	Node * Root;
} Tree;

Tree * CreateTree() //Создание дерева
{
	Tree * NewTree = (Tree*)malloc(sizeof(Tree));
	(*NewTree).Root = NULL;
	return NewTree;
}

MyEnum InputEnumValue()
{
	MyEnum NewVar;
	int Value = -1;
	printf("Input element from 0 to 10: ");
// 	while(Value <= 0 && Value >=2)
// 	{
		scanf("%d", &Value);
		switch(Value)
		{
		  case 0: NewVar=ZERO; break;
		  case 1: NewVar=ONE; break;
		  case 2: NewVar=TWO; break;
		  case 3: NewVar=THREE; break;
		  case 4: NewVar=FOR; break;
		  case 5: NewVar=FIVE; break;
		  case 6: NewVar=SIX; break;
		  case 7: NewVar=SEVEN; break;
		  case 8: NewVar=EIGHT; break;
		  case 9: NewVar=NINE; break;
		  case 10: NewVar=TEN; break;
		  default: printf("\nError. ");
		  break;
		}
// 	}
	return NewVar;
}

Node * CreateNode(MyEnum NewValue) //Создание узла. 
{
	Node * NewNode = (Node*)malloc(sizeof(Node));
	(*NewNode).LeftNode = NULL;
	(*NewNode).RightNode = NULL;
	(*NewNode).Value = NewValue;
	(*NewNode).CountOfValues = 1;
	return NewNode;
}

void AddNodeToTreeRecursive(Node * TargetNode, MyEnum NewValue)//Смотри ф-цию ниже AddNodeToTree
{
	if((*TargetNode).Value == NewValue)
		(*TargetNode).CountOfValues++;
	else if(NewValue < (*TargetNode).Value)
	{
		if((*TargetNode).LeftNode == NULL)
			(*TargetNode).LeftNode = CreateNode(NewValue);
		else
			AddNodeToTreeRecursive((*TargetNode).LeftNode, NewValue);
	}
	else if(NewValue > (*TargetNode).Value)
	{
		if((*TargetNode).RightNode == NULL)
			(*TargetNode).RightNode = CreateNode(NewValue);
		else
			AddNodeToTreeRecursive((*TargetNode).RightNode, NewValue);
	}
}

void AddNodeToTree(Tree * TargetTree, MyEnum NewValue)//Добавить узел в корень. Если корень пуст то с помощью CreatNode записываем туда значение.
//Если не пустой то идём в AddNodeToTreeRecursive и записываем через неё.
{
	if((*TargetTree).Root == NULL)
		(*TargetTree).Root = CreateNode(NewValue);
	else
		AddNodeToTreeRecursive((*TargetTree).Root, NewValue);
}

void DeleteNodeRecursive(Tree * TargetTree, Node * IterationNode, Node * PreviousNode, MyEnum ValueOfElement, int * NodeIsFound)//Удаление узла
{
	if((*NodeIsFound) == 0)
	{
		if(IterationNode == NULL)
			return;
		if((*IterationNode).Value == ValueOfElement)
		{
			(*NodeIsFound) = 1;
			Node * PartOfDeletedNode = (*IterationNode).RightNode;
			if(PreviousNode != NULL)
			{
				if((*PreviousNode).Value > (*IterationNode).Value)
				{
					(*PreviousNode).LeftNode = (*IterationNode).LeftNode;
					if((*IterationNode).LeftNode == NULL)
					{
						(*PreviousNode).LeftNode = PartOfDeletedNode;
						return;	
					}
					free(IterationNode);
					IterationNode = (*PreviousNode).LeftNode;
					if(IterationNode == NULL)
						return;
					PreviousNode = NULL;
					while(IterationNode != NULL)
					{
						PreviousNode = IterationNode;
						IterationNode = (*IterationNode).RightNode;
					}
					(*PreviousNode).RightNode = PartOfDeletedNode;
				}
				else
				{
					(*PreviousNode).RightNode = (*IterationNode).LeftNode;
					if((*IterationNode).LeftNode == NULL)
					{
						(*PreviousNode).RightNode = PartOfDeletedNode;
						return;	
					}
					free(IterationNode);
					IterationNode = (*PreviousNode).RightNode;
					if(IterationNode == NULL)
						return;

					PreviousNode = NULL;
					while(IterationNode != NULL)
					{
						PreviousNode = IterationNode;
						IterationNode = (*IterationNode).LeftNode;
					}
					(*PreviousNode).RightNode = PartOfDeletedNode;
				}
			}
			else
			{
				(*TargetTree).Root = (*(*TargetTree).Root).LeftNode;
				free(IterationNode);
				IterationNode = (*TargetTree).Root;
				if(IterationNode == NULL)
				{
					(*TargetTree).Root  = PartOfDeletedNode;
					return;
				}
				while(IterationNode != NULL)
				{
					PreviousNode = IterationNode;
					IterationNode = (*IterationNode).RightNode;
				}
				(*PreviousNode).RightNode = PartOfDeletedNode;
			}
			return;
		}
		PreviousNode = IterationNode;
		DeleteNodeRecursive(TargetTree, (*IterationNode).LeftNode, PreviousNode, ValueOfElement, NodeIsFound);
		DeleteNodeRecursive(TargetTree, (*IterationNode).RightNode, PreviousNode, ValueOfElement, NodeIsFound);
	}
}

void DeleteNode(Tree * TargetTree)
{
	if((*TargetTree).Root == NULL)
	{
		printf("Tree is empty.\n");
		return;
	}
	MyEnum ValueOfElement;
	ValueOfElement = InputEnumValue();
	Node * PreviousNode = NULL;
	Node * IterationNode = (*TargetTree).Root;
	int SomethingIsDeleted = 0;
	DeleteNodeRecursive(TargetTree, IterationNode, PreviousNode, ValueOfElement, &SomethingIsDeleted);
	if(SomethingIsDeleted == 0)
	{
		printf("There is no such an element in tree. Nothing is deleted.\n");
	}
	printf("Element is found and deleted.\n");
}

void CountDepthOfTreeRecursive(Node * StartingNode, int * MaximumDepthOfTree, int * CurrentDepthOfTree)//смотри ф-цию ниже
{
	if(StartingNode == NULL)
		return;
	(*CurrentDepthOfTree)++;
	if((*MaximumDepthOfTree) < (*CurrentDepthOfTree))
		(*MaximumDepthOfTree) = (*CurrentDepthOfTree);
	CountDepthOfTreeRecursive((*StartingNode).LeftNode, MaximumDepthOfTree, CurrentDepthOfTree);
	CountDepthOfTreeRecursive((*StartingNode).RightNode, MaximumDepthOfTree, CurrentDepthOfTree);
	(*CurrentDepthOfTree)--;
}

int CountDepthOfTree(Tree * TargetTree)//считает глубину дерева и в ходе выполнения идёт в ф-цую CountDepthOfTreeRecursive
{
	int MaximumDepthOfTree = 0, CurrentDepthOfTree = 0;
	CountDepthOfTreeRecursive((*TargetTree).Root, &MaximumDepthOfTree, &CurrentDepthOfTree);
	return MaximumDepthOfTree;
}

void PrintSpaces(int Count)//нужно для красивого вывода
{
	for(int i = 0; i < Count; i++)
		printf("           ");
}

void PrintTree(Node * StartingNode, int CurrentDepth)//печатает дерево
{
	if(StartingNode == NULL)
	{
		PrintSpaces(CurrentDepth);
		printf("        \n");
		return;
	}
	PrintTree((*StartingNode).RightNode, CurrentDepth+1);
	PrintSpaces(CurrentDepth);
	switch((*StartingNode).Value)
	{case 0: 
	printf("Zero x%2.d\n",(*StartingNode).CountOfValues); 
	break;
	case 1:
	printf("One x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 2:
	printf("Two x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 3:
	printf("Three x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 4:
	printf("For x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 5:
	printf("Five x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 6:
	printf("Six x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 7:
	printf("Seven x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 8:
	printf("Eight x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 9:
	printf("Nine x%2.d\n",(*StartingNode).CountOfValues);
	break;
	case 10:
	printf("Ten x%2.d\n",(*StartingNode).CountOfValues);
	break;
	}
	
	PrintTree((*StartingNode).LeftNode, CurrentDepth+1);
}

void LeftRootRight(Node * StartingNode, int a, int b, int* list, int* count) //Проверяет, все ли листья э[a,b]
{
    if(StartingNode == NULL)
      return;
    if(((*StartingNode).RightNode == NULL)&&((*StartingNode).LeftNode == NULL))
    {
      (*list)++;
      if((a <= (*StartingNode).Value) && ((*StartingNode).Value <= b))
	  (*count)++;
      return;
    }
    LeftRootRight((*StartingNode).LeftNode, a,b,list,count);
    LeftRootRight((*StartingNode).RightNode, a,b,list,count);
}

void MenuDisplay ()//выводит менюшку
{
	printf("   Binary tree\n");
	printf("0. Show this menu\n");
	printf("1. Add element\n");
	printf("2. Delete element\n");
	printf("3. Show tree\n");
	printf("4. Special action\n");
	printf("5. Exit\n");
        printf("6. Tree Level\n");
	}	

int main()
{
	int Action = 1;
	Tree * SomeTree = CreateTree();
	
	MenuDisplay ();
	
	while(Action!=5)
	{
		printf("\nSelet action ");
	        scanf("%d", &Action);
		switch(Action)
		{
		  case 0:
			MenuDisplay();
			break;
		  case 1:
			MyEnum ValueOfElement;
			ValueOfElement = InputEnumValue();
			AddNodeToTree(SomeTree, ValueOfElement);
			break;
		  case 2:
			DeleteNode(SomeTree);
			break;
		  case 3:
			PrintTree((*SomeTree).Root, 0);
			break;
		  case 4:
			printf("Range!\n");
			int list, count;
			MyEnum a, b;
			count=0; list=0;
			printf("Enter range [a,b]\n");
			a = InputEnumValue();
			b = InputEnumValue();
			LeftRootRight((*SomeTree).Root, a,b,&list,&count);
			if(count==list) 
			    printf("\nAll leaves lie in the interval [a,b].\n");
			else 
			    printf("\nNot all leaves lie in the interval [a,b].\n");
			break;
		  case 5:
			break;
	          case 6:
//вывод Степени двоичного дерева
			break;
 	          default:
                       printf ("Enter the action is well!\n");
                       break;
		}
	}
	
	return 0;
}