Info-Diversos

Prof. Adriano Teixeira de Souza



São estruturas de dados adequadas para a representação de hierarquias.



Uma árvore é composta por um conjunto de nós. 



Existe um nó r, denominado raiz, que contém zero ou mais subárvores, cujas raízes são ligadas diretamente a r.
A raiz se liga a um ou mais elementos, e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.



Fundamentos básicos
◦ GRAU – 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.



Fundamentos básicos
◦ A altura de uma árvore é o comprimento do caminho mais longo da raiz até uma das folhas. ◦ Uma árvore nula tem altura 0.
◦ Todos os nós são acessíveis a partir da raiz.
◦ Existe um único caminho entre a raiz e qualquer outro nó.



Formas de representação gráfica



Árvore Binária: Uma árvore binária é uma árvore que pode ser nula, ou então tem as seguintes características:
◦ Existe um nó especial denominado raiz;
◦ Nenhum nó tem grau superior a 2 (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.





Atravessamento (ou caminhamento) de árvore é a passagem de forma sistemática por cada um de seus nós;

Diferentes formas de percorrer os nós de uma árvore: ◦ Pré-ordem ou prefixa (busca em profundidade) ◦ Em ordem ou infixa (ordem central)
◦ Pós-ordem ou posfixa
◦ Em nível



Pré-ordem (prefixa)
◦ visitar a raiz;
◦ caminhar na subárvore à esquerda, segundo este caminhamento;
◦ caminhar na subárvore à direita, segundo este caminhamento. 

Atravessamento em ordem (infixa)
◦ caminhar na subárvore à esquerda, segundo este caminhamento;
◦ visitar a raiz;
◦ caminhar na subárvore à direita,