Uma outra estrutura de dados não-linear comum é a árvore.
Neste diagrama acima, nós podemos ver que o ponto começar, ou o nó da raiz, estão circundados na cor azul. Um nó é uma estrutura simples que prenda dados e ligações a outros nós. Neste caso, nosso nó da raiz contem a corda “John” dos dados e três ligações aos outros nós. Observar que o grupo dos nós circundados no vermelho não tem nenhumas ligações (childs). Estes nós estão na extremidade das filiais e são chamados apropriadamente como as folhas ou os nós da folha. Em nosso diagrama, os nós são interconectados com as linhas pretas contínuas chamadas arcos ou bordas. Estas bordas mostram os relacionamentos entre os nós na árvore.
Um relacionamento importante na árvore binária é o relacionamento da pai-criança. Os nós do pai têm pelo menos uma borda ao nó abaixam na árvore. Este nó mais baixo é chamado o nó da criança. Os nós podem ter mais de uma criança, mas as crianças podem somente ter um único pai. Observar que o nó da raiz não tem nenhum pai, e os nós da folha não tem nenhuma criança. A característica final à nota em nosso diagrama é o subtree. Em cada nível da árvore, nós podemos ver que a estrutura de árvore está repetida. Por exemplo, os dois nós que representam “Charles” e “Rick” compõem uma árvore muito simples com o “Charles” como o nó da raiz e e “Rick” como um único nó da folha.
As árvores são executadas na memória de computador. Nós começaremos introduzindo a estrutura de árvore simples chamada a árvore binária. As árvores binárias têm a limitação que os nós não podem ter mais de duas crianças. Com esta limitação, nós podemos fàcilmente determinar como representar um único nó binário na memória. Nosso nó necessitará reservar a memória para os dados e dois ponteiros (para apontar dois childs desse nó).
|
