// AVL.cpp: Reconstrucion del codigo original AVL.
// por Adrian "Sir. Dark Solink" DS
//
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

struct nodo{
	int bal;//balance
	int num;//numero
	nodo*izq;//apuntador izquier
	nodo*der;
};
nodo*HEAD;// apuntador del tipo nodo
nodo*crear(int b)/*crea un nodo*/{
	nodo*p=new nodo;
	p->bal=0;
	p->num=b;
	p->izq=NULL;
	p->der=NULL;
	return p;
}
int altura(nodo*p)/*utilisado para calcular el balance del nodo calculando la altura del mismo*/{
	if(p){
		if((!p->izq)&&(!p->der))
			return 0;
		int a=altura(p->izq);
		int b=altura(p->der);
		if(a>b)
			return a+1;
		else
			return b+1;
	}
	return 0;
}
int bal(nodo*p)/*calcula el balance de cada nodo para notificar al programa si debe hacer las rotaciones*/{
	int a=0; int b=0; int c=0;
	if(p->izq)
		a=altura(p->izq)+1;
	if(p->der)
		b=altura(p->der)+1;
	c=b-a;
	return c;
}
nodo*rotII(nodo*p)/*realiza la rotacion izquierda-izquierda*/{
	nodo*aux=p->izq;
	p->izq=aux->der;
	aux->der=p;
	p=aux;
	p->bal=bal(p);
	p->izq->bal=bal(p->izq);
	p->der->bal=bal(p->der);
	return p;
}
nodo*rotID(nodo*p)/*realiza la rotacion izquierda derecha*/{
	nodo*aux=p->izq;
	nodo*aux2=aux->der;
	p->izq=aux2->der;
	aux->der=aux2->izq;
	aux2->izq=aux;
	aux2->der=p;
	p=aux2;
	p->bal=bal(p);
	p->izq->bal=bal(p->izq);
	p->der->bal=bal(p->der);
	return p;
}
nodo*rotDD(nodo*p)/*realiza la rotacion derecha-derecha*/{
	nodo*aux=p->der;
	p->der=aux->izq;
	aux->izq=p;
	p=aux;
	p->bal=bal(p);
	p->izq->bal=bal(p->izq);
	p->der->bal=bal(p->der);
	return p;
}
nodo*rotDI(nodo*p)/*realiza la rotacion derecha-izquierda*/{
	nodo*aux=p->der;
	nodo*aux2=aux->izq;
	p->der=aux2->izq;
	aux->izq=aux2->der;
	aux2->der=aux;
	aux2->izq=p;
	p=aux2;
	p->bal=bal(p);
	p->izq->bal=bal(p->izq);
	p->der->bal=bal(p->der);
	return p;
}
void rot(nodo*p,nodo*j)/*invoca las rotaciones segun sea el caso de los balanceos de los nodos involucrados*/{
	if (p->bal==-2)
		if((p->izq->bal==-1)||(p->izq->bal==0))
			if(p==HEAD)
				HEAD=rotII(p);
			else
				if(p==j->izq)
					j->izq=rotII(p);
				else
					j->der=rotII(p);
		else
			if(p==HEAD)
				HEAD=rotID(p);
			else
				if(p==j->izq)
					j->izq=rotID(p);
				else
					j->der=rotID(p);
	else
		if(p->bal==2)
			if((p->der->bal==1)||(p->der->bal==0))
				if(p==HEAD)
					HEAD=rotDD(p);
				else
					if(p==j->izq)
						j->izq=rotDD(p);
					else
						j->der=rotDD(p);
			else
				if(p==HEAD)
					HEAD=rotDI(p);
				else
					if(p==j->izq)
						j->izq=rotDI(p);
					else
						j->der=rotDI(p);
}
void arbavl(int b,nodo*p,nodo*t,nodo*j,int c)/*inserta el numero en el arbol en donde corresponde*/{
	if((p)&&(p->num==b))
		c=1;
	if(HEAD==NULL)
		HEAD=crear(b);
	else
		if(!p)
			if(b<t->num)
				t->izq=crear(b);
			else
				t->der=crear(b);
		else{
			if(b<p->num){
				j=t;
				t=p;
				arbavl(b,p->izq,t,j,c);
			}
			else{
				j=t;
				t=p;
				arbavl(b,p->der,t,j,c);
			}
			if(c==1)
				if(p==HEAD)
					cout<<"ese numero es repetido"<<endl;
			if(c!=1){
				p->bal=bal(p);
				rot(p,j);
			}
	}
}
void inorden(nodo*p)/*imprime el arbol en inorden*/{
	if(p){
		inorden(p->izq);
		cout<<p->num<<endl;
		inorden(p->der);
	}
}
void preorden(nodo*p) /*imprime el arbol en preorden*/{
	if(p){
		cout<<p->num<<endl;
		preorden(p->izq);
		preorden(p->der);
	}
}
void postorden(nodo*p)/*imprime el arbol en postorden*/{
	if(p){
		postorden(p->izq);
		postorden(p->der);
		cout<<p->num<<endl;
	}
}
void main(){
	while(1==1){
		system("CLS");
		int a;
		cout<<"bienvenidos ya que has agregado el primer numero escoge de las siguiente opicones"<<endl;
		cout<<"1) Agregar un numero al arbol"<<endl;
		cout<<"2) imprimir en preorden"<<endl;
		cout<<"3) imprimir en inorden"<<endl;
		cout<<"4) imprimir en postorden"<<endl;
		cout<<"5) salir"<<endl;
		cin>>a;
		switch (a){
			case 1:{
				system("CLS");
				int b; int c=0;
				cout<<"cual es el numero que quieres agregar"<<endl;
				cin>>b;
				nodo*p=HEAD;
				nodo*t=NULL;
				nodo*j=NULL;
				arbavl(b,p,t,j,c);
					}break;
			case 2:{
				system("CLS");
				cout<<"preorden"<<endl;
				preorden(HEAD);
				   }break;
			case 3:{
				system("CLS");
				cout<<"inorden"<<endl;
				inorden(HEAD);
				   }break;
			case 4:{
				system("CLS");
				cout<<"postorden"<<endl;
				postorden(HEAD);
				 }break;
		}
		if(a==5)
			break;
	}
}