Bueno, aver si llego a terminar :|
Para travesar un arbol/graph existen varios algoritmos unos entre ellos son DFS y BFS, ahora explicare/usare el DFS.
DFS o Depth-First Search. Como el nombre lo dice busca en profundidad. Lo primero que visita son los descendentes de un nodo y al final el nodo. De normal se implementa mediante recursiones.
El pseudo code del DFS seria:
Código:
DFS(node)
{
for each child c of node
DFS(c);
print the current node;
}
El DFS lo que hara es que empezara por las Hojas ( en el caso 7,4,6 ) pasar por todos los Siblings y llagar al padre luego pasara por la otra hoja ( que es 3 ) y de esta a la otra que es 15 luego subira hacia arriba pasando por 2 , 11 y 5
Dare un ejemplo mas sencillo para que se entienda mejor:
(Me picaso)
Cual seria el resultado de esta Graph si lo travesamos con DFS ?!
El algoritmo empezara por el 1 vera que el uno tiene hijos ( 2, 6, 7 ), bajara al 2, vera que el tambien tiene hijos y bajara al 3. Como 3 no tiene hijos daria Output 3 ( print 3 .. etc. ) como 3 no tiene hijos ( es hoja ) volvera hacia arriba ( al padre ). Como 2 tiene otro hijo, bajaremos otra vez, en esta caso seria el 4, dariamos Output 4. Como 4 es una hoja volveriamos arriba al padre, el 2, y bajaremos al otro hijo, el 5, otra vez damos output 5 y volvemos al padre. Ya que 2 no tiene mas hijos damos Output 2 y volvemos al padre , que ahora es el 1, que por su parte tiene otro hijo, el 6. Bajamos al 6 y como es hoja, output 6. Volvemos al 1 bajamos al 7 y del 7 al 8, como 8 es hoja .. output 8, retrocedemos al 7 y como tiene otro hijo , bajamos y damos Output 9 volvemos hacia arriba y como 7 no tiene otro hijo damos output 7 volvemos hasta arriba del todo y como el 1 no tiene mas hijos lo imprimimos ( output 1 ) el resultado final de este arbol travesado seria:
Un ejemplo de codigo DFS en PHP podria ser:
Código PHP:
function DFS(Node $nodes)
{
foreach($nodes->GetAllChilds() as $node)
{
DFS($node);
echo "Visiting Node: " . $node->GetValue() . "<br />";
}
}
DFS($nodes[1]);
El resultado de tu arbol seria:
Cita: Visiting Node: 7
Visiting Node: 6
Visiting Node: 4
Visiting Node: 8
Visiting Node: 3
Visiting Node: 15
Visiting Node: 2
Visiting Node: 11
Visiting Node: 5