Trabalho

ÁRVORES BINÁRIAS
Algoritmos e Estruturas de Dados II

Introdução
Raiz

Folhas

Nós ou nodos da Árvore

Introdução
Raiz: é o primeiro nó da árvore Nós pais e nós filhos

Folha: nó sem filhos

Introdução
Nível de um Nó: é a distância do nó até a raiz. A raiz está sempre no Nível 0

Nível 0 Nível 1 Nível 2

Nível 3

Altura ou Profundidade da Árvore: é o nível máximo dos nós da árvore. Neste exemplo, Altura = 4

Introdução
Sub-árvores: esquerda e direita

Grau de um Nó: é o número de sub-árvores do nó

Folhas: grau zero

Uma árvore binária é um conjunto finito de nós que pode ser vazio ou pode ser particionado em três sub-conjuntos: uma raiz e duas árvores binárias denominadas: sub-árvore da esquerda e sub-árvore da direita

Introdução
Propriedades: i O número máximo de nós no nível i de uma árvore binária é 2
Nível 0 Nível 1 Nível 2 20 = 1 21 = 2 22 = 4

Nível 3

23 = 8

Árvores Binárias

Propriedades: o elemento mais a esquerda na árvore é o de menor valor e o elemento mais a direita na árvore é o de maior valor

Árvores Binárias

typedef struct _no arvorebin; struct _no { int info; arvorebin *esquerda; arvorebin *direita; } Dados

esquerda

direita

Árvores Binárias - Percursos
Considerando que E, M, D, representam as operações "ir para a esquerda", "mostrar o nó" e "ir para a direita". Existem seis possibilidades para realizarmos estas operações em um nó: EMD, EDM, DEM, DME, MED, MDE. Se adotarmos a convenção de irmos para a esquerda antes de irmos para direita, somente três possibilidades permanecem: EMD, EDM, MED. Chamamos estas operações de percurso em-ordem, pós-ordem, e pré-ordem.

Árvores Binárias - Percursos
Percurso Em-ordem void em_ordem(arvorebin *root) { if (root != NULL) { em_ordem(root->esquerda); printf("%d",root->info); em_ordem(root->direita); } }

Ordem do Percurso: 20, 30, 40, 50, 90, 100

Árvores Binárias - Percursos
Percurso Pós-ordem

Ordem do Percurso: 20, 40, 30, 100,