Programar em C/Árvores binárias de Busca: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Linha 17:
 
Dado o conjunto S com mais de um elemento, existem várias ABB que resolvem o problema.
 
<syntaxhighlight lang="c" line="1">
//Demonstração |Parte do código em Linguagem C - Verificando se a arvore binária está ordenada
 
int contarNos(Arvore *a){
if(a == NULL)
return 0;
else
return 1 + contarNos(a->esq) + contarNos(a->dir);
}
 
int Verificar_Ordem(Arvore *a){
int vetor_ordenacao[contarNos(a)];
if(a != NULL){
Verificar_Ordem(a->esq);
vetor_ordenacao[i]=a->info;
i++;
 
Verificar_Ordem(a->dir);
}
 
for(i=0;i<=(contarNos(a));i++)
{
if(vetor_ordenacao[i]<=vetor_ordenacao[i+1])
continue;
else
return 1;
}
return 0;
}
 
</syntaxhighlight>
 
=== Elementos ===
Linha 40 ⟶ 72:
A busca começa examinando o nó raiz. Se a árvore está vazia, o valor procurado não pode existir na árvore. Caso contrário, se o valor é igual a raiz, a busca foi bem sucedida. Se o valor é menor do que a raiz, a busca segue pela subárvore esquerda. Similarmente, se o valor é maior do que a raiz, a busca segue pela subárvore direita. Esse processo é repetido até o valor ser encontrado ou a subárvore ser nula (vazia). Se o valor não for encontrado até a busca chegar na subárvore nula, então o valor não deve estar presente na árvore.
 
Desta forma se consegue utilizar a vantagem da arvore binária estar ordenada.<syntaxhighlight lang="c">
//funcao que localiza um determinado noh na arvore ordenada - Arvore de busca
 
int buscar_ordenada(Arvore *a, int num)
{
int direita, esquerda;
if(a==NULL)
return 0;
if(a->info==num) //Localizou o noh
{
return 1;
}
if(num<a->info) //Percorre pela esquerda, caso o numero seja menor do que a raiz
{
esquerda=buscar_ordenada(a->esq,num);
}
else
{
direita=buscar_ordenada(a->dir,num);
}
return esquerda+direita;
}
 
</syntaxhighlight>
 
=== Inserção ===
A busca do local a ser inserido o novo nó se inicia examinando a raiz. Se a árvore está vazia, é inserido o nó. Caso contrário, se o valor é menor do que a raiz, a percurso segue pela sub-árvore a esquerda. Introduz-se um nó novo na subárvore da esquerda se o valor novo for menor do que a raiz, ou na subárvore da direita se o valor novo for maior do que a raiz.<syntaxhighlight lang="c">
Arvore * inserir_noh(Arvore *a, int num)
{
if(a==NULL) //Se não houver nó
{
a = (Arvore *) malloc(sizeof(Arvore)); //cria
a->info=num; //Insere o valor
a->esq=NULL; //Cria filho esquerdo
a->dir=NULL; //Cria filho direito
}
else if(num<a->info) //Se o numero for menor do que a raiz, percorre a esquerda.
{
a->esq = inserir_noh(a->esq,num);
}
else
{
a->dir = inserir_noh(a->dir,num);
}
return a;
}
</syntaxhighlight>
 
=== Remoção ===