Ávores binárias em C
Publicado por Lucas Novaes 27/06/2007
[ Hits: 20.291 ]
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; }
Jogo do adivinha para descontrair..
Utilizando arrays, funções e arquivos de texto
Validador de Cartão de Credito
Crie alias para as tarefas que possuam longas linhas de comando - bash e zsh
Criando um gateway de internet com o Debian
Configuração básica do Conky para mostrar informações sobre a sua máquina no Desktop
Aprenda a criar músicas com Inteligência Artificial usando Suno AI
Entendendo o que é URI, URL, URN e conhecendo as diferenças entre POST e GET
Como instalar o XFCE4-terminal na sua distribuição Linux e integrá-lo ao sistema
Como instalar o Tilix Terminal no Gnome e usá-lo como menu drop-down ao estilo Quake
Instalando Grub Customizer no Ubuntu 24.04
Microfone não está conectado no Ubuntu 22.04 (1)
COMANDO PVCREATE NÃO ENCONTRADO (2)
Como adicionar módulo de saúde da bateria dos notebooks Acer ao kernel... (43)
BUG ao atualizar pacotes libglib2.0-0 libglib2.0-bin libglib2.0-data (0)