É uma árvore binária bastante normal, exceto pelo fato de que um dos nós pode estar vazio.

Eu gostaria de encontrar uma maneira de produzi-lo de maneira horizontal (ou seja, o nó raiz está à esquerda e se expande para a direita).

Eu tive alguma experiência em expandir árvores verticalmente (nó raiz na parte superior, expandindo para baixo), mas não sei por onde começar, neste caso.

De preferência, seguiria estas duas regras:

Se um nó tiver apenas um filho, ele poderá ser ignorado como redundante (um "nó final", sem filhos, sempre será exibido)Todos os nós da mesma profundidade devem estar alinhados verticalmente; todos os nós devem estar à direita de todos os nós menos profundos e à esquerda de todos os nós mais profundos.Os nós têm uma representação de string que inclui sua profundidade.Cada "nó final" possui sua própria linha exclusiva; isto é, o número de linhas é o número de nós finais na árvore e, quando um nó final está em uma linha, pode não haver mais nada nessa linha após esse nó final.Como consequência da última regra, o nó raiz pode estar melhor no canto superior esquerdo ou no canto inferior esquerdo; o canto superior esquerdo é o preferido.

Por exemplo, esta é uma árvore válida, com seis nós finais (o nó é representado por um nome e sua profundidade):EDIT: consulte a parte inferior da pergunta para obter uma renderização alternativa e mais fácil

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

Que representa a árvore binária vertical explícita:

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

(galhos dobrados para compactação;* representando nós redundantes de um filho; Observe que*sãoreal nós, armazenando um filho cada, apenas com nomes omitidos aqui para fins de apresentação)

(também, para esclarecer, eu gostaria de gerar a primeira árvore horizontal; não essa árvore vertical)

Digo independente de linguagem porque estou apenas procurando por um algoritmo; Digo ruby porque, eventualmente, terei que implementá-lo de qualquer maneira.

Suponha que cadaNode A estrutura de dados armazena apenas seu ID, um nó esquerdo e um nó direito.

Um mestreTree A classe mantém o controle de todos os nós e possui algoritmos adequados para encontrar:

O enésimo enésimo ancestral de um nóO nono descendente de um nóTodos os descendentes do nó final de um nó e sua contagemA geração de um nóO menor ancestral comum de dois nós dados

I já sei:

O número de nós finais

Alguém tem alguma idéia de onde eu poderia começar? Devo ir para a abordagem recursiva? Iterativo? Algum código Psuedo seria bem legal também, e muito apreciado =)

progresso

Conforme a sugestão de walkytalky, decidi ver como seria mapear cada nó "relevante" ou significativo para uma grade, com as colunas sendo a profundidade e as linhas identificáveis por seus nós finais. Aqui está o que acontece (pulando a coluna 7 porque não há nós significativos na profundidade 7):

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

Deve ser fácil o suficiente para gerar essa grade, com buscas de amplitude ou profundidade. Talvez o mais trivial simplesmente mantendo uma matriz 2D e colocando todos os nós significativos encontrados nela, inserindo uma linha para cada "segundo filho".

Agora, conhecendo estes fatos:

O último nó em uma linha deve ser um nó finalOs filhos estão sempre à direita e na mesma linha ou menos do nó pai.Todos os nós não finais devem ter exatamentedois criançasPortanto, todos os nós não finais têm filhos que sãoo primeiro à direita da coluna, o primeiro filho sendo na mesma linha, o segundo filho sendon linhas abaixo deles, onden é o número de nós no lado direito dele.

Podemos ver que, dada qualquer grade válida, existeuma maneira inequívoca "conectar os pontos", por assim dizer; há uma árvore inequívoca sendo representada.

Agora, a "conexão dos pontos" não é mais uma questão de estrutura de árvore binária ... é simplesmente uma questão de decoração. Só precisamos criar um algoritmo para colocar corretamente o-'areia\é para onde eles podem ir, talvez seguindo apenasregras simples de grade / lexicográficas, em vez de regras de estrutura de árvore binária.

Basicamente, isso significa que o problema de renderizar uma árvore agora é o problema mais simples derenderizando uma grade, com decorações extravagantes.

Alguém pode sugerir alguma maneira de formular essas regras? Ou talvez um método completamente diferente?

editar

Eu concebi uma renderização final muito, muito mais 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)

Pode ser mais fácil tentar criar esse, em vez do que eu havia postado anteriormente. Por um lado, ele preserva uma forma de grade bonita e você não precisa se preocupar com linhas diagonais. As linhas são todas mapeadas ao longo de linhas de coluna claramente visíveis. Infelizmente, não é nem de longe tão bonito quanto o primeiro.