ARVORE CONCEITOS

Árvore, no contexto da programação, engenharia de software e ciência da computação, é uma das mais importantes estruturas de dados não lineares. Herda as características das topologia em árvore. Conceitualmente diferente das listas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica, seus elementos se encontram "acima" ou "abaixo" de outros elementos da árvore.

São estruturas eficientes e simples em relação ao tratamento computacional, diferentemente dos grafos. Há inúmeros problemas no mundo real que podem ser modelados e resolvidos através das árvores. Estruturas de pastas de um sistema operacional, interfaces gráficas, bancos de dados e sites da internet são exemplos de aplicações de árvores.

Uma árvore é formada por um conjunto de elementos que armazenam informações chamados nodos (ou nós). Toda a árvore possui o elemento chamado raiz, que possui ligações para outros elementos denominados ramos ou filhos. Estes ramos podem estar ligados a outros elementos que também podem possuir outros ramos. O elemento que não possui ramos é conhecido como nó folha, nó terminal ou nó externo.

Formalmente, definimos uma árvore T como um conjunto finito de zero ou mais nodos tal que:
se o número de nodos = 0 temos uma árvore vazia, ou
se o número de nodos >0
   existe um nó especialmente denominado raiz de T
   os nós restantes formam m>0 conjuntos disjuntos p1,p2,p3......pm, cada um desses conjuntos é uma árvore em si, chamada subárvore da raiz de T, ou simplesmente subárvore.

Há diversas formas de representação de uma árvore: hierárquica, diagrama de inclusão, diagrama de barras, numeração por níveis, por aninhamento.

A hierárquica é parecida com um organograma de uma empresa, linhas unem dois nodos e indicam o relacionamento lógico entre eles. Tradicionalmente desenha-se a raiz na parte superior e todos os nodos subordinados na parte inferior, mas o contrário também é possível. Na figura ao lado, o item (a) é um exemplo desta representação.

Diagrama de inclusão, um círculo representa cada nodo e seus nodos descendentes são inseridos dentro do círculo de seus pais. Também conhecida como diagrama de Venn, é muito utilizada na representação de conjuntos. O item (c) da figura ao lado mostra a árvore do item (a) usando diagrama de inclusão.

Em um diagrama de barras, linhas são usadas para mostrar a hierarquia dos nodos. A raiz possui a linha de maior tamanho e os nodos irmãos possuem linhas de tamanhos iguais. Método bastante utilizado na criação de índices de livros. É similar à indentação usada em linguagens de programação. O item (b) da imagem ao lado indica como seria a árvore do item (a) usando essa representação.

Usando numeração por níveis o nodo raiz recebe o número um e todos os nodos seguintes recebem uma numeração sequencial, sempre antecedidos pela numeração de seus nodos superiores. Item (e) da figura à direita representa a árvore (a) com representação por níveis

Na representação por aninhamento, também conhecida por "representação por parênteses aninhados", a sucessão de parênteses reproduz as relações entre os nodos, aninhando um nodo filho ao seu pai. Como exemplo temos o item (d) da imagem ao lado representando a árvore (a).