Arvores binarias

Á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