#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include "arvBin.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->chave = chave;
   return novo;
}

void insereRaiz(NO** raiz, TIPOCHAVE chave) {
   *raiz = criaNo(chave);
}

void insereEsq(NO* pai, TIPOCHAVE chave) {
   NO* novo = criaNo(chave);
   pai->esq = novo;
}

void insereDir(NO* pai, TIPOCHAVE chave) {
   NO* novo = criaNo(chave);
   pai->dir = novo;
}

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){
         if(raiz->chave == chave){
            return raiz;
         }

         NO* esq = busca(raiz->esq, chave);

         if(esq != NULL){
            return esq;
         }

         return busca(raiz->dir, chave);
   }

   return NULL;
}

int main() {
   NO* raiz;
   inicializa(&raiz);
   insereRaiz(&raiz, 'C');
   insereEsq(raiz, 'B');
   insereDir(raiz, 'E');
   insereEsq(raiz->esq, 'A');
   insereEsq(raiz->dir, 'D');
   insereDir(raiz->dir, '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;
   }
}