#include <iostream>
#include <cstdlib>
using namespace std;
template<class T>//template class
class Item
{
public:
        Item* left;//pointer on the left item
        Item* right;//pointer on the right item
		T data;//data variable
public:
	Item();//default constructor
	Item(T);//constractor(data)
	T getData();//get of data
	void setData(T);//set of data
};

template <class T>
Item<T>::Item()//default constructor
{
	this->left=NULL;
	this->right=NULL;
}

template <class T>
Item <T>::Item(T x)//constractor(<T>data=x)
{
	data=x;
	left=right=NULL;
}
template <class T>
T Item <T>::getData()//get of data
{
	return data;
}
template <class T>
void Item <T>::setData(T x)//set of data
{
	data=x;
}

#include "Item.h"

template<class T>
class BinaryTree
{
private:
	Item<T>* root;//unit of tree
public:
	BinaryTree(){root=NULL;};//default constractor
	BinaryTree(Item<T>);//constractor
	Item<T>* getRoot();//get pointer on the root of the tree

	void setRoot(Item<T> );//seting a new root of the tree (deleting the old root)
	void setLeft(BinaryTree<T> );//seting a left tree
	void setRight(BinaryTree<T> );//seting a right tree

	Item<T>* removeLeft();//removing of left child
	Item<T>* removeRight();//removing of right child

	void preorder();//tree preorder
	void trip_preorder(Item<T>*);//preorder service function
	void inorder();//tree inorder
	void trip_inorder(Item<T>*);//inorder service function
	void postorder();//tree inorder
	void trip_postorder(Item<T>*);//postorder service function
	void levelorder();//tree level order
	void trip_levelorder(Item<T>*);//levelorder service function
	bool isEmpty() const { return root==NULL; }//Checking if tree is empty (boolean function)

};

template<class T>
BinaryTree<T>::BinaryTree(Item<T> x)//constractor (<T>Item=x)
{
	Item<T>* tmp=new Item<T>(x);//creating the temporarry unit (data copying constructor)
	tmp->left=tmp->right=NULL;//childs=0
	root=tmp;//copying of tmp variable by the adrres
}

template<class T>
Item<T>* BinaryTree<T>::getRoot()//get pointer on the root of the tree
{
	return root;
}

template<class T>
void BinaryTree<T>::setRoot(Item<T>	item)//seting a new root of the tree (deleting the old root)
{
	Item<T>* tmp=new Item<T>(item);//creating the temporarry unit (data copying constructor)
	//seting the pointers on childs
	tmp->left=this->root->left;
	tmp->right=this->root->right;
	//seting the new root by copying the adrres
	this->root=tmp;
}

template<class T>
void BinaryTree<T>::setLeft(BinaryTree<T> tree)//seting a left tree
{
	this->root->left=tree.root;
}

template<class T>
void BinaryTree<T>::setRight(BinaryTree<T> tree)//seting a right tree
{

	this->root->right=tree.root;
}

template<class T>
Item<T>* BinaryTree<T>::removeLeft()//removing of left child  and returning of this child
{
	Item<T>* leftRoot=new Item<T>(root->left->data);
	leftRoot=root->left;
	this->root->left=NULL;
	return leftRoot;
}

template<class T>
Item<T>* BinaryTree<T>::removeRight()//removing of right child  and returning of this child
{
	Item<T>* rightRoot=new Item<T>(root->right->data);
	rightRoot=root->right;
	this->root->right=NULL;
	return rightRoot;
}

template<class T>
void BinaryTree<T>::inorder()//inorder function
{
	trip_inorder(root);//sending the root to service recursion trip_inorder function
}

template<class T>
void BinaryTree<T>::trip_inorder(Item<T>* walker)//recursion trip_inorder function
{
	/*
	left
	print
	right
	*/
	if(walker!=NULL)
	{
		if(walker->left)
		{
			trip_inorder(walker->left);
		}
		cout<<" "<<walker->data<<" ";
		if(walker->right)
		{
			trip_inorder(walker->right);
		}

	}
	else
		return;
}

template<class T>
void BinaryTree<T>::preorder()//preorder function
{
	trip_preorder(root);//sending the root to service recursion trip_preorder function
}

template<class T>
void BinaryTree<T>::trip_preorder(Item<T>* walker)
{
	/*
	print
	left
	right
	*/
	if(walker!=NULL)
	{
		cout<<" "<<walker->data<<" ";
		if(walker->left)
		{
			trip_preorder(walker->left);
		}
		if(walker->right)
		{
			trip_preorder(walker->right);
		}
	}
	else
		return;
}

