#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include "ABB.h"
using namespace std;

void inicializa(NO** raiz) {
   *raiz = NULL;
}

bool vazia(NO* raiz) {
   return raiz == NULL;
}

int max(int a, int b) {
   return a > b ? a : b;
}

int altura(NO* raiz) {
   if(raiz == NULL){
      return -1;
   }

   if(raiz->esq == raiz->dir) {
      return 0;
   }

   int left = altura(raiz->esq);
   int right = altura(raiz->dir);
   return max(left, right) + 1;
}

NO* criaNo (TIPOCHAVE chave) {
   NO* novo = (NO*) malloc(sizeof(NO));
   novo->esq = NULL;
   novo->dir = NULL;
   novo->pai = NULL;
   novo->chave = chave;
   return novo;
}

void insere(NO** raiz, TIPOCHAVE chave) {
   if(*raiz == NULL){
      NO* no = criaNo(chave);
      *raiz = no;
   } else if(chave < (*raiz)->chave){
      insere(&((*raiz)->esq), chave);
   } else {
      insere(&((*raiz)->dir), chave);
   }
}

void imprimePreOrdem(NO* raiz) {
   if(raiz != NULL) {
      cout << raiz->chave << " ";
      imprimePreOrdem(raiz->esq);
      imprimePreOrdem(raiz->dir);
   }
}

void imprimePosOrdem(NO* raiz) {
   if(raiz != NULL) {
      imprimePosOrdem(raiz->esq);
      imprimePosOrdem(raiz->dir);
      cout << raiz->chave << " ";
   }
}

void imprimeEmOrdem(NO* raiz) {
   if(raiz != NULL) {
      imprimeEmOrdem(raiz->esq);
      cout << raiz->chave << " ";
      imprimeEmOrdem(raiz->dir);
   }
}

NO* busca(NO* raiz, TIPOCHAVE chave) {
   if(raiz == NULL) {
      return NULL;
   } else if(raiz->chave == chave) {
       return raiz;
   } else if(raiz->chave < chave) {
      return busca(raiz->dir,chave);
   } else {
      return busca(raiz->esq, chave);
   }
}

void rotacionaEsq(NO* no) {
   NO* vo  = no->pai;
   NO* fio = no->dir;
   no->dir = fio->esq;
   fio->esq->pai = no;
   fio->esq = no;
   no->pai = fio;

   if(vo->dir == no) {
      vo->dir = fio;
   } else {
      vo->esq = fio;
   }

   fio->pai = vo;
}

void rotacionaDir(NO* no) {

}

int main() {
   NO* raiz;
   inicializa(&raiz);
   insere(&raiz, 'C');
   insere(&raiz, 'B');
   insere(&raiz, 'E');
   insere(&raiz, 'A');
   insere(&raiz, 'D');
   insere(&raiz, 'F');

   cout << "Pré-ordem: ";
   imprimePreOrdem(raiz);
   cout << endl;
   cout << "Em-ordem: ";
   imprimeEmOrdem(raiz);
   cout << endl;
   cout << "Pós-ordem: ";
   imprimePosOrdem(raiz);
   cout << endl;
   cout << "Altura: " << altura(raiz) << endl;

   char v[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

   for(int i = 0; i < 7; i++) {
      cout << "busca " << v[i] << ": "
           << (busca(raiz, v[i]) != NULL ? "ACHOU" : "NÃO ACHOU")
           << endl;
   }

   
}