// TREE.cpp : Defines the entry point for the console application. 

/* 
В прямом порядке:
Попасть в корень 
Пройти в прямом порядке левое поддерево 
Пройти в прямом порядке правое поддерево

В симметричном порядке: 
Пройти в симметричном порядке левое поддерево 
Попасть в корень 
Пройти в симметричном порядке правое поддерево

В обратном порядке: 
Пройти в обратном порядке левое поддерево 
Пройти в обратном порядке правое поддерево 
Попасть в корень*/

#include "stdafx.h" 
#include <stack> 
#include "string.h"
#include "math.h"
using namespace std; 

struct Node 
{ 
int value; 
Node *pleft, *pright; 
}; 

class Tree 
{public: 
Tree() 
{ 
root = NULL; 
} 
Node*& get_root()
{
	return root;
}
void inf_walkL(Node*& doko)
{
	RoutSt.push(doko);
	while(RoutSt.empty() == false)
	{
		Node *h;		
		h = RoutSt.top();
		RoutSt.pop();		
		
		if((h->pleft ==  NULL)&&(h->pright ==  NULL)){printf("%d ",h->value);}else{		
	
		Node *tmpH;
		tmpH = new Node;
		tmpH->value = h->value;
		tmpH->pleft=NULL;
		tmpH->pright=NULL;
		RoutSt.push(tmpH);

		if(h->pright != NULL){RoutSt.push(h->pright);}		
		if(h->pleft !=  NULL){RoutSt.push(h->pleft);}}
	}
}
void pref_walkL(Node*& doko)
{
	RoutSt.push(doko);
	while(RoutSt.empty() == false)
	{
		Node *h;		
		h = RoutSt.top();
		RoutSt.pop();		
		
		if((h->pleft ==  NULL)&&(h->pright ==  NULL)){printf("%d ",h->value);}else{
		if(h->pright != NULL){RoutSt.push(h->pright);}
	
		Node *tmpH;
		tmpH = new Node;
		tmpH->value = h->value;
		tmpH->pleft=NULL;
		tmpH->pright=NULL;
		RoutSt.push(tmpH);
		
		if(h->pleft !=  NULL){RoutSt.push(h->pleft);}}
	}
}
void direct_walkL(Node*& doko)
{
	RoutSt.push(doko);
	while(RoutSt.empty() == false)
	{
		Node *h;		
		h = RoutSt.top();
		RoutSt.pop();
		printf("%d ",h->value); 
		if (h->pright!=NULL){RoutSt.push(h->pright);}
		if (h->pleft!=NULL){RoutSt.push(h->pleft);}
	}
}
void inf_walk(Node*& doko)
{
  if (doko != NULL){  
  inf_walk(doko->pleft);  
  inf_walk(doko->pright);
  printf("%d ",doko->value);}
}
void pref_walk(Node*& doko)
{
  if (doko != NULL){  
  pref_walk(doko->pleft);
  printf("%d ",doko->value); 
  pref_walk(doko->pright);}
}
void direct_walk(Node*& doko)
{
  if (doko != NULL){
  printf("%d ",doko->value); 
  direct_walk(doko->pleft);
  direct_walk(doko->pright);}
}
void place_to_tree(Node* nNew, Node*& doko)
{
	if (doko == NULL){doko = nNew;}
	else
	{
		if (doko->value > nNew->value)
		{
			place_to_tree(nNew, doko->pleft);
		}else
		{
			place_to_tree(nNew, doko->pright);
		}
	}
}
void add_value(int val) 
{
	Node *newN; 
	newN = new Node; 
	newN->value = val; 
	newN->pleft = NULL; 
	newN->pright = NULL; 

	place_to_tree(newN,root);

} 
void AddNewElement(int val)
{
	Node *newN; 
	newN = new Node; 
	newN->value = val; 
	newN->pleft = NULL; 
	newN->pright = NULL; 

	Node *pcur,*prev;
    pcur = root;
	bool success,left;
	success = true;
	left = true;

	if (root==NULL){root = newN; success = false;}    

	while(pcur)
	{
		if (val < pcur->value){prev = pcur; pcur = pcur->pleft; left = true; }else{
			if (val > pcur->value){prev = pcur; pcur = pcur->pright; left = false;}
			else{if (val = pcur->value){success = false; break;}}
		  }
		
	}
	if (success){
		if(left){prev->pleft = newN;} else {prev->pright = newN;}
	}	
}
int* make_levelline(int &pos,int &lvl)
{
	stack <Node*> ChetnSt; 
	stack <Node*> NeChetnSt;
	int *line,prepos;
	line = new int[256];
	bool chetn = false;
	pos = 0;
	lvl = 0;
	NeChetnSt.push(root);
	bool allEmpty;
	allEmpty = false;


	while(!allEmpty)
	{
		if(chetn)
		{
			allEmpty = true;
			prepos = pos;
			while(!ChetnSt.empty())
			{
			  Node *h;		
		      h = ChetnSt.top();
		      ChetnSt.pop();

			  if(h!=NULL){
				  allEmpty = false;
				  line[pos]=h->value; pos++;
				  NeChetnSt.push(h->pleft);
				  NeChetnSt.push(h->pright);
				  }else
			  {
				  line[pos]=0; pos++;
				  NeChetnSt.push(NULL);
			      NeChetnSt.push(NULL);
			  }
			}
			chetn = false; lvl++;
		}
		else
		{
			allEmpty = true;
			prepos = pos;
			while(!NeChetnSt.empty())
			{
			  Node *h;		
		      h = NeChetnSt.top();
		      NeChetnSt.pop();

			  if(h!=NULL){
				  allEmpty = false;
				  line[pos]=h->value; pos++;
				  ChetnSt.push(h->pright);
				  ChetnSt.push(h->pleft);}else
			  {
				  line[pos]=0; pos++;
				  ChetnSt.push(NULL);
			      ChetnSt.push(NULL);
			  }
			}
			chetn = true; lvl++;
		}
	}
lvl--;
pos = prepos;
return line;
}
void DrawTree()
{
	int cpos,space;
	bool chetn;
	cpos = 0;
	chetn = false;
     
int *line,pos,lvl;
line = make_levelline(pos,lvl);

//printf("%d \n",lvl);
//for(int i=0; i<pos; i++)
//{printf("%d ",line[i]);}
//printf("\n");
	
	for(int i=0; i<lvl; i++)
	{		
		space = 40-i*5;
		while(space)
		{printf(" "); space--;}

		if(chetn)
		{
			space = pow(2.0,i);
			while(space)
			{
				printf("%d",line[cpos]);
				cpos++;
				space--;

				int space2 = (lvl-i)*2;
		        while(space2)
		        {printf(" "); space2--;}
			}
			printf("\n");
			chetn = false;
		}else
		{
			space = pow(2.0,i);
			int bufcpos;
			bufcpos = cpos+space-1;
			while(space)
			{
				printf("%d",line[bufcpos]);
				cpos++;
				bufcpos--;
				space--;

				int space2 = (lvl-i)*2;
		        while(space2)
		        {printf(" "); space2--;}
			}
			printf("\n");
			chetn = true;
		}


	}
}
private: 
Node *root; 
stack <Node*> RoutSt; 

}; 

int main() 
{ 
Tree MainTree; 
MainTree.AddNewElement(10);
MainTree.AddNewElement(9);
MainTree.AddNewElement(8); 
MainTree.AddNewElement(7); 
MainTree.AddNewElement(6); 
MainTree.AddNewElement(20); 
MainTree.AddNewElement(15);
MainTree.AddNewElement(14);
MainTree.AddNewElement(16);
MainTree.AddNewElement(21);
//           10
//        9       20
//     8       15    21 
//  7        14  16

MainTree.DrawTree();


printf("\nDR: ");
MainTree.direct_walk(MainTree.get_root());
printf("\n");
printf("DL: ");
MainTree.direct_walkL(MainTree.get_root());
printf("\n");
printf("PR: ");
MainTree.pref_walk(MainTree.get_root());
printf("\n");
printf("PL: ");
MainTree.pref_walkL(MainTree.get_root());
printf("\n");
printf("IR: ");
MainTree.inf_walk(MainTree.get_root());
printf("\n");
printf("IL: ");
MainTree.inf_walkL(MainTree.get_root());
printf("\n");


int i; 
scanf("%d",&i); 
return 0; 
}