Árvore de dados

Árvores
Representação gráfica
As três formas de representação gráfica são:
Representação por parênteses aninhados
( A (B) ( C (D (G) (H)) (E) (F (I)) ) )
Diagrama de inclusão

Representação hierárquica

Motivação diversas aplicações necessitam de estruturas mais complexas que as listas estudadas até agora inúmeros problemas podem ser modelados através de árvores árvores admitem tratamento computacional eficiente quando comparadas às estruturas mais genéricas como os grafos (os quais, por sua vez são mais flexíveis e complexos)
Definição
Uma árvore enraizada T, ou simplesmente uma árvore, é um conjunto finito de elementos denominados nós ou vértices tais que:
T = 0 é a árvore dita vazia ou existe um nó especial r, chamado raiz de T; os restantes constituem um único conjunto vazio ou são divididos em m (deve ser maior ou igual a 1) conjuntos distintos não vazios que são as subárvores de r, cada subárvore a qual é, por sua vez, uma árvore.
Notação: Tv, se v é um nó de T então a notação Tv indica a subárvore de T com raiz em v.
Subárvore
Seja a árvore acima T = {A, B, ...}
A árvore T possui duas subárvores:
Tb e Tc onde
Tb = { B } e Tc = {C, D, ...}
A subárvore Tc possui 3 subárvores:
Td, Tf e Te onde
Td = {D, G, H}
Tf = {F, I}
Te = {E}
As subárvores Tb, Te, Tg, Th, Ti possuem apenas o nó raiz e nenhuma subárvore.
Exemplo: representação da expressão aritmética: (a + (b * (c / d) - e))

Nós filhos, pais, tios, irmãos e avô
Seja v o nó raiz da subárvore Tv de T.
Os nós raízes w1, w2, ... wj das subárvores de Tv são chamados filhos de v. v é chamado pai de w1, w2, ... wj.
Os nós w1, w2, ...wj são irmãos.
Se z é filho de w1 então w2 é tio de z e v é avô de z.
Grau de saída, descendente e ancestral
O número de filhos de um nó é chamado grau de saída desse nó.
Se x pertence à subárvore Tv, então, x é descendente de v e v é ancestral, ou antecessor, de x. Se neste caso x é diferente de v então x é