Árvores: mudanças entre as edições
| Linha 1: | Linha 1: | ||
=Árvores= | =Árvores= | ||
Uma '''árvore binária''' é uma '''estrutura de dados''' formada por um conjunto finito de elementos ou '''nós'''. Uma árvore pode | Uma '''árvore binária''' é uma '''estrutura de dados''' formada por um conjunto finito de elementos ou '''nós'''. Uma árvore pode estar vazia ou pode ser formada por um nó chamado '''raiz''' e dois sub-conjuntos de elementos chamados '''sub-árvore esquerda''' e '''sub-árvore direita'''. As sub-árvores esquerda e direita são também árvores binárias e podem estar vazias <ref name="TENENBAUM">[[Mídia:EstruturaDadosC.pdf | TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe. Estruturas de dados usando C. Árvores, p. 323, Makron Books, 1995.]]</ref>. | ||
A figura ilustra uma '''árvore binária''' <ref name="TENENBAUM"/>: | A figura abaixo ilustra uma '''árvore binária''' <ref name="TENENBAUM"/>: | ||
[[Arquivo:ArvoreBinaria.png | 400px]] | [[Arquivo:ArvoreBinaria.png | 400px]] | ||
Na figura: | Na figura: | ||
*O nó raiz A tem duas sub-árvores B e C; | *O nó '''raiz''' A tem duas '''sub-árvores''' B e C; | ||
*O nó B tem duas sub-árvores D e E; | *O nó B tem duas sub-árvores D e E; | ||
*O nó C tem apenas a sub-árvore da direita F; | *O nó C tem apenas a sub-árvore da direita F; | ||
Edição das 17h11min de 11 de novembro de 2014
Árvores
Uma árvore binária é uma estrutura de dados formada por um conjunto finito de elementos ou nós. Uma árvore pode estar vazia ou pode ser formada por um nó chamado raiz e dois sub-conjuntos de elementos chamados sub-árvore esquerda e sub-árvore direita. As sub-árvores esquerda e direita são também árvores binárias e podem estar vazias [1].
A figura abaixo ilustra uma árvore binária [1]:
Na figura:
- O nó raiz A tem duas sub-árvores B e C;
- O nó B tem duas sub-árvores D e E;
- O nó C tem apenas a sub-árvore da direita F;
- O nó E tem apenas a sub-árvore da esquerda G;
- O nó F tem duas sub-árvores H e I;
- Os nós D, G, H e I não tem sub-árvores, portanto, são chamados folhas.
Se A tem duas sub-árvores B e C, diz-se que:
- A é pai de B e C;
- B é filho esquerdo de A;
- C é filho direito de A.
- B é irmão de C.
- Profundidade da árvore binária
- Numa árvore binária, o nó raiz é considerado como profundidade 0 (zero). As sub-árvores do nó raiz profundidade 1, e assim sucessivamente. No exemplo da figura, a árvore binária tem profundidade 3.
- Árvore estritamente binária
- Uma árvore é estritamente binária se todo nó que não for folha tenha as sub-árvores direita e esquerda não vazias.
- Árvore binária completa
- Uma árvore é binária completa se for uma árvore estritamente binária e todas as folhas estiverem na mesma profundidade.
Aplicações das árvores binárias
As árvores binárias são uma estrutura de dados útil quando precisam ser tomadas decisões bi-direcionais em cada ponto do processo. Por exemplo, suponha que queiramos encontrar repetições em uma lista de números. Uma maneira de fazer isto é comparar cada número com todos os que o precedem. Entretanto, isto pode envolver muitas comparações. Outra maneira é utilizar uma árvore binária [1].
- Exemplo
Suponha que temos a seguinte lista de números para verificar repetições:
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Neste caso, iniciamos a árvore com o primeiro número da lista como sendo o nó raiz. Na sequência, comparamos o próximo número com o número da raiz, se for igual é uma repetição. Se for menor, comparamos com a sub-árvore da esquerda. Se for maior, comparamos com a sub-árvore da direita. Se a sub-árvore estiver vazia, incluímos o número como filho desta sub-árvore, caso seja menor ou maior, da mesma forma que foi realizado no início.
Veja a árvore que seria construída neste exemplo:
Percorrendo uma árvore
Uma operação importante em uma árvore binária é percorrer todos os seus nós.
Diferentemente de uma lista, na qual os nós são percorridos de maneira linear, numa árvore, existem diferentes ordens para poder percorrê-la.
Um método bastante comum para percorrer uma árvore é a ordem esquerda-raiz-direita [2].
- Ordem esquerda-raiz-direita
- Nesta ordem, percorre-se primeiro a sub-árvore esquerda, na ordem esquerda-raiz-direita. Depois a raiz. E depois a sub-árvore direita, também na ordem esquerda-raiz-direita.
Exemplo de ordem de varredura esquerda-raiz-direita [2]:
5
/ \
3 8
/ / \
1 6 9
/ \ \
0 2 7
Implementação de árvores em linguagem C
Cada nó de uma árvore pode ser implementado em linguagem C como uma estrutura com três campos: um campo conteúdo, para guardar a informação deste nó, e dois campos tipo ponteiro que apontam para as sub-árvores direita e esquerda.
Declaração de um nó de uma árvore
typedef struct arvore {
int conteudo;
struct arvore *esq;
struct arvore *dir;
} arvore;
Referência: [2].
Note que a declaração do nó da árvore é recursiva, onde os ponteiros *esq e *dir apontam para estruturas do mesmo tipo que está sendo declarada.
Inserção em árvores binárias
void inserir(struct arvore *pRaiz, int numero){
if(*pRaiz == NULL){
* pRaiz = (struct No *) malloc(sizeof(struct No));
(*pRaiz)→pEsquerda = NULL;
(*pRaiz)→pDireita = NULL;
(*pRaiz)→numero = numero;
}else{
if(numero <(*pRaiz)→numero)
inserir(&(*pRaiz)→pEsquerda, numero));
else
inserir(&(*pRaiz)→pDireita, numero));
}
}
Referências
--Evandro.cantu (discussão) 09h43min de 11 de novembro de 2014 (BRST)
