NOTAS DE AULA2

Árvores Binárias

Definição:
Uma árvore binária T é um conjunto finito de nós tal que: - T=0 e a arvore é vazia, - existe um nó especial,chamado raiz(r ) de T, e os restantes podem ser divididos em 2 subconjuntos disjuntos Ter e Tde, que são subárvores esquerda e direita de r, e cada uma é também uma arvore binária. A raiz da subárvore esquerda de r é chamado de filho esquerda de r.O mesmo ocorre para o direito. O filho esquerdo pode existir sem o direito e vice-versa.
=>Toda árvore binária com n nós possui exatamente n+1 subárvores vazias.

Nomenclatura: Uma árvore binária é dita estritamente binária quando os seus nós tem 0 ou 2 filhos. Uma árvore binária é dita completa quando existem subárvores vazias apenas nos nós do último e do penúltimo nível. Uma árvore é dita cheia quando só existem sub-árvores vazias nos nós do último nível da árvore. Uma árvore é dita zig-zag quando os seus nós tiverem somente 1 filho =>A árvore completa tem altura mínima. =>A arvore zig-zag tem altura máxima Estritamente binária Completa /cheia

Estritamente binária/Completa

Zig-zag

Percursos:

Struct no
{
no*esq; char chave; no dir;
}

Deseja-se percorrer a estrutura de uma arvore imprimindo as chaves dos nós visitados (rotina –recursiva)

1) Percurso em Pré-Ordem
Void percurso(no *p)
{
if (p= =NULL) return; printf(“%c”,p->chave); percurso(p->esq); percurso(p->dir); }

2)Percurso em Ordem Simetrica
Void percurso(no *p)
{
if (p= =NULL) return; percurso(p->esq); printf(“%c”,p->chave); percurso(p->dir); }

3)Percurso em Pós Ordem
Void percurso(no *p)
{
if (p= =NULL) return; percurso(p->esq); percurso(p->dir); printf(“%c”,p->chave); }