Ponteiros

Web Aula 1

É bem provável que a estrutura não linear de maior aplicação em computação é a estrutura de árvore, ou simplesmente, árvore, que pode ser definida da seguinte maneira:

Uma árvore A é um conjunto finito de N nodos, tal que N > O. Então:

1 – Existe um nodo especial, chamado raiz da árvore;

2 – Os restantes N-1 nodos estão particionados em m conjuntos disjuntos,

A1 ,..., Am , sendo que cada um é, por sua vez, uma árvore.

Essas árvores A1 ,... Am são chamadas subárvores da raiz.

Esta é uma definição recursiva, ou seja, definimos árvore em função de árvores. A recursividade aqui é utilizada como uma ferramenta para a definição de um padrão fundamental de estruturação. Na definição de listas lineares, utilizamos o sequenciamento (ou a repetição) como padrão fundamental de estruturação e comportamento. É importante observar que podemos utilizar a recursividade para expressar sequenciamento ou repetição, como m:

Uma lista linear é um conjunto finito de N nodos, tal que, se N > O, então:

1. Existe um modo especial que precede todos os demais;

2. Os restantes N - 1 nodos formam uma lista linear.

A recíproca, no entanto, não é verdadeira (Wirth, 1976). Podemos utilizar a recursividade para definir de uma maneira elegante e concisa estruturas com um grau de sofisticação muito além da capacidade da repetição ou do sequenciamento. A definição de árvores é um exemplo clássico

Existem diversas maneiras de se representar graficamente uma árvore, e a figura 1.25 mostra algumas delas (as principais), para a árvore {A,B,C,D,E,F}. Nesta árvore, A é a raiz, e {B, D, E, F} e {C, G} são subárvores de A. {D}, {E} e {F} ]são subárvores da raiz B, e {G} é subárvore da raiz C.

1) Grafo

2) Conjuntos Superpostos (Também conhecidos como DIAGRAMA DE VENN)

3) Parênteses

(A(B(D,E,,F), C(G)))

4) Paragrafamento ou Identação

Grau de um nodo é o número de subárvores que possui; um nodo de grau 0 é chamado nodo terminal, ou, significativamente, folha.

Na árvore da figura 1.25:

• A possui grau 2

• B grau 3

• C grau 1

• D, E, F e G possuem grau 0, sendo folhas, portanto.

Repare que a representação em forma de grafo, apesar de ser a que mais justifica o nome dado à estrutura, está desenhada na figura 1.25 de uma forma bastante incomum entre as árvores da natureza: com a raiz em cima e as folhas em baixo.

Na verdade, este é um costume generalizado em computação e, provavelmente, teve sua origem na representação de estruturas hierárquicas por árvores.

Uma discussão sobre qual das maneiras (a), (b) ou (c) da figura 1.26 deve ser seguida, pode parecer bizantina à primeira vista, mas existe uma terminologia associada com a disposição gráfica dos nodos que já se tornou padrão.

Dizemos, por exemplo, que B e C estão “abaixo” de A; C está “acima” de D e E, ou então que é o nodo “mais à esquerda” da árvore. Somente a representação (A) está coerente com esta terminologia.

Definimos nível de um nodo, com relação a uma árvore T, da seguinte maneira:

1 . Se um nodo X está no nível i,