Wikilivros
ptwikibooks
https://pt.wikibooks.org/wiki/Wikilivros:P%C3%A1gina_principal
MediaWiki 1.39.0-wmf.23
first-letter
Multimédia
Especial
Discussão
Utilizador
Utilizador Discussão
Wikilivros
Wikilivros Discussão
Ficheiro
Ficheiro Discussão
MediaWiki
MediaWiki Discussão
Predefinição
Predefinição Discussão
Ajuda
Ajuda Discussão
Categoria
Categoria Discussão
Tópico
Tópico discussão
Resumo
Resumo discussão
TimedText
TimedText talk
Módulo
Módulo Discussão
Gadget
Gadget talk
Gadget definition
Gadget definition talk
Topic
Programar em C/Árvores binárias
0
26238
479927
479323
2022-08-07T21:15:42Z
2804:14D:90AD:619C:5DFA:ED0C:9615:1E81
/* Pré-ordem */
wikitext
text/x-wiki
{{revisão}}
== Árvore binária ==
Uma árvore binária é uma estrutura de dados que pode ser representada como uma hierarquia onde cada elemento é chamado de nó. O nó inicial ou o primeiro elemento é chamado de raiz. Em uma árvore binária um elemento pode ter um máximo de dois filhos no nível inferior denominados como sub-árvore esquerda e sub-árvore direita.Um nó sem filhos é chamado de folha. A profundidade de um nó é a distância desse nó até a raiz e a distância entre a folha mais distante e a raiz é a altura da árvore.Um conjunto de nós com a mesma profundidade é denominado, nível da árvore.
==Struct==
<syntaxhighlight lang="C">
struct No
{
int numero;
struct No *esquerda;
struct No *direita;
};
typedef struct No No; //typedef permite ao programador definir um novo nome para um determinado tipo.
</syntaxhighlight>
==Iniciar==
<syntaxhighlight lang="C">
void criarArvore(No **pRaiz)
{
*pRaiz = NULL;
}
</syntaxhighlight>
==Inserção==
<syntaxhighlight lang="C">
void insercao(No **pRaiz, int numero2)
{
if (*pRaiz == NULL)
{
*pRaiz=(No *)malloc(sizeof (No));
(*pRaiz)->esquerda=NULL;
(*pRaiz)->direita=NULL;
(*pRaiz)->numero=numero2;
}
else
{
if (numero2 < ((*pRaiz)->numero))
{
insercao(&((*pRaiz)->esquerda), numero2);
}
else
{
insercao(&((*pRaiz)->direita), numero2);
}
}
}
</syntaxhighlight>
==Remoção==
<syntaxhighlight lang="C">
No *MaiorDireita(No **no)
{
if((*no)->direita != NULL)
{
return MaiorDireita(&(*no)->direita);
}
else
{
No *aux = *no;
if((*no)->esquerda != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da esquerda!
{
*no = (*no)->esquerda;
}
else
{
*no = NULL;
return aux;
}
}
}
No *MenorEsquerda(No **no)
{
if((*no)->esquerda != NULL)
{
return MenorEsquerda(&(*no)->esquerda);
}
else
{
No *aux = *no;
if((*no)->direita != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da direita!
{
*no = (*no)->direita;
}
else
{
*no = NULL;
}
return aux;
}
}
void remover(No **pRaiz, int numero){
if(*pRaiz == NULL){ // esta verificacao serve para caso o numero nao exista na arvore.
printf("Numero nao existe na arvore!");
getch();
return;
}
if(numero < (*pRaiz)->numero)
remover(&(*pRaiz)->esquerda, numero);
else
if(numero > (*pRaiz)->numero)
remover(&(*pRaiz)->direita, numero);
else{ // se nao eh menor nem maior, logo, eh o numero que estou procurando! :)
No *pAux = *pRaiz; // quem programar no Embarcadero vai ter que declarar o pAux no inicio do void! :[
if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){ // se nao houver filhos...
free(pAux);
(*pRaiz) = NULL;
}
else{ // so tem o filho da direita
if ((*pRaiz)->esquerda == NULL){
(*pRaiz) = (*pRaiz)->direita;
pAux->direita = NULL;
free(pAux); pAux = NULL;
}
else{ //so tem filho da esquerda
if ((*pRaiz)->direita == NULL){
(*pRaiz) = (*pRaiz)->esquerda;
pAux->esquerda = NULL;
free(pAux); pAux = NULL;
}
else{ //Escolhi fazer o maior filho direito da subarvore esquerda.
pAux = MaiorDireita(&(*pRaiz)->esquerda); //se vc quiser usar o Menor da esquerda, so o que mudaria seria isso:
pAux->esquerda = (*pRaiz)->esquerda; // pAux = MenorEsquerda(&(*pRaiz)->direita);
pAux->direita = (*pRaiz)->direita;
(*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
free((*pRaiz)); *pRaiz = pAux; pAux = NULL;
}
}
}
}
}
</syntaxhighlight>
===Em ordem===
<syntaxhighlight lang="C">
void exibirEmOrdem(No *pRaiz){
if(pRaiz != NULL){
exibirEmOrdem(pRaiz->esquerda);
printf("\n%i", pRaiz->numero);
exibirEmOrdem(pRaiz->direita);
}
}
</syntaxhighlight>
===Pré-ordem===
<syntaxhighlight lang="C">
void PreOrdem(No *Raiz){
if(Raiz){
printf("\n%d", \t" Raiz->dados);
PreOrdem(Raiz->esquerda);
PreOrdem(Raiz->direita);
}
}
</syntaxhighlight>
===Pós-ordem===
<syntaxhighlight lang="C">
void exibirPosOrdem(No *pRaiz){
if(pRaiz != NULL){
exibirPosOrdem(pRaiz->esquerda);
exibirPosOrdem(pRaiz->direita);
printf("\n%i", pRaiz->numero);
}
}
</syntaxhighlight>
==Contar nós==
<syntaxhighlight lang="C">
int contarNos(No *pRaiz){
if(pRaiz == NULL)
return 0;
else
return 1 + contarNos(pRaiz->esquerda) + contarNos(pRaiz->direita);
}
</syntaxhighlight>
==Contar folhas==
<syntaxhighlight lang="C">
int contarFolhas(No *pRaiz){
if(pRaiz == NULL)
return 0;
if(pRaiz->esquerda == NULL && pRaiz->direita == NULL)
return 1;
return contarFolhas(pRaiz->esquerda) + contarFolhas(pRaiz->direita);
}
</syntaxhighlight>
==Altura da árvore==
<syntaxhighlight lang="C">
int maior(int a, int b){
if(a > b)
return a;
else
return b;
}//maior
int altura(No *pRaiz){
if((pRaiz == NULL) || (pRaiz->esquerda == NULL && pRaiz->direita == NULL))
return 0;
else
return 1 + maior(altura(pRaiz->esquerda), altura(pRaiz->direita));
}
</syntaxhighlight>
==Buscar elemento na árvore==
<syntaxhighlight lang="c">
typedef int bool;
#define false 0;
#define true 1;
bool find(int element)
{
// Procura o elemento na árvore
// O(log n)
Node* temp = root;
int parar=0;
if(root==NULL){
return false;
}else if(temp->left== NULL && temp->right==NULL){
if(temp->value == element){
return true;
}else{
return false;
}
}else if(temp->value==element){
return true;
}else{
while(parar==0){
if(temp->value < element){
if(temp->left == NULL){
parar++;
if (temp->value==element){
break;
return true;
}else{
return false;
}
}else{
temp=temp->right;
if (temp->value== element){
return true;
break;
}
}
}else if(temp->value > element){
if(temp->right== NULL){
parar++;
if (temp->value==element){
return true;
break;
}else{
return false;
}
}else{
temp=temp->left;
if (temp->value== element){
return true;
break;
}
}
}
}
}
}
</syntaxhighlight>
==Estrutura Completa==
{{AutoCat}}
92phlf6a2yydquvgjhfuxaudy6omn9l