Es un árbol binario bastante normal, excepto por el hecho de que uno de los nodos puede estar vacío.

Me gustaría encontrar una forma de generarlo de forma horizontal (es decir, el nodo raíz está a la izquierda y se expande a la derecha).

He tenido cierta experiencia expandiendo árboles verticalmente (nodo raíz en la parte superior, expandiéndose hacia abajo), pero no estoy seguro de dónde comenzar, en este caso.

Preferiblemente, seguiría estas dos reglas:

Si un nodo tiene solo un hijo, se puede omitir como redundante (siempre se muestra un "nodo final", sin hijos)Todos los nodos de la misma profundidad deben estar alineados verticalmente; todos los nodos deben estar a la derecha de todos los nodos menos profundos y a la izquierda de todos los nodos más profundos.Los nodos tienen una representación de cadena que incluye su profundidad.Cada "nodo final" tiene su propia línea única; es decir, el número de líneas es el número de nodos finales en el árbol, y cuando un nodo final está en una línea, puede que no haya nada más en esa línea después de ese nodo final.Como consecuencia de la última regla, el nodo raíz podría estar mejor en la esquina superior izquierda o inferior izquierda; se prefiere arriba a la izquierda.

Por ejemplo, este es un árbol válido, con seis nodos finales (el nodo está representado por un nombre y su profundidad):EDITAR: consulte la parte inferior de la pregunta para obtener una representación alternativa más fácil

        
[a0]-----------[b3]------[c5]------[d8]
    \              \         \----------[e9]
     \              \----[f5]
      \-[g1]--------[h4]------[i6]
            \           \--------------------[j10]
             \-[k3]

Que representa el árbol binario vertical y explícito:

0              a
              / \
1            g   *
            / \   \
2          *   *   *
          /     \   \
3        k       *   b
                /   / \
4              h   *   *
              / \   \   \
5            *   *   f   c
            /     \     / \
6          *       i   *   *
          /           /     \
7        *           *       *
        /           /         \
8      *           *           d
      /           /
9    *           e
    /
10 j

(ramas dobladas para compacidad;* representando nodos redundantes de un hijo; tenga en cuenta que*sonreal nodos, almacenando un hijo cada uno, solo con nombres omitidos aquí por el bien de la presentación)

(también, para aclarar, me gustaría generar el primer árbol horizontal; no este árbol vertical)

Digo agnóstico al lenguaje porque solo estoy buscando un algoritmo; Digo ruby porque de todos modos tendré que implementarlo en ruby.

Suponga que cadaNode la estructura de datos almacena solo su id, un nodo izquierdo y un nodo derecho.

Un maestroTree La clase realiza un seguimiento de todos los nodos y tiene algoritmos adecuados para encontrar:

Enésimo antepasado de un nodoEnésimo descendiente de un nodoTodos los descendientes del nodo final de un nodo y su recuentoLa generación de un nodo.El ancestro común más bajo de dos nodos dados

I ya saben:

El número de nodos finales

¿Alguien tiene alguna idea de dónde podría comenzar? ¿Debo ir por el enfoque recursivo? ¿Iterativo? Algún código Psuedo también sería genial, y muy apreciado =)

Progreso

Según la sugerencia de walkytalky, decidí ver cómo se vería asignar cada nodo "relevante" o significativo a una cuadrícula, siendo las columnas la profundidad y las filas identificables por sus nodos finales. Esto es lo que sucede (omitiendo la columna 7 porque no hay nodos significativos en la profundidad 7):

depth: 0  1  2  3  4  5  6  8  9  10
       a        b     c     d
                               e
                      f
          g        h     i
                                  j
                k

Debería ser bastante fácil generar esta cuadrícula, ya sea con búsquedas de amplitud o de profundidad. Quizás lo más trivial sea simplemente manteniendo una matriz 2D y colocando cada nodo significativo encontrado en ella, insertando una fila para cada "segundo hijo".

Ahora, conociendo estos hechos:

El último nodo de una fila debe ser un nodo finalLos hijos siempre están a la derecha, y en la misma fila o más abajo, de su nodo padre.Todos los nodos no finales deben tener exactamentedos niñosPor lo tanto, todos los nodos no finales tienen hijos que sonel primero a la derecha de su columna, el primer hijo está en la misma fila, el segundo hijo están filas debajo de ellos, donden es el número de nodos en el lado derecho de la misma.

Podemos ver que, dada cualquier cuadrícula válida, hayuna manera inequívoca para "conectar los puntos", por así decirlo; Hay un árbol inequívoco representado.

Ahora, "conectar los puntos" ya no es una pregunta de estructura de árbol binario ... es simplemente una pregunta de decoración. Solo necesitamos construir un algoritmo para colocar correctamente el correcto-'s y\es donde pueden ir, tal vez solo siguiendoCuadrícula simple / reglas lexicográficas, en lugar de reglas binarias de estructura de árbol.

Básicamente, esto significa que el problema de renderizar un árbol es ahora el problema mucho más simple derenderizando una cuadrícula, con elegantes decoraciones.

¿Alguien puede sugerir alguna forma de formular estas reglas? ¿O tal vez un método completamente diferente?

editar

He concebido una representación final mucho, mucho más fácil:

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)

 [a0 ]-------[b3 ]-------[c5 ]-------[d8 ]
   |           |           \---------------[e9 ]
   |           \---------[f5 ]
   \---[g1 ]-------[h4 ]-------[i6 ]
         |           \---------------------------[j10]
         \---[k3 ]

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)

Puede ser más fácil intentar crear este, en lugar del que había publicado anteriormente. Por un lado, conserva una bonita forma de cuadrícula, y no tienes que voltear con líneas diagonales. Todas las filas se asignan a lo largo de líneas de columna claramente visibles. Desafortunadamente, no es tan bonito como el primero.