Arvores binarias

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (843 palavras )
  • Download(s) : 0
  • Publicado : 8 de abril de 2013
Ler documento completo
Amostra do texto
Á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 deum 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 an-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 umaBT é 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 arvoresnao 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 nivelestã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 osmesmos 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 direitade 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...
tracking img