Árvore

Pessoal, hoje iremos falar um pouco sobre a estrutura de dados chamada árvore, bora aprender um pouco? 😀

Árvore é um tipo abstrato de dados que armazena elementos de uma forma hierárquica. A árvore é um conjunto finito de elementos chamados nós, com informação e que têm relação entre si do tipo pai-filho. Se a árvore não é vazia, ou seja, tem nós, então:
*existe um nó especial chamado raiz que não tem pai
*todo o nó da árvore (exceto a raiz) tem um único pai
*um nó pode ter 0, 1 ou mais filhos

Nós irmãos: aqueles que têm o mesmo pai. Se o nó x pertence à sub árvore Tv, então, x é descendente de v e v é ancestral de x. Nó folha (ou externo) é o nó que não tem filhos. Nó interno: nó que tem um ou mais filhos.

arvore1

*Nós internos: A, B, C, D, F, I
*Nós folhas: E, G, H, J, K, L, M
*I, J, K são filhos de D, logo são irmãos
*D é pai de I, J, K e antepassado de N
*N é descendente de D

Grau de saída: o número de filhos de um nó é chamado o grau de saída desse nó. Grau de uma árvore: é o maior grau entre os graus de seus nós. Floresta: um conjunto de zero ou mais árvores. Árvore cheia: é uma árvore com número máximo de nós.

arvore2

Altura

*do nó: comprimento dos maiores caminhos do nó a uma folha
*da árvore: a altura da raiz
*convenciona-se que:
**A altura de uma folha é 1
**A altura da árvore vazia é 0

Profundidade
*do nó: comprimento do (único) caminho da raiz ao nó
*da árvore: máximo das profundidades das sua folhas
*convenciona-se que:
**A profundidade da raiz é 1
**A profundidade da árvore vazia é 0

arvore3

Fontes:
http://www.devmedia.com.br/trabalhando-com-arvores-binarias-em-java/25749
http://precisoestudarsempre.blogspot.com.br/2015/01/arvore-binaria-implementacao-em-java.html
https://pt.wikipedia.org/wiki/%C3%81rvore_%28estrutura_de_dados%29

Comentários

comentários

Share this post

No comments

Add yours