Arvores Binarias

Árvores Binárias e Métodos e Busca

1. Árvores Binárias

São estruturas de dados que contém uma quantidade finita de elementos chamados de nós, que está vazia ou é particionado em 3 subconjuntos:
- 1° subconjunto  Raiz da árvore
- 2° e 3° subconjunto  subárvores esquerda e direita

Ex.:

Cada nó na árvore tem no máximo 2 nós descendentes (1 esquerdo e 1 direito), onde esses dois nós descendentes são chamados de nós irmãos. Nenhum nó descendente pode ter algum dos seus descendentes como sendo algum ancestral. Também, nenhum nó na árvore pode ter como pai, 2 ancestrais, ou melhor, nenhuma nós é apontado por 2 outros nós ao mesmo tempo. Abaixo, temos exemplos de árvores que não são binárias:

(a) (b)

(c)

1.1. Árvores Estritamente Binária

São árvores onde todos os nós não folhas, têm os dois descendentes, esquerda e direita:

Ex.:

Nível de profundidade – É relativo com o local onde os nós se encontram na árvore. O nó raiz se encontra no nível 0, os descendentes esquerda e direita do nó raiz, se encontram no nível 1 e assim sucessivamente até as folhas. A profundidade da árvore é igual ao último nível. Se o último nível é o 3, isso quer dizer que a árvore possui profundidade 3.

1.2. Árvores Binárias Completas

São árvores estritamente binárias, onde todos os nós considerados folhas, estão no mesmo nível de profundidade.
As árvores binárias completas seguem as seguintes regras:

2d -> Sendo d o nível de profundidade, temos com isso o número de elementos em cada nível.
2d – 1 -> Nós que não possuem folhas. tn = 2d+1 – 1 -> Total de nós em uma árvore binária completa.

Ex.:

1.3. Árvores Binárias Quase Completas

Uma árvore binária quase completa segue as seguintes regras:
1) Cada folha deve estar no nível d ou no nível d-1
2) Para qualquer nó ND da árvore com um descendente direito no nível d, todos os descendentes esquerdos de ND que são folhas, deve também encontrar-se em d.
3) Os nós de uma árvore binária são