#include <iostream>
#include <map>
#include <vector>

using namespace std;
struct node
{
	int value;
	node *left;
	node *right;
	node()
	{
		value = 0;
		left = right = nullptr;
	}
	node(int data)
	{
		value = data;
		left = right = nullptr;
	}
};

struct Tree
{
	node *root;
	Tree()
	{
		root = nullptr;
	}
};

void Free(node *root)
{
	if (root == nullptr)
		return;
	//Free(root);

	Free(root->left);
	Free(root->right);
	delete root;

}

//void Free1(Tree T)
//{
//	if (T.root == nullptr)
//		return;
//	Free(T.root->left);
//	Free(T.root->right);
//	Free(T.root);
//}

//int LeftOf(const int value, const Tree &T)
//{
//	return value < T.root->value;
//}
//
//int RightOf(const int value, const Tree &T)
//{
//	return value > T.root->value;
//}
//
//node* Insert(Tree &T, const int data)
//{
//	if (!T.root)
//	{
//		node* temp = new node(data);
//		return temp;
//	}
//	if (LeftOf(data, T))
//		T.root->left = Insert(T.root->left, data);
//	else if (RightOf(data, T))
//		T.root->right=Insert()
//}

//int Insert(node* &p, int data)
//{
//	if (p)
//	{
//		if (p->value == data)
//			return 0;
//		if (p->value > data)
//			return Insert(p->left, data);
//		else
//			return Insert(p->right, data);
//	}
//	p = new node();
//	if (p == nullptr)
//		return -1;
//	p->value = data;
//	p->left = p->right = nullptr;
//	return 1;
//}

void Insert(node *&root, const int x)
{
	if (root == NULL)
	{
		root = new node();
		root->value = x;
		root->right = NULL;
		root->left = NULL;
	}
	else
	{
		if (root->value <= x)
			Insert(root->left, x);
		else
			Insert(root->right, x);
	}
}

node* Search(node*p, int value)
{
	if (p)
	{
		if (p->value == value)
			return p;
		if (p->value > value)
			return Search(p->left, value);
		else
			return Search(p->right, value);
	}
	return nullptr;
}

void Print_LNR(node *p)
{
	if (p)
	{
		Print_LNR(p->left);
		cout << p->value << " ";
		Print_LNR(p->right);
	}
}

void CountHD(node *p, int hd, map<int, vector<int>>& mp)
{
	if (p == nullptr)
		return;
	mp[hd].push_back(p->value);
	CountHD(p->left, hd - 1, mp);
	CountHD(p->right, hd + 1, mp);
}

void Print_Cau4(node* p)
{
	if (p)
	{
		char s = 'A';
		map<int, vector<int>> mp;
		CountHD(p, 0, mp);
		map<int, vector<int>>::iterator it;
		for (it = mp.begin(); it != mp.end(); it++)
		{
			cout << s++ << ". ";
			for (int i = 0; i < it->second.size(); i++)
				cout << it->second[i] << " ";
			cout << endl;
		}

	}
}

int main()
{
	Tree T;
	/*Insert(T.root, 44);
	Insert(T.root, 18);
	Insert(T.root, 88);
	Insert(T.root, 13);
	Insert(T.root, 37);
	Insert(T.root, 59);
	Insert(T.root, 108);
	Insert(T.root, 15);
	Insert(T.root, 23);
	Insert(T.root, 40);
	Insert(T.root, 55);
	Insert(T.root, 71);*/

	Insert(T.root, 1);
	Insert(T.root->left, 2);
	Insert(T.root->right, 3);
	Insert(T.root->left->left, 4);
	Insert(T.root->left->right, 5);
	Insert(T.root->right->left, 6);
	Insert(T.root->right->right, 7);
	Insert(T.root->right->left->right, 8);
	Insert(T.root->right->right->right, 9);

	//Insert(T.root, 30);
	//Print_LNR(T.root);
	cout << endl;
	/*node *temp = Search(T.root, 69);
	cout << temp->value;*/
	Print_Cau4(T.root);
	Free(T.root);
	system("pause");
}