Só para não ficar sem resposta, resolvi implementar o algoritmo em JavaScript.
Os comentários explicam melhor do que um parágrafo introdutório, mas observo aqui que este código pode ser facilmente adaptado para qualquer linguagem, principalmente as orientadas a objeto. Evitei declarações de classe e complicações desnecessárias, mas incluí uma função para impressão do resultado, apenas para a comodidade de quem quiser testar o código (basta clicar em Executar trecho de código).
Reparem que esta solução se baseia no fato de que os nós são descritos, no array de dados (dados
), na sequência crescente de seus códigos (ID's).
O algoritmo, entretanto, pode ser facilmente adaptado para suportar sequências arbitrárias de descrição, desde que o código seja informado na 3ª coluna do array, por exemplo; basta incluir o código como um valor secundário (id: dados[i][2]
, neste novo exemplo), dentro da estrutura de cada nó (1º loop do algoritmo), e então realizar a comparação (if
, no 2º loop) a partir deste código armazenado, ao invés de usar o índice do loop (i+1
).
// Array de dados. A primeira coluna é o valor do nó; a segunda, indica o nó pai.
var dados = [
[ "Dado 1", null ],
[ "Dado 2", 1 ],
[ "Dado 3", 1 ],
[ "Dado 4", 2 ],
[ "Dado 5", 2 ],
[ "Dado 6", 4 ],
[ "Dado 7", 5 ]
];
// Declaração do array que conterá cada nó:
var nos = [];
// Transformação de cada elemento do array de dados em um nó (ainda sem relacionamento):
for(var i = 0; i < dados.length; i++){
nos.push({
valor: dados[i][0],
filhos: []
});
}
/*
CRIAÇÃO DOS RELACIONAMENTOS:
A ideia é que cada nó procure por seus filhos no array de dados; como o índice de um
elemento no array de dados é exatamente o mesmo índice do seu respectivo nó, no array
de nós, basta que cada nó procure no array de dados quais deles fizeram referência a ele:
*/
for(var i = 0; i < nos.length; i++){
for(var j = 0; j < dados.length; j++){
if(i+1 == dados[j][1]) nos[i].filhos.push(nos[j]); // i+1 porque os índices começam em 0.
}
}
// Imprime o resultado:
print(nos[0], "→ "); // nos[0] representa o nó raiz da árvore.
//==============================================================================================
/*
EXTRA:
Função recursiva para imprimir a árvore (com busca em profundidade), apenas para visualizar
o resultado.
Varia bastante de linguagem para linguagem, no JavaScript está é uma das formas de fazer:
*/
function print(no, recuo){
var p = document.createElement("p"); // Cria um parágrafo HTML.
p.innerHTML = recuo + no.valor; // Seta o texto deste parágrafo para indentação + valor.
document.body.appendChild(p); // Joga o parágrafo na tela (torna visível).
// Se possuir filhos...
if(no.filhos.length > 0) for(var i = 0; i < no.filhos.length; i++){
// ...imprime cada um deles, com um recuo 8 espaços maior:
print(no.filhos[i], " " + recuo);
}
}
ArrayList
você acrescenta uma entrada em umHashMap<Integer,TreeNode>
associando oID
do dado com o nó que você criou pra ele; então você pega o nó superior desse mesmo dado, consulta no mesmo map para obter o nó pai, e então acrescenta o filho no pai (ou no root, se não há pai). É +- isso, ou outra coisa?