// Strom.cpp 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

struct prvek {
		int key;
		string value;
		prvek * left;
		prvek * right;
	};


prvek * search (prvek * b, int k)
{
	while (b!=nullptr && b->key != k){
	   if (k < b->key)
		  b=b->left;
	   else 
		  b=b->right;
	}
	return b;
}

void insert0 (prvek * & branch, int k, string v)
{
	prvek * b = branch;
	prvek * last = NULL;
	while (b!=nullptr && b->key != k){
	   last = b;
	   if (k < b->key) b=b->left; else b=b->right;
	}
	if (b != NULL)
   	  b->value = v;
	else 
	{
		prvek * p = new prvek;
		p->key = k;
		p->value = v;
		p->left = NULL;
		p->right = NULL;
		if (last == NULL)
			branch = p;
		else if (k < last->key)
			last->left = p;
		else 
			last->right = p;
	}
}

prvek * find (prvek * b, int k)
{
	if (b == nullptr)
		return nullptr;
	else if (b->key == k)
	    return b;
	else if (k < b->key)
		return find (b->left, k);
	else 
		return find (b->right, k);
}

void insert (prvek * & b, int k, string v)
{
	if (b == nullptr){
	    prvek * p = new prvek;
		p->key = k;
		p->value = v;
		p->left = NULL;
		p->right = NULL;
		b = p;
	}
	else if (b->key == k)
		b->value=v;
	else if (k < b->key)
		insert (b->left, k, v);
	else 
		insert (b->right, k, v);
}

void write(prvek *b, int level = 1)
{
	if(b!=nullptr)
	{
		for (int i = 1; i < 4*level; i++)
			 cout << " ";
		cout << b->key << " " << b->value << endl;
		write(b->left, level+1);
		write(b->right, level+1);
	}
}

void write2 (prvek *b)
{
	if(b!=nullptr)
	{
		write2 (b->left);
		cout << "(" << b->key << "," << b->value << ") ";
		write2 (b->right);
	}
}

void write_key (prvek *b, int step)
{
	stringstream f;
	if (b != NULL)
	   f << b->key;
	string s = f.str ();
	while (s.length() < step)
		s = " " + s;
	cout << s;
}


void write_step (prvek *b, int step, int level)
{
	if (level == 1)
        write_key (b, step);
	else
	{
		if (b != NULL)
		{
   		   write_step (b->left, step, level-1);
		   write_step (b->right, step, level-1);
		}
		else
		{
		   write_step (NULL, step, level-1);
		   write_step (NULL, step, level-1);
		}
	}
}

void write3 (prvek *b)
{
	int step = 40;
	for (int i = 1; i <= 4; i++)
	{
		write_step (b, step, i);
		step /= 2;
		cout << endl;
	}
}

prvek * root;

int _tmain(int argc, _TCHAR* argv[])
{
	root = nullptr;

	insert (root, 7, "sedm");
	insert (root, 10, "");
	insert (root, 5, "");
	insert (root, 8, "osm");
	insert (root, 12, "");

	//prvek * p = search (root, 
	write (root);
	cout << "Setridene" << endl;
	write2 (root);
	cout << "----------" << endl;
	write3 (root);
	cout << "Hotovo" << endl;
	system ("pause");

	return 0;

	return 0;
}