Árvores Estrutura de dados

É uma estrutura de dados que herda as características das topologias em árvore. É conceitualmente diferente das listas encadeadas, no qual os dados se encontram numa sequência. Nas árvores os dados estão dispostos de forma hierárquica.

Uma árvore é composta por um conjunto de nós. Possui um elemento principal chamado raiz, que pode conter ligações para outros elementos, cada um destes forma uma nova subárvore. Estes elementos são denominados de ramos ou filhos, estes ramos levam a outros elementos que também possuem outros ramos. O elemento que não possui ramos é conhecido como folha e/ou Nó-terminal.

Observação: Grau é um número de subárvores de um nó.

Folha é um nó que possui grau zero, ou seja, não possui subárvores.

Filhos são as raízes das subárvores de um nó.

Nó não terminal - é um nó que não é uma folha e é diferente da raiz.

Formas de representação gráfica

Árvores Binárias

Uma árvore binária (binary tree) é um conjunto de registros que satisfaz certas condições. Os registros serão chamados nós (poderiam também ser chamados células). Cada nó possui um endereço e deve-se ter cautela para não confundir cada nó com seu endereço.

A árvore binária é caracterizada por:

Existe um nó especial denominado raiz;
Nenhum nó tem grau superior a dois, isto é, nenhum nó tem mais de dois filhos;
Existe um "senso de posição", ou seja, distingue-se entre uma subárvore esquerda e uma subárvore direita.

O atravessamento (ou caminhamento) de árvore é a passagem de forma sistemática por cada um dos seus nós.

Há diferentes formas de percorrer os nós de uma árvore:

Pré-Ordem ou Prefixa (Profundidade);
Em Ordem ou Infixa (Ordem Simétrica);
Pós Ordem ou Posfixa;

Pré-Ordem (Profundidade)

visitar a raiz (mostrar elemento)
percorrer subárvore esquerda
percorrer subárvore direita

Exemplo:

Em Ordem (Ordem Simétrica)

percorrer na subárvore esquerda
visitar a raiz (mostrar elemento)
percorrer na subárvore direita

Exemplo:

Pós Ordem

percorrer na subárvore esquerda
percorrer na subárvore direita
visitar a raiz (mostrar elemento)

Exemplo:

Neste artigo tentei explicar de uma forma bem simples e básica o conceito de árvore e árvore binária. Nos próximos artigos, explicarei os tipos de remoção em uma árvore.