#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
//------------Lista
typedef struct CelulaLista * ApontadorLista;
struct DadosLista{
int CHAVE;
};
struct CelulaLista{
DadosLista REG;
ApontadorLista PROX;
};
struct Lista{
ApontadorLista PRI;
ApontadorLista ULT;
int TAM;
};
void FLVazia (Lista *l){
l->PRI = NULL;
l->ULT = l->PRI;
l->TAM = 0;
}
int Vazia (Lista l){
return (l.PRI == NULL);
}
int Tamanho (Lista l){
return (l.TAM);
}
void InserirLista (DadosLista r, Lista *l){
ApontadorLista aux;
aux = (ApontadorLista) malloc (sizeof(CelulaLista));
if(aux == NULL){
cout<<"Erro, sem memoria para inserir";
return;
}
aux->REG = r;
aux->PROX = NULL;
l->TAM++;
if(Vazia(*l)){
l->PRI = aux;
l->ULT = l->PRI;
}
else{
l->ULT->PROX = aux;
l->ULT = aux;
}
}
void Retirar(Lista *l, int chave){
ApontadorLista aux, aux_ant;
if (Vazia (*l)){
cout<<"Lista Vazia!";
return;
}
aux = l->PRI;
if(aux==l->ULT){
if(chave == aux->REG.CHAVE){
cout<<"Chave Excluida";
free(aux);
FLVazia(l);
return;
}
else{
cout<<"Chave não encontrada";
return;
}
}
if(chave == l->PRI->REG.CHAVE){
l->PRI=aux->PROX;
cout<<"Chave Excluida";
free(aux);
l->TAM--;
return;
}
aux_ant=aux;
aux=aux->PROX;
while(aux!=NULL){
if(chave == aux->REG.CHAVE){
if(aux == l->ULT){
aux_ant->PROX = NULL;
l->ULT = aux_ant;
l->TAM--;
free(aux);
cout<<"Chave excluida";
return;
}
aux_ant->PROX = aux->PROX;
l->TAM--;
free(aux);
cout<<"Chave excluida";
return;
}
aux_ant=aux;
aux=aux->PROX;
}
cout<<"Chave não encontrada";
}
void MostrarLista(Lista *l, int *vetor){
int i=0;
ApontadorLista aux;
aux = l->PRI;
while(aux!=NULL){
cout<<aux->REG.CHAVE<<"\n";
vetor[i]=aux->REG.CHAVE;
i++;
aux = aux->PROX;
}
}
void Consultar(Lista *l, int chave){
ApontadorLista aux;
if(Vazia(*l)){
cout<<"Lista Vazia";
return;
}
aux = l->PRI;
while(aux!=NULL){
if(aux->REG.CHAVE == chave){
cout<<"Chave Encontrada: "<<aux->REG.CHAVE;
return;
}
aux = aux->PROX;
}
}
//------------Árvore
typedef struct CelulaArvore *ApontadorArvore;
struct DadosArvore{
int CHAVE;
};
struct CelulaArvore {
DadosArvore REG;
ApontadorArvore ESQ, DIR;
};
void InserirArvore(ApontadorArvore raiz, DadosArvore r){
ApontadorArvore novo;
if(r.CHAVE < raiz->REG.CHAVE){
if(raiz->ESQ == NULL){
novo = (ApontadorArvore) malloc(sizeof(CelulaArvore));
raiz->ESQ = novo;
novo->REG = r;
novo->ESQ = novo->DIR = NULL;
}else
InserirArvore(raiz->ESQ, r);
}else if(r.CHAVE > raiz->REG.CHAVE){
if(raiz->DIR== NULL){
novo = (ApontadorArvore) malloc(sizeof(CelulaArvore));
raiz->DIR = novo;
novo->REG = r;
novo->ESQ = novo->DIR = NULL;
}else
InserirArvore(raiz->DIR, r);
}else
cout<<"Chave duplicada";
getch();
}
int ContaNodos(ApontadorArvore raiz) {
if (raiz == NULL)
return 0;
return ContaNodos(raiz->ESQ) + ContaNodos(raiz->DIR) + 1;
}
void BuscaOrdem(ApontadorArvore raiz){
if(raiz == NULL)
return;
BuscaOrdem(raiz->ESQ);
cout<<"\n"<<raiz->REG.CHAVE;
BuscaOrdem(raiz->DIR);
}
//------------Main
int main(){
ApontadorArvore RAIZ = NULL;
DadosArvore REG, vetArvore[10];
int OP,CHAVE, vetor[10];
DadosLista D;
Lista L;
DadosLista vet[10];
FLVazia(&L);
do{
system("cls");
cout<<"\n1-Inserir";
cout<<"\n2-Listar";
cout<<"\n3-Tamanho";
cout<<"\n4-Sair da lista";
cout<<"\nDigite a sua opcao:" ;
cin>>OP;
switch(OP){
case 1:
cout<<"\nDigite uma chave: ";
cin>>D.CHAVE;
InserirLista(D,&L);
break;
case 2:
MostrarLista(&L, vetor);
getch();
break;
case 3:
cout<<"\nTamanho: "<<Tamanho(L);
getch();
break;
case 4:
cout<<"\nFIM!";
getch();
break;
default:
cout<<"Opcao invalida!";
break;
}
}while(OP!=4);
//Passa os dados do vetor do tipo int para o tipo DadosArvore
for (int i=0; i<10; i++){
vetArvore[i].CHAVE=vetor[i];
}
//Passa os dados do vetor para uma árvore.
for (int j=0; j<10; j++){
while(vetArvore[j].CHAVE != 0){
if(RAIZ == NULL){
RAIZ = (ApontadorArvore) malloc(sizeof(CelulaArvore));
RAIZ->REG = vetArvore[j];
RAIZ->ESQ = RAIZ->DIR = NULL;
getch();
}
else{
InserirArvore(RAIZ, vetArvore[j+1]);
}
}
}
cout<<"A arvore tem "<<ContaNodos(RAIZ)<<" nodos";
cout<<"\n\n Busca Ordenada: \n";
BuscaOrdem(RAIZ);
getch();
MostrarLista(&L, vetor);
getch();
return 0;
}