Arvores binarias

843 palavras 4 páginas
Árvores Binárias (Estruturas Recursivas) * Estrututa de Busca; * BT é uma estrutura recursiva, composta:
Raiz;
Sub - árvore esquerda;
Sub - árvore direita; * Um elemento e2 pé filho de um elemento e1 se e2 é raiz de uma das sub-árvores de e1; * E1 é pai de e2 e e3; * Um elemento é folha se suas sub arvores são vazias; * Todo elemento que nao é folha é denominado nó terminal ou interior; * Um caminho entre dois elementos e1 e e2 é uma sequencia <x1,x2,x3,...xn> onde x1=e1 e xn=e2 e cada elemento é pai do seu sucesor; * Longitude de um caminho é igual a n-1; * Ramo é um caminho que parte de uma raiz e termina em uma folha; * Ancestral e1 é ancestral de e2 se existe caminho entre e1 e e2. Alem disso e2 é descendente de e1; * Altura de uma BT é a longitude do caminho mais longo que parte da raiz da arvore, raiz+1; * Peso é a quantidade de nós da arvore; * Uma BT é completa se todo nó interno possui exatamente duas sub arvores nao vazias; * Uma BT esta cheia se ela é completa e todas as folhas estão no mesmo nivel; * Quase cheia é uma BT que esta quase cheia até o penultimo nivel e todas as folhas do seguinte nivel estão tão a esquerda quanto possivel; * Duas BT, são iguais se elas são vazias ou se suas raizes são iguais. O mesmo se aplicando para suas sub arvores; * Duas BT são semelhantes se possuem os mesmos elementos; * Uma BT a1 ocorre em a2 se são iguais ou se a1 esta contido em a2;

TAD BT:
BT left (BT) = Retorna a sub arvore esquerda de BT;
BT right (BT) = Retorna a sub arvore direita de BT;
Info root (BT) = Retorna o elemento info da raiz de BT;
Int isEmpty (BT) = Verifica se BT é vazia;

Percurso em Árvore
Pré-ordem = raiz, subesquerda, subdireita;
Em ordem = subesquerda, raiz, subdireita;
Pos ordem = subesquerda, subdireita, raiz;
Por niveis = Nos niveis 0, 1, 2,... Consecutivas;

Implementação de Árvores Binárias * Árvore simplesmente encadeada;
Typedef

Relacionados

  • Arvores binarias
    983 palavras | 4 páginas
  • Árvores Binárias
    1499 palavras | 6 páginas
  • Arvores binarias
    364 palavras | 2 páginas
  • Arvores binárias
    1191 palavras | 5 páginas
  • arvores binarias
    2352 palavras | 10 páginas
  • Árvores Binárias
    775 palavras | 4 páginas
  • arvores binarias
    1170 palavras | 5 páginas
  • Árvores Binárias
    3722 palavras | 15 páginas
  • Arvores binárias
    4463 palavras | 18 páginas
  • árvores binárias
    415 palavras | 2 páginas