Ávores binárias em C
Publicado por Lucas Novaes 27/06/2007
[ Hits: 20.286 ]
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; }
Biblioteca do Calculo do Retangulo em C++
Ordenar vetor com algoritmo Insertion Sort
Atenção a quem posta conteúdo de dicas, scripts e tal (2)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como criar um robot em NTSL (Nelogica Trading System Language) para Profitchart
Use o Google PageSpeed Insights para verificar um site
Como Atualizar Fedora 39 para 40
Sistema da Coréia do Norte - Red Star OS (20)
filtrar só as pastas onde tem arquivo (4)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (31)
Instalacao Manjaro em notebook com placa de video hibrida [RESOLVIDO] (2)