#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 100

//Estrutura para armazenar o alfabeto para algoritmo e montar a arvore binaria
typedef struct arv{
	char c;
	int freq;
	int isleft;
	int codigo[10];
	struct arv *prox;
	struct arv *esq;
	struct arv *dir;
}Arv;
//Estrutura da tabela contendo as inforacoes dos cohdigos
typedef struct tabela{
	int codigo[20];
	char a;
}Tabela;
//cria uma lista de arvores com cabeça
Arv* cria_lst(){
	Arv* q = (Arv*)malloc(sizeof(Arv));
	q->c='\n';
	q->freq=max+1;
	q->esq = q->dir = NULL;
	q->prox = NULL;
	return q;
}
//insere as folhas na lista
Arv* lst_insereF(char a, int f, Arv* lis){ 
	Arv* t = (Arv*)malloc(sizeof(Arv));
	t->c = a;
	t->freq = f;
	t->prox = lis->prox;
	lis->prox = t;
	t->esq = t->dir = NULL;
	return lis;
}
//insere subarvores na lista
Arv* lst_insereA(Arv* a, Arv* lis){
	a->prox = lis->prox;
	lis->prox = a;
	return lis;
}
//imprime a arvore
void arv_imprime(Arv* a){ 
	if(!arv_vazia(a)){
        printf("(");
        printf("%c(%d)", a->c, a->isleft);
        
        if(a->esq==NULL)
			printf("()");
        if(a->dir==NULL)
			printf("()");
        arv_imprime(a->esq);
        
        
        arv_imprime(a->dir);
        printf(")");
	}
}
//cria uma subarvore correpondente a 'nao-folha' 
Arv* cria_arv(Arv *sae,Arv *sad){
	Arv* q = (Arv*)malloc(sizeof(Arv));
	q->c = '*';
	q->freq = sae->freq + sad->freq;
	
	q->esq = sae;
	q->dir = sad;
	
	return q;
}
//verifica se a lista com cabeca esta vazia
int vazia(Arv *lis){
    return (lis->prox==NULL);
}
//retira o menor elemento da lista criada com cada celula sendo uma arvore
Arv* retira_menor(Arv* lis){
	Arv *q=lis->prox, *menor = lis->prox, *ant=NULL;
	
	while(q->prox!=NULL){//ponteiro 'menor' pecorre a lista das arvores primarias
		if(menor->freq>q->prox->freq){
			menor = q->prox;
			ant = q;
		}
		q=q->prox;
	}
	
	if(menor==lis->prox){
        
        lis->prox=lis->prox->prox;
        
        return menor;
        
	}
	
	ant->prox = menor->prox;
	menor->prox=NULL;
	return menor;
	
}
//conta a frequencia do caracter digitado pelo usuario
Arv* contafreq(char *m,char a,Arv *lis){
	int i, freq=0;          
	if(a=='\n')
		return lis;
	for(i=0;i<=strlen(m);i++){
		if(m[i]==a){
			freq++;
			m[i]='\n';
		}
	}
	lis = lst_insereF(a,freq,lis);
	return lis;
}
//imprime a lista dos caracteres e suas respecitivas frequencias
void lst_imprime(Arv* lis){
	Arv *p;
	for(p = lis;p!=NULL; p=p->prox)
		printf("info = %c(%d)\n", p->c,p->freq) ;
}
//quantidade de sub arvores na lista de sub arvores
int Nos(Arv* lis){
    int i=0;
    while(lis!=NULL){
		i++;
		lis=lis->prox;
	}
    return i;
}
//insere no campo isleft caso a arvore sej colocada a direita ou a esqueda da subfolha
void Arv_left(Arv* A,Arv* sae, Arv *sad){
	if(A!=NULL&&A->esq!=NULL&&A->dir!=NULL){
		sae->isleft = 1;
		sad->isleft = 0;
		Arv_left(sae,sae->esq,sae->dir);
		Arv_left(sad,sad->esq,sad->dir);
	}
}
//estrutursa de uma lista
typedef struct lista{
	int cd;
	char a;
	struct lista *prox;
}Lista;

//imprime lista
void imprime(Lista* lis){
	while(lis!=NULL){
		printf("%c(%d) ", lis->a, lis->cd);
		lis = lis->prox;
	}
}
//herda o codigo da subarvore 'pai' para a subarvore 'filha'
void guardacodigo(Arv* v,Arv* sa,int n){
    int i;
    if(sa!=NULL){ 
		for(i=0;i<n;i++)
			sa->codigo[i] = v->codigo[i];
		sa->codigo[n] = sa->isleft;
		guardacodigo(sa,sa->esq,n+1);
		guardacodigo(sa,sa->dir,n+1);
	}
}

void criatabd(Tabela *tabd, Arv *v, int n){
	int i=0;
	if(v!=NULL){
        if(v->esq==NULL){
			while(v->codigo[i]==0||v->codigo[i]==1){
				tabd[n].codigo[i]=v->codigo[i];
				i++;
			}
			tabd[n].a = v->c;
			n++;
			
        }
		criatabd(tabd,v->dir,n);
	}
}

void criatabe(Tabela *tabe, Arv *v, int n){
	int i=0;
	if(v!=NULL){
        if(v->esq==NULL){
			while(v->codigo[i]==0||v->codigo[i]==1){
				tabe[n].codigo[i]=v->codigo[i];
				i++;
			}
			tabe[n].a = v->c;
			n++;
			
        }
        //system("pause");
		criatabe(tabe,v->esq,n);
	}    
} 
int main(){
    char mensagem[50];
    int i;
    Arv *lis =cria_lst(), *a;
    Tabela tabd[50], tabe[50];
    printf("Digite a mensagem: ");
    gets(mensagem);
    //conta a qte de caracter e usa a funcao para contar a frequencia dos caracteres
	for(i=0;i<strlen(mensagem);i++)
		lis = contafreq(mensagem,mensagem[i],lis);
	lst_imprime(lis);
	
	int j;
	for(i=0;i<50;i++){
		for(j=0;j<10;j++){
			tabe[i].codigo[j] = -5;
			tabd[i].codigo[j] = -5;
		}
	}
	while(Nos(lis->prox)>1){
		
		a = cria_arv(retira_menor(lis),retira_menor(lis));
		lis = lst_insereA(a,lis);
	}
	
	a = lis->prox;
	
	printf("\n\n\n");
	Arv_left(a,a->esq,a->dir);
	arv_imprime(a);
	guardacodigo(a->esq,a->esq,0);
	guardacodigo(a->esq,a->dir,0);
	criatabe(tabe,a->esq,0);
	criatabe(tabd,a->dir,0);
	i=0;
	
	while(tabd[0].codigo[i]==0||tabd[0].codigo[i]==1){
		printf("%d",tabd[0].codigo[i]);
		i++;
	}
	printf("\nCaracter: %c", tabd[0].a);
	
    //system("pause");
    return 0;
}