Busqueda en un arbol c++

[herc]

Hola de nuevo!

Tengo un problema con un ejercicio sobre árboles, llevo días dándole vueltas pero no se me ocurre como puedo solucionar éste ejercicio.

Se me presenta un árbol en el que cada nodo representa un servidor. Los nodos de los servidores tienen un identificador (un entero) y estos números van de 1 a n (donde n es el tamaño del árbol) de manera que un árbol podria ser así:

-------------------10
----------------/-------\
---------------9-------- 5
--------------/--\----------\
-------------3---4----------8
------------/--\------------/-\
-----------1---2----------6---7

Para hacerlo mas eficiente he hecho un vector de enteros de tamaño n que contiene la información de cada servidor.
Cada servidor tiene un ancho de banda almacenado en el vector. A grandes rasgos lo que yo quiero es que dada una petición de descarga de un archivo, buscar el servidor o servidores más apropiados para esta descarga (sumando los anchos de banda). El caso es que los servidores deben pertenecer a un mismo camino (puedo coger el servidor 3 y el servidor 2, pero no el 9 y el 1 por ejemplo).

Sé que igual es un poco complicado pero ya no se que hacer con este ejercicio, no se me ocurre ninguna manera así que agradeceré cualquier idea, gracias por leerlo!

[Markitos1024]

Mira todo arbol tambien es un grafo dirigido, podes conciderarlo como un grafo, donde el peso de las aristas es el ancho de banda y aplicar dijkstra O(n log(n)) para tener el camino mas corto partiendo desde uno.

La otra es dado el arbol aplicar backtraking con branch and bound. LO unico que es mas costoso aunque como es un arbol binario segun veo seria O(2^n)
Osea, preguntas si es hoja te fijas si no lo es sumas el ancho de banda y vas a recursion por los dos lados, si es hoja lo comparas con la solucion aterior si es menor pasa a ser la nueva solucion y sino lo descartas asi con todo el arbol. El branch and bound lo aplicas ya que si no es hoja pero ya su suma es mayor que la solucion haces poda osea no llamas a la recursion.

saludos