#include "stdafx.h"
#include <iostream>

using namespace std;

short int elements;

struct Node
{
	char name[20];
	int short cost, count;
    Node *left, *right;
};

void AddToTree(char name[], int cost, int count, Node *MyTree)
{
	if(strncmp(name, MyTree->name, 1) < 0)
	{
		if (MyTree->left != NULL)
			AddToTree(name, cost, count, MyTree->left);
		else
		{
			MyTree->left = new Node;
			MyTree->left->left = MyTree->left->right =  NULL;
			strcpy(MyTree->left->name, name);
			MyTree->left->cost = cost;
			MyTree->left->count = count;
		}
	}
	else
	{
		if (MyTree->right != NULL)
			AddToTree(name, cost, count, MyTree->right);
		else
		{
			MyTree->right = new Node;
			MyTree->right->left = MyTree->right->right=NULL;
			strcpy(MyTree->right->name, name);
			MyTree->right->cost = cost;
			MyTree->right->count = count;
		}
	}
}

 void PrintTree(Node *Tree, bool method)
{
    if(NULL == Tree)
		return;
	switch(method)
	{
		case false:
		{
			printf("%s\t\t\t%d\t%d\n", Tree->name, Tree->cost, Tree->count);
			PrintTree(Tree->left, false);
			PrintTree(Tree->right, false);
			break;
		}
		case true:
		{
			PrintTree(Tree->left, true);
			PrintTree(Tree->right, true);
			printf("%s\t\t\t%d\t%d\n", Tree->name, Tree->cost, Tree->count);
			break;
		}
	}
}

void PrintLeafs(Node *Tree)
{
    if(Tree)
    {
        PrintLeafs(Tree->left);
        if (!Tree->left && !Tree->right)
            printf("%s\t\t\t%d\t%d\n", Tree->name, Tree->cost, Tree->count);
        PrintLeafs(Tree->right);
    }
}

Node *p;

void SearchMaxCountOfComponents(Node *Tree, int max)
{
	 if(NULL == Tree)
		return;
	if(Tree->count > max)
	{
		max = Tree->count;
		p = Tree;
	}
    SearchMaxCountOfComponents(Tree->left, max);
    SearchMaxCountOfComponents(Tree->right, max);
}

void main()
{
	Node *MyTree = NULL;
	int n;
	{
		setlocale(LC_ALL, "Russian");
		do
		{
			cout << "\n1. Добавить новый елемент";
			cout << "\n2. Вывести дерево (прямой обход)";
			cout << "\n3. Вывести дерево (обратный обход)";
			cout << "\n4. Вывести листья";
			cout << "\n5. Вычислить количество ветвей";
			cout << "\n6. Вывести блок с найбольшим числом узлов";
			cout << "\n7. Выход из программы\n\n";
			cin >> n;
			switch(n)
			{
				case 1:
				{
					char name[20];
					int cost, count;
					cin.get();
					cout << "\tЕлемент № " << ++elements << endl;
					cout << "\nВведите наименование блока: ";
					cin.getline(name, 20);
					cout << "\nВведите цену: ";
					cin >> cost;
					cout << "\nВведите количество узлов: ";
					cin >> count;
					if(MyTree == NULL)
					{
						MyTree = new Node;
						strcpy(MyTree->name, name);
						MyTree->cost = cost;
						MyTree->count = count;
						MyTree->left = MyTree->right = NULL;
					}
					else
						AddToTree(name, cost, count, MyTree);
					break;
				}
				case 2:
				{
					cout << "\n\tДерево (прямой вывод):\n";
					cout << "Наименование блока\tЦена\tКоличество\n";
					PrintTree(MyTree, false);
					break;
				}
				case 3:
				{
					cout << "\n\tДерево: (обратный вывод)\n";
					cout << "Наименование блока\tЦена\tКоличество\n";
					PrintTree(MyTree, true);
					break;
				}
				case 4:
				{
					cout << "\n\tЛистья:\n";
					cout << "Наименование блока\tЦена\tКоличество\n";
					PrintLeafs(MyTree);
					break;
				}
				case 5:
				{
					printf("\nКоличество веток: %d\n", elements-1);
					break;
				}
				case 6:
				{
					p = MyTree;
					int MaxComponents = MyTree->count;
					cout << "\n\tБлок с найбольшим числом узлов:\n";
					SearchMaxCountOfComponents(MyTree, MaxComponents);
					cout << "Наименование блока\tЦена\tКоличество\n";
					printf("%s\t\t\t%d\t%d\n", p->name, p->cost, p->count);
					break;
				}
			}
		}
		while(n != 7);
		setlocale(LC_ALL, "OSP");
	}
}