#include<iostream>
#include <math.h>

template<typename T>
class ChainTree
{
public:
	ChainTree();
	ChainTree(int size);
	~ChainTree();
	ChainTree(ChainTree<T> const&);
	ChainTree& operator =(ChainTree<T> const&);

	//prints left root right
	void pr(int i = 0);
	//prints left tree
	void prLeft();
	//prints right tree
	void prRight();

	T GetRoot();
private:
	int size;
	T* a;
	int* b;
	int* c;
	int rootIndex;
	void CreateChainTree(int i);
	void DeleteTree();
	void CopyTree(ChainTree<T> const&);
};

int main()
{
	int size;
	std::cout << "Vyvedete visochinata na durvoto: " << std::endl;
	std::cin >> size;
	ChainTree<int> ct(size);
	ChainTree<int>ct1;
	ct1 = ct;
	ct1.pr();
	std::cout << std::endl;
	ct1.prLeft();
	std::cout << std::endl;
	ct1.prRight();
	system("pause");
	return 0;
}

template<typename T>
ChainTree<T>::ChainTree()
{
}

template<typename T>
inline ChainTree<T>::ChainTree(int size)
{
	this->size = (int)pow(2, size);
	a = new T[this->size];
	b = new int[this->size];
	c = new int[this->size];
	for (size_t i = 0; i < this->size; i++)
	{
		a[i] = T();
		b[i] = -1;
		c[i] = -1;
	}
	int i = 0;
	CreateChainTree(i);
}

template<typename T>
ChainTree<T>::~ChainTree()
{
	DeleteTree();
}

template<typename T>
ChainTree<T>::ChainTree(ChainTree<T> const & other)
{
	CopyTree(other);
}

template<typename T>
ChainTree<T> & ChainTree<T>::operator=(ChainTree<T> const & other)
{
	if (this != &other)
	{
		DeleteTree();
		CopyTree(other);
	}
	return *this;
}

template<typename T>
void ChainTree<T>::pr(int i = 0)
{
	if (i > size)
	{
		return;
	}
	if (b[i] != -1)
	{
		pr(2 * i + 1);
	}
	else
	{
		std::cout << "none ";
	}
	if (i == rootIndex)
	{
		std::cout << a[rootIndex] << " ";
	}
	else
	{
		std::cout << a[i] << " ";
	}
	if (c[i] != -1)
	{
		pr(2 * i + 2);
	}
	else
	{
		std::cout << "none ";
	}
}

template<typename T>
void ChainTree<T>::prLeft()
{
	if (b[rootIndex] == -1)
	{
		std::cout << "none";
		return;
	}
	pr(2 * rootIndex + 1);
}

template<typename T>
void ChainTree<T>::prRight()
{
	if (c[rootIndex] == -1)
	{
		std::cout << "none";
		return;
	}
	pr(2 * rootIndex + 2);
}

template<typename T>
T ChainTree<T>::GetRoot()
{
	return a[rootIndex];
}

template<typename T>
void ChainTree<T>::CreateChainTree(int i)
{
	if (i > size)
	{
		return;
	}
	T x; char ch;
	std::cout << "root: " << std::endl;
	std::cin >> x;

	if (i == 0)
		rootIndex = i;
	a[i] = x;

	std::cout << "left BinTree of: " << x << " y/n? ";
	std::cin >> ch;
	if (ch == 'y')
	{
		b[i] = 2*i+1;
		CreateChainTree(2 * i + 1);
	}
	else
	{
		b[i] = -1;
	}

	std::cout << "right BinTree of: " << x << " y/n? ";
	std::cin >> ch;
	if (ch == 'y')
	{
		c[i] = 2 * i + 2;
		CreateChainTree(2 * i + 2);
	}
	else
	{
		c[i] = -1;
	}
}

template<typename T>
void ChainTree<T>::DeleteTree()
{
	delete a;
	delete b;
	delete c;
}

template<typename T>
void ChainTree<T>::CopyTree(ChainTree<T> const & other)
{
	this->rootIndex = other.rootIndex;
	this->size = other.size;
	this->a = new T[other.size];
	this->b = new int[other.size];
	this->c = new int[other.size];
	for (size_t i = 0; i < other.size; i++)
	{
		this->a[i] = other.a[i];
		this->b[i] = other.b[i];
		this->c[i] = other.c[i];
	}
}