template<class T>
void BinaryTree<T>::postorder()//postorder function
{
	trip_postorder(root);//sending the root to service recursion trip_postorder function
}

template<class T>
void BinaryTree<T>::trip_postorder(Item<T>* walker)
{
	/*
	left
	right
	print
	*/
	if(walker!=NULL)
	{
		if(walker->left)
		{
			trip_postorder(walker->left);
		}
		if(walker->right)
		{
			trip_postorder(walker->right);
		}
		cout<<" "<<walker->data<<" ";
	}
	else
		return;
}

template<class T>
void BinaryTree<T>::levelorder()//level order function (print each level for left to right)
{
	cout<<" "<<root->data<<" ";//Printing of the root of the tree
	trip_levelorder(root);//sending the root to recursion levelorder function
}

template<class T>
void BinaryTree<T>::trip_levelorder(Item<T>* walker)
{
	if(walker!=NULL)
	{
		if(walker->left && walker->right)//If we have left and right child
		{
			cout<<" "<<walker->left->data<<" ";//print the left child
			cout<<" "<<walker->right->data<<" ";//print the right child
			trip_levelorder(walker->left),		//firstly sending the left child to recursion trip_levelorder
				trip_levelorder(walker->right); //And at the same time, through a SUPER MICROSECOND later, we are sending the right child to recursion trip_levelorder
		}
		else if(walker->left && !walker->right)//if we have left child and don't have right child
		{
			cout<<" "<<walker->left->data<<" ";//print the left child
			trip_levelorder(walker->left);//and sending the left child to the recursion trip_levelorder
		}
		else if(walker->right && !walker->left)//if we have right child and don't have left child
		{
			cout<<" "<<walker->right->data<<" ";//print the right child
			trip_levelorder(walker->right);////and sending the right child to the recursion trip_levelorder
		}
	}
	else
		return;
}

# include <iostream>
# include <string>
# include <cassert>
# include <stdlib.h>
#pragma once
typedef struct Node
{
	char x; //data
	Node *Next,*Head; //pointers on next and head of node
}Node;
using namespace std;
class Stack
{
public:
	char x; //data
    Node* list;//our Stack
public:
	Stack();//default constructor
	void push(char);//push new nod(data)
	char pop();//pop from stack
	char top();// top of the stack
	bool isEmpty();//checkin if stack is empty

	void mix_stack();//mix of the stack
	void Show();//printig all the stack
	void NodePrint(Node*);//printing unit of stack
	~Stack();//destructor
};

#include "Stack.h"

Stack::Stack()//default constructor
{
	list=new Node;
	assert(list);
	list->Head=NULL;
}

void Stack::push(char x)//push new nod(data=x)
{
	Node* temp=new Node;
	assert(temp);
	temp->x=x;
	temp->Next=list->Head;
	list->Head=temp;
}

char Stack::pop()//pop from stack
{
	char i;
	if(!isEmpty())
	{
		i=list->Head->x;
		Node* temp=list->Head->Next;
		delete list->Head;
		list->Head=temp;
		return i;
	}
	else
		cout<<"Error,stack is empty!"<<endl;
	return 0;
}

char Stack::top()// top of the stack
{
	if(!isEmpty())
		return list->Head->x;
	else
		cout<<"Error,stack is empty!"<<endl;
	return 0;
}

bool Stack::isEmpty()//checkin if stack is empty
{
	if(list-> Head==NULL )
		return true;
	return false;
}

void Stack::mix_stack()//mix of the stack(with 2 service stack's)
{
	Stack S1,S2;
	while(!this->isEmpty())
	{
		S1.push(this->pop());
	}
	while(!S1.isEmpty())
	{
		S2.push(S1.pop());
	}
	while(!S2.isEmpty())
	{
		this->push(S2.pop());
	}
}
void Stack::Show()//printig all the stack
{
	Node* temp=new Node;
	assert(temp);
	temp=list->Head;
	while(temp!=NULL)
	{
		cout<<temp->x<<endl;
		temp=temp->Next;
	}
	cout<<endl;
}

void Stack::NodePrint(Node* temp)//printing unit of stack
{
	cout<<temp->x;
}

Stack::~Stack()//destructor(while stack is not empty delete of each unit)
{
	while(!isEmpty())
	{
		Node* temp=list->Head->Next;
		delete list->Head;
		list->Head=temp;
	}
}