arvore

ESTRUTURA DE DADO ARVORE
Conceitos Básicos

Árvores são estruturas de dados que seguem o conceito de hierarquia, a forma mais simples de definir a estrutura da arvore é a recursividade.

A arvore possui um conjunto de nós, e existe um nó principal chamado raiz.

Em uma definição mais formal, uma árvore é uma estrutura que contém um conjunto finito de um ou mais nós, sendo que um dos nós é especialmente designado como o nó raiz e os demais nós são particionados em 0 ou mais conjuntos disjuntos onde cada um desses conjuntos é em si uma árvore, que recebe o nome de sub-árvore.

Cada árvore tem apenas uma raiz. Os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas. Os nós que tem filhos são chamados nós internos.

Todo nó de uma árvore é a raiz de outra sub-arvore.

Existe a analogia com a arvore genealogica, portanto existe os nós filhos, pais, irmão, avós e tios de outro nó. Existe também analogia com descendente e ancestral.

O numero de filhos do nó é chamado grau de saída do nó.

Os nós folhas tem grau de saída 0.

Grau do nó: é o numero de sub-arvores que ele possui.

Grau da Árvore: O grau da àrvore é o maior entre os graus de seus nós.

Floresta: Uma floresta é o conjunto de zero ou mais àrvores.

Caminho: Quantidade de arestas existentes do nó A até o nó B.

Altura do nó: A altura de um nó é o maior caminho deste nó ate um nó folha, ou seja, é a quantidade de nós contando do nó até o nó folha. O nó folha tem altura 0.

Altura da Árvore: é igual ao maior nível de seus nós.

Nível ou Profundidade do nó: O nível ou profundidade de um nó é o tamanho do caminho (quantidade de nós visitados) da raiz até este nó.

Nivel ou Profundidade da raiz: O nível da raiz é 0.

Árvore Ordenada X Árvore Orientada:

Quando a ordem das subárvores de cada nó é significativa, dizemos que a árvore é ordenada. Neste caso, pode-se falar em primeira subárvore,