Ávores binárias em C
Publicado por Lucas Novaes 27/06/2007
[ Hits: 20.532 ]
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: Acerte o número (com níveis de dificuldade)
Equação do segundo grau em C++
Calculadora de equações de 2º grau versão 2 (com funções)
Função para escrita de um número em notação binária através de recursão
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
VMs e Interfaces de Rede desapareceram (11)
Instalação do drive do adaptador wiffi (7)