Just to not be left unanswered, I decided to implement the algorithm in JavaScript.
The comments explain better than an introductory paragraph, but I note here that this code can be easily adapted to any language, especially object-oriented. I avoided class declarations and unnecessary complications, but I included a function to print the result, just for the convenience of whoever wants to test the code (just click Run snippet ).
Note that this solution is based on the fact that nodes are described in the data array ( dados ), in the growing sequence of their ID's.
The algorithm, however, can be easily adapted to support arbitrary description sequences as long as the code is entered in the 3rd column of the array, for example; it is enough to include the code as a secondary value ( id: dados[i][2] , in this new example), within the structure of each node (1st loop of the algorithm), and then perform the comparison ( if , in the 2nd loop) from this stored code , instead of using the loop index ( 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);
}
}
