algorithm - recursivos - Cómo dibujar una estructura de árbol?(¿Un algoritmo de recursión de árbol de asignación de espacio bidimensional?)

recursividad social

Question

Tengo una estructura de árbol arbitraria de nodos. Quiero dibujar este árbol para proporcionar a los usuarios una representación visual. Necesito recurrir sobre el árbol y para cada nodo agregar un elemento gráfico a una lista, y luego dibujar la lista de elementos una vez que la recursión de árbol haya finalizado. La recursión y el dibujo de elementos es, por supuesto, trivial; lo que es un poco más complicado es cómo colocar los nodos gráficos para que no se superpongan con otras ramas.

Estoy usando Android, pero eso no es importante. Estoy buscando un enfoque, posiblemente un algoritmo que pueda mantener una imagen del espacio 2D a medida que pasa sobre el árbol, por lo que solo asigna las coordenadas más apropiadas para cada nodo a medida que lo hace El permiso.

¿Algunas ideas?

Actualizar

Este es el artículo con el mejor y más completo algoritmo.

Answer 1

Eche un vistazo a Dot . Puede convertir su árbol en representación de puntos y luego usar Graphviz para visualizar en el formato que desee. Por ejemplo, Doxygen lo usa para representar la estructura del programa.

Answer 2

Dependiendo de la naturaleza de sus datos, un TreeMap puede ser más apropiado que una representación de tinkertoy.

Answer 3

Graphviz y mfgraph son potentes, pero son para gráficos generales y probablemente sean excesivos para los árboles.

Pruebe googlear en el árbol + diseño + algoritmo o vea Árbol de Javascript gráfico con Diseño . Este último es antiguo pero usa lienzo HTML y javascript, y explica el código, por lo que tanto el código como el enfoque deberían ser portátiles.

Answer 4

Sugiero dibujar el árbol en línea. Para ello, utiliza algún tipo de "cursor de dibujo" en movimiento.

Puede almacenar un width atributo para cada nodo que se calcula de la siguiente manera:

• el width de una licencia es 1
• el width de un nodo interno es la suma del width de todos los niños

Luego, dibuja la raíz "en la primera línea" en el medio, lo que significa que simplemente toma la mitad del width de raíz.

Luego, genera una cuadrícula sobre la imagen de manera que cada línea de la cuadrícula corresponde a una línea resp. un paso de izquierda a derecha y cada intersección de líneas de cuadrícula puede contener un nodo y cada nodo tiene suficiente espacio.

Luego, itera a través de los niños y mientras itera, acumula el width los niños y dibuja los niños "en la siguiente línea". Para dibujar currentChild , mueves tu cursor de dibujo currentWidth/2 a la derecha, dibuja currentChild , y mueve el cursor de dibujo al currentWidth/2 restante a la derecha.

Para que los nodos estén en buen orden, podría considerar una primera búsqueda de amplitud.

Espero que mi explicación sea clara, pero creo que será mejor si hago una pequeña foto.

Este es nuestro árbol ( x son nodos, todo lo demás)

 +-------x--+-------+
| | |
+-x-+ +-+x+-+ +-x-+
| | | | | | | | |
x x x x x x x x x

Entonces, calcula el width la hoja s:

 +-------x--+-------+
| | |
+-x-+ +-+x+-+ +-x-+
| | | | | | | | |
1 1 1 1 1 1 1 1 1

Luego, de abajo hacia arriba, el width es como sumas de width para niños s:

 +-------9--+-------+
| | |
+-2-+ +-+4+-+ +-3-+
| | | | | | | | |
1 1 1 1 1 1 1 1 1

Entonces, comienzas en la raíz ( width 9) y vas 4.5 pasos hasta el rigt en la primera línea.

Luego, mueve su "cursor de dibujo" a la segunda línea, "columna 0" (vaya a la izquierda).

El primer niño tiene un width 2, por lo que vamos 2/2=1 líneas de cuadrícula a la derecha y dibujamos el nodo y movemos el cursor de dibujo las líneas de cuadrícula restantes 1 hacia la derecha para terminar el nodo. Por lo tanto, el siguiente nodo tiene un width 4, lo que significa que vamos a la derecha 4/2 = 2 líneas de cuadrícula, dibujamos, vamos los 2 pasos restantes, y así sucesivamente.

Y así sucesivamente con la siguiente línea. Al final (o en pasos intermedios), conecta los nodos.

Este procedimiento asegura que no haya nodos superpuestos (si las líneas de la cuadrícula están lo suficientemente lejos entre sí), pero podría generar diagramas de árbol bastante grandes que podrían usar el espacio de manera más eficiente.

Para detectar el espacio no utilizado, uno puede simplemente escanear las líneas después del proceso anterior y observar si hay intersecciones de líneas de cuadrícula no utilizadas y luego posiblemente realinear algunos nodos para llenar el espacio.

Answer 5

Intentaría con el algoritmo de Walker. Aquí hay un trabajo académico sobre el algoritmo. Si quiere ver el código, mire el NodeLinkTreeLayout en Prefuse . Prefuse es de código abierto, por lo que no debería haber problemas para adaptar el código a su situación, siempre y cuando siga los términos de la licencia.