Definições Básicas Arvore Binária

Definições Básicas

Árvores são estruturas de dados extremamente úteis em muitas aplicações. Uma árvore é formada por um conjunto finito T de elementos denominados vértices ou nós de tal modo que se T = 0 a árvore é vazia, caso contrário temos um nó especial chamado raiz da árvore (r), e cujos elementos restantes são particionados em m>=1 conjuntos distintos não vazios, as sub-árvores de r, sendo cada um destes conjuntos por sua vez uma árvore.
A forma convencional de representar uma árvore está indicado na figura abaixo. Esta árvore tem nove nós sendo A o nó raiz.

Os conjuntos das subárvores tem de ser disjuntos tem de ser disjuntos, portanto a estrutura indicada na Figura não é uma árvore.

Se n é um nó da árvore T então Tn indica uma subárvore de T com raiz no nó n. Os nós n1, n2, ..., nk das subárvores de Tn são chamados de filhos de n e n é o pai destes nós, que são nós irmãos. Os nós B e C são filhos de A e nós irmãos. Nós sem filhos como os nós D, H, I, F e G são chamados de folhas. A subárvore da esquerda do nó A tem raiz em B e a subárvore da direita tem raiz em C, isto está indicado pelos dois ramos saindo de A. A ausência de um ramo na árvore indica uma subárvore vazia, como a subárvore da direita do nó B. O número de de filhos de um nó é chamado de grau de saída deste nó. Por exemplo, o nó C tem grau de saída 3 e o nó E grau 2. Se o nó n é a raiz de uma subárvore Tn e n1 pertence a Tn então n1 é descendente de n e n ancestral de n1. Portanto nós sem descendentes próprios é uma folha. Por exemplo, o nó H é ancestral do nó C e o nó D é descendente do nó A.
Um caminho da árvore é composto por uma seqüência de nós consecutivos (n1, n2, ..., nk-1, nk) tal que existe sempre a relação ni é pai de ni+1. Os k vértices formam k-1 pares e um caminho de comprimento igual a k-1. O comprimento do caminho entre o nó A e o nó H é 3.
O nível de um nó n pode ser definido do seguinte modo: o nó raiz tem nível 0, os outros nós tem um nível que é