Estrutura de Dados - Arvore

gcaraciolo
(usa elementary OS)

Enviado em 15/08/2013 - 01:01h

Boa noite pessoal, estou tentando criar um algoritmo que faça inserção em uma arvore binaria por nível. Não quero que seja ABB nem AVL, preciso de que seja por nivel, tipo a leitura de uma arvore por nivel.

//com essa estrutura
struct Tno{
int info;
struct Tno *esq, *dir;
};

//exemplo pratico com a sequencia de inserção A, B, C, D, E, F, G, H, I

......................A.....................
.............B...............C...........
.......D..........E.....F..........G.....
.H...........I...........................

espero que tenham entendido..

paulo1205
(usa Ubuntu)

Enviado em 15/08/2013 - 08:43h

Fico curioso para saber a aplicação desse tipo de inserção. Tentei imaginar alguma situação em que se aplicasse, mas não consegui achar nenhuma.

Com relação a implementação, não seria o caso de simplesmente usar um algoritmo de busca em largura (breadth-first search), só que modificado para procurar por um nó vazio (incluindo filhos não utilizados de nós folhas), em lugar de buscar uma determinada chave? Não vejo como não possa funcionar.

Mas um problema é que a inserção de um único elemento seria O(n). Inserir vários elementos seria O(n²). Para inserir de modo mais eficiente, seria melhor você criar primeiro uma fila com todas os elementos a serem inseridos, e depois inseri-los todos sequencialmente, aproveitando a mesma operação de busca em largura.

gcaraciolo
(usa elementary OS)

Enviado em 15/08/2013 - 09:51h

a aplicação é didática mesmo.. por exemplo tem alguns exercicios da faculdade que são: verifique se uma arvore é ABB ou não.. ai pra fazer o algoritmo q faz a verificação, eu precisaria da arvore com inserções aleatória..
o problema dessa sua solução é q não cheguei no nivel de grafos ainda =/