arvore c

Árvore
Árvore é uma estrutura não linear, que determina uma coleção finita de n >= 0, nós.
Se n = 0

a árvore é nula.
Senão

- existe um nó especial raiz
- os demais nós são chamados subárvores T1, T2, ..., Tk e considerados como estruturas disjuntas de árvores.
- cada uma das estruturas Ti é organizada na forma de árvore.
A exigência de serem disjuntas garante que um mesmo nó não aparece em mais de uma subárvore, o que é conseguido não permitindo que não se interliguem.
Nível 0

a

b

x

s

c

z

h

Nível 1

d

f

t

n

Nível 2

Nível 3

O número de subárvores de um nó denomina-se grau. Ex: o nó a tem grau 3 o nó d tem grau 2 o nó c tem grau 1
Um nó com grau zero não possui subárvores e é chamado de terminal ou folha. Ex: nó
f.
Os demais nós são chamados de não-terminais. O grau de uma árvore é definido como sendo igual ao máximo dos graus de todos os seus nós, por exemplo,o grau dessa árvore é 3, pois nenhum nó tem mais de 3 subárvores.
As raízes das subárvores de um nó chama-se filhos do nó sendo este o pai deles. Os filhos do mesmo pai são denominados irmãos.
Ex: Os filhos do nó b são x, s, z.
O nó d é o pai de l, m.
O nó f é irmão do nó n.
A raiz de uma árvore encontra-se no nível 0. Se um nó estiver no nível n, seus filhos estarão no nível n+1.

A altura de uma árvore é definida como sendo o máximo de níveis de todos os seus nós, por exemplo, nesta árvore a altura é de 4 e a altura da subárvore d é 2.

Árvore Binária
É uma árvore que pode ser nula ou então tem as seguintes características: existe um nó especial raiz. os demais nós são particionados em T1 e T2 estruturas disjuntas de árvores binárias, onde T1 é a subárvore esquerda e T2 a subárvore da direita, da raiz. nenhum nó tem grau superior a 2 (2 filhos).
Implementação de uma árvore binária:
Cada nó de uma árvore precisa armazenar um elemento e referenciar o nó pai e seus nós filhos. Isso pode ser esquematizado em uma estrutura. Ex;