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

#include "stdafx.h"

//arbore
typedef struct node {
	int key;
	int size;
	int niv;
	struct node *left;
	struct node *right;
} NodeT;

NodeT* createNode(int key) {
	NodeT *nod = (NodeT*)malloc(sizeof(NodeT));
	nod->left = NULL;
	nod->right = NULL;
	nod->niv = 0;
	nod->size = 1;
	nod->key = key;
	return nod;
}
NodeT* buildPBT(int *a,int first,int last,int niv) {
	if (first > last) return NULL;
	else {
		int mij = (first + last) / 2;
		NodeT *node = createNode(a[mij]);
		node->niv = niv;
		node->left = buildPBT(a, first, mij - 1,niv+1);
		node->right = buildPBT(a, mij + 1, last,niv+1);
		if (node->left != NULL && node->right != NULL)
			node->size = node->left->size + node->right->size + 1;
		if (node->left == NULL && node->right == NULL)
			node->size = 1;
		if (node->left == NULL && node->right != NULL)
			node->size = node->right->size + 1;
		if (node->left != NULL && node->right == NULL)
			node->size = node->left->size + 1;
		return node;
	}

}
NodeT* OSSelect(NodeT *T, int i) {
	int r;
	if (T->left == NULL)
		r = 1;
	else r = T->left->size + 1;
	if (i == r)
		return T;
	else if (i < r) return OSSelect(T->left, i);
	else return OSSelect(T->right, i - r);
}


//pretty-print
typedef struct nou {
	struct nou *next;
	NodeT *ptr;
}nodPretty;
nodPretty *prim, *ultim;
int niv;
int adaugareCoada(NodeT *p)
{
	nodPretty *q;
	q = (nodPretty*)malloc(sizeof(nodPretty));
	q->ptr = p;
	q->next = 0;
	if (!prim)
	{
		prim = q;
		ultim = q;
	}
	else
	{
		ultim->next = q;
		ultim = q;
	}
	return 1;
}
NodeT *extragereCoada()
{
	nodPretty *p;
	NodeT *q;
	if (!prim)
		return 0;
	p = prim;
	prim = prim->next;
	if (!prim)
		ultim = 0;
	q = p->ptr;
	free(p);
	return q;
}
int traversare(NodeT *rad)
{
	NodeT  *p;
	int i;
	prim = NULL;
	ultim = NULL;
	adaugareCoada(rad);
	do
	{
		p = extragereCoada();
		if (p!=NULL)
		{
			if (niv != p->niv)
			{
				printf("\n");
				niv = p->niv;
			}
			for (i = 0; i<6 / niv; i++)
				printf("   ");
			printf(" %d: size %d", p->key,p->size);
			adaugareCoada(p->left);
			adaugareCoada(p->right);
		}
	} while (p!=NULL || prim!=NULL);
	return 1;
}
void preorder(NodeT *p)
{
	if (p != NULL)
	{
		printf("%d ", p->key);
		preorder(p->left);
		preorder(p->right);
	}
}


int main()
{
	int a[13] = { 1,2,3,4,5,6,7,8,9,10,11,12,13};
	NodeT* T = buildPBT(a, 0, 12, 1);
	niv = T->niv;
	preorder(T);
	printf("\n");
	traversare(T);
	printf("\nSelectie: %d\n", OSSelect(T, 1)->key);
    return 0;
}