Ávores binárias em C
Publicado por Lucas Novaes 27/06/2007
[ Hits: 20.450 ]
Homepage: http://c4blog.wordpress.com/
Implementação de algoritmos para a manipulação de uma árvore binária de busca na linuagem C.
Especificações:
1. Consultar se a árvore é vazia ou não
2. Inserir valor
3. Percurso em pré-ordem
4. Percurso em ordem
5. Percurso em pós-ordem
6. Consultar valor
7. Consultar valor com mais detalhes
8. Consultar o maior valor
9. Consultar o menor valor
10. Consultar quantidade de nós
11. Imprimir Árvore
12. Sair
/*Lucas Juan Nogueira Novaes || Aluno Ciencia da computação CEUT email p/ contato novaeslucas@hotmail.com*/ #include <stdio.h> #include <stdlib.h> #include <conio.h> int quantidadeNos = 0; typedef struct _no{ int chave; int cont; struct _no *esq, *dir, *pai; }no; no* auxPai = NULL; void vaziaArvore(no *raiz){ if (raiz == NULL){ printf(" A arvore esta vazia\n\n"); } else { printf(" A arvore nao esta vazia\n\n"); } } void insere (int x, no **p){ if (*p==NULL){ *p=(no *)malloc(sizeof(no)); (*p)->chave=x; (*p)->dir=NULL; (*p)->esq=NULL; (*p)->pai = auxPai; (*p)->cont=0; (*p)->cont++; } else{ if (x<(*p)->chave){ if((*p)->esq == NULL) auxPai = *p; insere(x, &(*p)->esq); } if(x>(*p)->chave){ if((*p)->dir == NULL) auxPai = *p; insere(x, &(*p)->dir); } if(x == (*p)->chave){ (*p)->cont++; return; } } } int contaNos(no *p){ if(p != NULL){ quantidadeNos ++; contaNos(p -> dir); contaNos(p -> esq); } return quantidadeNos; } no* busca(no *arvore, int x){ if (arvore == NULL) return NULL; if (x == arvore->chave) return arvore; if (x < arvore->chave) return busca(arvore->esq, x); else return busca(arvore->dir, x); } void consultarValor(no* raiz){ int num; no* aux; printf("Digite o numero procurado: "); scanf("%d", &num); aux = busca(raiz, num); if (aux == NULL) printf("Nao encontrado!\n"); else{ printf("Encontrado!\n"); printf("O numero %d foi repetido %d vezes\n", num, aux->cont); } } void consultarDetalhes(no* raiz){ int num; no* aux; printf("Digite o numero procurado: "); scanf("%d", &num); aux = busca(raiz, num); if (aux == NULL) printf("Nao encontrado!\n"); else{ printf("Encontrado!\n"); printf("O numero %d foi repetido %d vezes.\n", num, aux->cont); if(aux->pai == NULL){ printf("O No que contem o valor %d e a raiz da arvore.\n", num); if(aux->esq != NULL) printf("Valor contido no No filho a esquerda: %d\n", aux->esq->chave); if(aux->dir != NULL) printf("Valor contido no No filho a direito: %d\n", aux->dir->chave); } if((aux->esq == NULL)&&(aux->dir == NULL)&&(aux->pai != NULL)){ printf("O No que contem o valor %d e uma folha da arvore.\n", num); printf("Valor contido no No pai: %d\n", aux->pai->chave); } if(((aux->esq != NULL)||(aux->dir != NULL))&&(aux->pai != NULL)){ printf("O No que contem o valor %d e um no interno a arvore.\n", num); printf("Valor contido no No pai: %d\n", aux->pai->chave); if(aux->esq != NULL) printf("Valor contido no No filho a esquerda: %d\n", aux->esq->chave); if(aux->dir != NULL) printf("Valor contido no No filho a direito: %d\n", aux->dir->chave); } } } void imprime(no *p, int nivel){ int i; if(p == NULL) return; imprime(p->dir, nivel+1); for(i=0;i<nivel;i++) printf(" "); printf("%6d\n\n",p->chave); imprime(p->esq,nivel+1); } void consultaNivel(no *p){ int i, nivel; if(p == NULL) return; imprime(p->dir, nivel+1); for(i=0;i<nivel;i++) printf(" "); printf("%6d\n\n",p->chave); imprime(p->esq,nivel+1); } void preordem (no *arvore){ if(arvore != NULL){ printf("%d\n",arvore->chave); preordem(arvore->esq); preordem(arvore->dir); } } void emordem(no *arvore){ if(arvore != NULL){ emordem(arvore->esq); printf("%d\n",arvore->chave); emordem(arvore->dir); } } void posordem(no *arvore){ if(arvore != NULL){ posordem(arvore->esq); posordem(arvore->dir); printf("%d\n",arvore->chave); } } void maiorValor(no* raiz){ if((raiz->dir != NULL)&&(raiz->dir->chave > raiz->chave)) maiorValor(raiz->dir); else printf("Maior Valor: %d\n", raiz->chave); } void menorValor(no* raiz){ if((raiz->esq != NULL)&&(raiz->esq->chave < raiz->chave)) menorValor(raiz->esq); else printf("Menor Valor: %d\n", raiz->chave); } //int quantNos(no* raiz){ //int cont; // } int menu(){ int op; printf("\n>>>>>>>>>>MENU<<<<<<<<<<\n\n"); printf("1 - Consultar lista\n"); printf("2 - Inserir valor\n"); printf("3 - Imprimir pre ordem\n"); printf("4 - Imprimir in-ordem\n"); printf("5 - Imprimir pos ordem\n"); printf("6 - Procurar um numero\n"); printf("7 - Consulta detalhada\n"); printf("8 - Consultar maior valor\n"); printf("9 - Consultar menor valor\n"); printf("10 - Quantidades de nos da arvore\n"); printf("11 - Imprimir arvore\n"); printf("12 - Sair\n\n>>>>>>>>>>MENU<<<<<<<<<<\n\n\n"); printf("Digite sua opcao: "); scanf("%d", &op); return op; } int main(){ int n,a,b; no *raiz, *aux; raiz = NULL; int opcao; while(opcao!=12){ system("cls"); opcao = menu(); switch(opcao){ case 1: system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); vaziaArvore(raiz); printf(">>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); getch(); break; case 2: system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf("Digite -1 para terminar\n"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); do{ printf("Digite um numero: "); scanf("%d", &n); if(n!=-1){ insere(n, &raiz); } }while (n!=-1); system("cls"); printf(" (o)\n"); printf(" (o)(o)(o)\n"); printf(" ( ARVORE BINARIA )\n"); printf(" (o)(o)(o)(o)\n"); printf(" ) (\n"); printf(" __| |__\n\n\n"); imprime(raiz,0); getch(); break; case 3: system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf("------> Pre-Ordem <------\n"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); preordem(raiz); getch(); break; case 4: system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf("------> Em-Ordem <------\n"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); emordem(raiz); getch(); break; case 5: system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf("------> Pos-Ordem <------\n"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); posordem(raiz); getch(); break; case 6: system("cls"); printf("\n\nDigite o numero procurado: "); scanf("%d",&a); aux = busca(raiz,a); if (aux == NULL){ system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf(" Nao encontrado!\n"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); } else{ system("cls"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf(" Encontrado!\n"); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); } getch(); break; case 7: system("cls"); consultarDetalhes(raiz); getch(); break; case 8: system("cls"); maiorValor(raiz); getch(); break; case 9: system("cls"); menorValor(raiz); getch(); break; case 10: system("cls"); b=contaNos(raiz); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); printf(" A arvore possui %d nos!\n",b); printf("\n>>>>>>>>>>>>><<<<<<<<<<<<<\n\n"); getch(); break; case 11: system("cls"); printf("ARVORE BINARIA\n"); imprime(raiz,0); getch(); break; case 12: exit(0); break; default : system("cls"); printf("opcao nao existe! tente novamente"); getch(); break; } } system("PAUSE"); return 0; }
Mostra valores da tabela ascii
Controle de maior / menor de idade (por ano)
Ordenando linhas e colunas de matrizes
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Como renomear arquivos de letras maiúsculas para minúsculas
Imprimindo no formato livreto no Linux
Vim - incrementando números em substituição
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Preciso resolver um erro de DPKG (1)
Melhores Práticas de Nomenclatura: Pastas, Arquivos e Código (2)
Não to conseguindo resolver este problemas ao instalar o playonelinux (1)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta