#include <iostream.h>
//#include <stdlib.h> // for exit,NULL, if iostream not included

class node
{   public:
	node *left;
	int info;
	node *right;
};

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
//*       F U N C T I O N   G E N T R E E                   *
//      This generates a tree.  n is a small positive integer
//	specifying an upper bound on the number of nodes
//	of the tree.  The nodes can have two children, and
//	an information field.  The information field is 
//*	given a sequential node number.                     *
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
node *gentree(int n, int & numnode)
{	node *t;
	t = new node;
	t->info = ++numnode; //numnode is the unique number
		     //stored in each node after its creation
	if (n<=2)  t->left = NULL;
	else       t->left = gentree(n/2,numnode);
	if (n<=2)  t->right = NULL;
	else	   t->right = gentree(n/2,numnode);
	return(t);
}

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
//*       P R O C E D U R E   T R E E P R I N T           *
//*	The information fields of the nodes of a tree
//	are printed so that the tree is rotated 90 degrees
//	counter-clockwise.  The nodes are given proper 
//*	depths.                                           *
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
void treeprint(node *t, int count)
{	int i;
	count++; //count serves as a counter of the depth
		 //of the node and permits the correct
		 //spacing before the node contents are printed.
	if (t!=NULL)
	{	treeprint(t->right,count);
		for (i=0;i<count;i++)
		   cout << "         " ;
		cout << t->info << endl;
		treeprint(t->left,count);
	}
	count--; 
}

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
//* main program
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
int main ()
{	node *root;
	int count,numnode;
//  (* initialization *)
	numnode = count = 0;
	root = gentree(16,numnode);
	treeprint(root, count);
	return 0;
}