Algoritmo de visualización de árbol

Question

¿Hay algún algoritmo para la visualización de estructura de datos en árbol? Intenté buscar en Google, pero no pude encontrar ninguno. Estoy bastante seguro de que tiene que haber algún algoritmo para esta tarea no tan simple. O alguien tiene algunas ideas?

Answer 1

Asunción: desea que cada nodo se muestre de manera que se centre sobre sus nodos secundarios.

Para lograr esto, calcule el ancho de cada nodo, que defino como la cantidad de espacio horizontal requerido para mostrar el subárbol completo de este nodo, de modo que no se superponga con los subárboles de los hermanos izquierdo o derecho.

Esto conduce a:

width = 1 + sum(widths of children's nodes) 

lo tanto, hacer un recorrido en profundidad a través del árbol para calcular el ancho de cada nodo. Para visualizar, haz un recorrido transversal de ancho para dibujar el árbol nivel por nivel.

Esta es la idea aproximada de cómo hacerlo. Es posible que desee ajustar el cálculo de ancho dependiendo de los detalles de cómo le gustaría renderizar el árbol.

Answer 2

Puede usar el lenguaje DOT con graphviz, por ejemplo.

Answer 3

Tree-mapping es probablemente lo que estás buscando. Graphviz es bueno para visualizar estructuras de gráficos no especializadas para estructuras de árbol. No pude encontrarlo de nuevo, pero recuerdo haber leído en un artículo científico que los treemaps (creo que los voronoi) son óptimos para representar estructuras arbóreas, con respecto al lugar que consumen y que el área puede usarse para representar alguna unidad (como el tamaño del byte para ejemplo).

Here son algunas alternativas.

Here es una buena lista de artículos y otra información sobre el tema.

Answer 4

También puede imprimir el árbol de izquierda a derecha, es decir, la raíz a la izquierda, el primer nivel a la derecha y así sucesivamente. Encontrará el árbol impreso con cada nivel en su propia 'columna'. El algoritmo es algo como esto:

print(node, spaces): 
    if node has left child: 
     print(left_child, spaces + ' ') 
    print spaces + node + '\n' 
    if node has right child: 
     print(right_child, spaces + ' ') 

Este algoritmo imprimirá un nodo de árbol por línea. Cada nivel del árbol se sangrará a la derecha por algunos espacios. Este algoritmo imprimirá los elementos en orden ascendente, pero el orden descendente se puede lograr procesando primero al niño correcto.