EP3

[Alfredo Goldman <gold@ime.usp.br>]

Recebi a seguinte dúvida com relação ao EP3 e respondo a todos.
 > Professor,
 > 
 > Tenho uma dúvida quanto à primeira parte do EP3.
 > 
 > Vamos supor que para criacao da árvore eu escolha k=3.
 > Isso significa que terei um cubo de 3 dimensões em que
 > cada vertice aponta para outros três vertices
 > (conforme o desenho da figura 1).
 > 
 > Nas arvores binarias, cada ná pode ter apenas 2
 > filhos. Para isso, temos na estrutura os campos esq e
 > dir.
 > 
 > Mas e no caso da árvore que sera gerada no EP3? 
 > 
 > Se eu escolho k=3, o nó raiz (que começa com 000),
 > logo de cara possui 3 filhos (001, 010, 100 - veja a
 > figura 1 do enunciado).
 > 
 > Se k=4, o nó raiz possui 4 filhos e assim
 > sucessivamente...
 > 
 > Como imlementar em C uma estrutura em que um nó pode
 > ter vários filhos? Como o nó raiz pode apontar para 3
 > ou 4 nós simultâneamente?
 > 
Você vai ter basicamente duas opções. 
1) Observando que para o programa você deve ler uma matriz
de quadrada de dimensão 2^k, de alguma forma este espaço tem
que ser alocado. A solução simples é prever um tamanho máximo
para a matrix/árvore.

2) A melhor solução é a seguinte:
   a) Alocar dinamicamente o espaçõ necessário para guardar
a matriz (através de malloc (n*n*sizeof(int));
   b) Representar a árvore da seguinte forma:

               +------raiz
               v   
           filho1 -> filho2 ->  filhoi -> ...  -> filho n
     --------+                    +
     +                            |
     v                            v
   neto1(f1)-> ..->neton(f1)    neto1(fi)->... -> neton(fi) 

Os nós são do tipo:

typedef struct _no {
  int info;
  struct _no *primogenito, /* Ponteiro para o primeiro filho */
             *irmao;       /* Ponteiro para uma lista ligada de irmãos */
} no;

Alfredo

ps: A Marina está fazendo uma primeira versão do EP para
que fiquem mais clara a parte de soma de mensagens.