Arvores binarias

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (364 palavras )
  • Download(s) : 0
  • Publicado : 14 de junho de 2012
Ler documento completo
Amostra do texto
Árvore binária é uma estrutura de dados caracterizada por:
* Ou não tem elemento algum (árvore vazia).
* Ou tem um elemento distinto, denominado raiz, com dois apontamentos para duasestruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.
Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipode árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca.

-------------------------------------------------
Definições para árvores bináriasOs nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.
Uma árvore binária é considerada estritamente binária se cada nó da árvore possui grau zero oudois.
A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.Uma árvore é dita completa se todas as folhas da árvore estão no mesmo nível da árvore.

-------------------------------------------------
Definições em teoria dos grafos
Em teoria dos grafos,uma árvore binária é definida como um grafo acíclico, conexo, dirigido e que cada nó não tem grau maior que 3. Assim sendo, só existe um caminho entre dois nós distintos.
E cada ramo da árvore éum vértice dirigido, sem peso, que parte do pai e vai o filho.
-------------------------------------------------
Percursos em árvore
-------------------------------------------------

Existemtrês tipos de percursos: Percurso em InOrdem, PreOrdem e PosOrdem.

InOrdem
O algoritmo desse percurso é:
-------------------------------------------------
emOrdem(Struct No *n){-------------------------------------------------
if(n!=null){
-------------------------------------------------
emOrdem(n->esq);
-------------------------------------------------
visita(n);...
tracking img