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

#define TIPOCHAVE char

typedef struct NO {
   TIPOCHAVE chave;
   struct NO *esq;
   struct NO *dir;
   struct NO *pai;
} NO;

void rotacionaEsq(NO* no);

void rotacionaDir(NO* no);

NO* busca(NO* raiz, TIPOCHAVE chave);

void inicializa(NO** raiz);

bool vazia(NO* raiz);

int altura(NO* raiz);

void insere(NO* pai, TIPOCHAVE chave);

void imprimePreOrdem(NO* raiz);

void imprimePosOrdem(NO* raiz);

void imprimeEmOrdem(NO* raiz);