Resolução de Prova de Avaliação:

//pergunta 3, Exame de Recurso, 1998/99, MTA

template<class T>
bool SimilarTree(BinaryTree<T> & tree1, BinaryTree<T> & tree2)
{
  return Semelhantes(tree1.root,tree2.root);
}

template<class T>
bool Semelhantes(BinaryTreeNode<T>* t1, BinaryTreeNode<T>* t2)
{
  if(!t1 && !t2) return true;    // duas 'arvores vazias (condicao i do enunciado)
  if(t1 && t2)
    return Semelhantes(t1->LeftChild,t2->LeftChild) && Semelhantes(t1->RightChild,t2->RightChild);
  else return false;
}

Nota: estas duas funcções, no sendo membros da classe BinaryTree, teriam que ser declaradas como funções "amigas" dessa classe para poderem utilizar os membros-dado privados das classes BinaryTree e BinaryTreeNode.

//pergunta 4, Exame de Recurso, 1998/99, MTA

Apresentam-se 3 abordagens possíveis para a resolução do problema:

1) supondo que temos todos os pontos disponíveis no mesmo instante:

1.1) estruturas de dados a utilizar:
   - lista linear com representação em array para guardar todos os pontos - "listaGeral".
   - lista linear em array (ou ligada) de listas ligadas para os clusters - "listaDeClusters".
 
Cada cluster é uma lista ligada cujo 1o. elemento se situa em listaDeClusters[j]; cada posição das listas deve conter três campos numericos para armazenar as duas coordenadas (campos x e y do tipo T) e para armazenar a distancia do ponto 'a origem do sistema de eixos (campo "distancia-'a-origem" do tipo T). No caso da lista ligada, estes campos fazem parte do campo data;

1.2) algoritmo:
   - ordenar "listaGeral" por ordem nao decrescente com base no campo "distancia-'a-origem",  utilizando o algoritmo QuickSort;
   - criar a "listaDeClusters" com n posicoes e utilizar o indice j com 0 <= j <n para aceder a cada posicao dessa lista;
   - efectuar o seguinte ciclo de instrucoes, iniciando na posicao 0 da "listaGeral" e acabando na ultima posicao n-1 (utilizando o indice i com 0 <= i <n):
     {
      - ler o campo "distancia-'a-origem" do elemento i;
      - se se tratar do 1o. elemento (i=0) armazenar esse ponto na 1a. posicao da "listaDeClusters"
        ( listaDeClusters[0].data.x = listaGeral[0].x; ...);
      - se ja' nao for o 1o. elemento (i!=0), comparar os campos "distancia-'a-origem" do elemento i em analise e do elemento (i-1);
        {
          - se a diferenca entre os dois valores for inferior 'a distancia de referencia, criar um novo no' na lista ligada (acrescentar um no' ao cluster j);
          - se a diferenca for maior, avancar para a posicao seguinte da "listaDeClusters" (j++) e guardar a informacao relativa ao ponto em analise no novo cluster.
        }
     }
1.3) complexidade temporal:
   - O(log(n)) para a ordenacao;
   - O(n) para o agrupamento em clusters (cada ponto so' tem que ser comparado com o seu vizinho anterior).

2)
Se nao for feita a ordenacao do conjunto inicial de pontos, pode utilizar as mesmas estruturas de dados embora nao necessite do campo "distancia-'a-origem". O algoritmo sera': - criar duas variaveis do tipo int, i e j, inicializadas a zero. Essas duas variaveis serao utilizados como indices para aceder a cada posicao da lista geral, listaGeral[i], e da lista de clusters, listaDeClusters[j]. Executar o seguinte ciclo enquanto i<length(listaGeral):
     {
      - colocar listaGeral[i] em listaDeClusters[j];
      - executar o seguinte ciclo para cada ponto k do cluster j, enquanto existirem pontos no cluster j: (necessita criar um apontador de no inicializado com o endereco do cluster j, i. e., com o valor (ListaDeClusters+j); o ciclo termina quando o apontador de no' for nulo)
         {
           - calcular a distancia entre o ponto k e cada ponto de listaGeral; se a distancia entre os dois for inferior 'a distancia de referencia:
              {
               - colocar esse ponto da listaGeral num novo no' do cluster j;
               - apagar (com a funcao Delete) esse elemento da listaGeral;
              }
         }
      - incrementar i;
      - incrementar j;
     }

3)  caso em que os pontos nao estao todos disponiveis no instante em que o programa arranca. Supoe-se que os pontos vao sendo recebidos e processados um a um.

1) estruturas de dados:
   - objecto constituido por dois campos do tipo T para guardar as coordenadas do ponto;
   - lista ligada de listas duplamente ligadas para implementar o conjunto de clusters;
     Cada campo data da lista ligada tem que ser um no' para conter um campo data e um apontador para o no' seguinte. Cada no' da lista ligada constitui o 1o. no' de cada cluster.
2) algoritmo:
   - enquanto existirem dados na entrada:
     {
       - cada ponto recebido tem que ser comparado com todos os pontos que ja' se encontram  armazenados em clusters; se se verificar que a distancia do ponto recebido a um ponto ja' armazenado num cluster e' inferior 'a distancia de referencia:
          - se for a 1a. vez que isso acontece, cria um novo no' no cluster que estava a analisar e continua a comparar com os outros pontos de todos os
clusters;
          - se for a segunda ou mais vezes que se verifica isso, entao junta num so' os clusters a que pertencem os pontos para os quais isso se verificou;
     }