Arvores binárias e arvores avl

Arvores Binarias

Linguagem de Programação

Índice

Introdução ………………………………………………………………………… 3 Desenvolvimento ……………………………………………………………… 4 Conclusão ……………………………………………………………………… 9

Introdução

Neste trabalho recolhemos informação sobre 2 tipos de arvores (AVL e Binárias). Tambem pesquisámos os conceitos basícos a cerca de Arvores em programação.

Estrutura em Arvore

Árvore, no contexto da programação e ciência da computação, é uma estrutura de dados que herda as características das topologias em árvore.
Estruturas em árvores são estruturas de dados adequadas para a representação de hierarquias.
Uma árvore é composta por um conjunto de nós.
Existe um nó r, denominado raiz, que contém zero ou mais subárvores, cujas raízes são ligadas directamente a r.
A raiz se liga a um ou mais elementos, e cada um destes forma uma nova subárvore. Esses elementos são seus galhos ou filhos.

Subárvore
Uma subárvore é como um pai da árvore. Em cada árvore, se existir um pai, esse pai é a subárvore.

Formas de representação de estrutura árvore
Existem varias formas de representação de estrutura árvore: * Garfo * Indentação * Diagrama de venn * Parenteses alinhados

Como percorrer uma árvore
O seguinte exemplo é uma versão simplificada. Ele imprime o item de cada nó da árvore binária cuja raiz é h (o "h" é inicial de "here").

void imprime (link h) { if (h == NULL) return; printf("%d\n", h->item); imprime(h->l); imprime(h->r);} Essa função percorre a árvore em ordem raiz-esquerda-direita (= preorder).

Se as três últimas instruções forem trocadas por:

imprime(h->l); printf("%d\n", h->item); imprime(h->r); a árvore será percorrida em ordem esquerda-raiz-direita (= inorder).

Se as três últimas