Como faço uma árvore binária desequilibrada que se ramifica para a direita?

Question

Uma imagem do que eu quero:

Para aqueles que estão interessados: Este valor específico é retirado deEste artigo(não consegui encontrar uma versão disponível gratuitamente) e programask-baldes(os quadrados) cobrindo um prefixo cada vez maior de um espaço de ID binário.

Eu agradeceria muito se alguém pudesse dar uma sugestão de como posso fazer esse tipo de árvore:

• Cada folha é um balde/quadrado
• Apenas as folhas possuem baldes.
• A árvore se ramifica para a direita, deixando cada galho com metade do espaço do anterior

Editar

Ajustei um pouco alguns dos números da resposta brilhante de Gonzalo Medina para chegar mais perto do que exatamente quero, mas devo confessar que não tenho ideia do que está acontecendo e como o código funciona.

O que eu gostaria agora é deixar a árvore mais larga para que as caixas não se sobreponham no eixo vertical.

\begin{forest}
for tree={parent anchor=south, child anchor=north},
s sep=30pt,
[
  [,draw,text width=4cm,edge label={node[midway,left=12pt]{$1$}}]
  [,shape=coordinate,edge label={node[midway,right=10pt]{$0$}}
    [,draw,text width=2cm,edge label={node[midway,left=4pt]{$1$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right=4pt]{$0$}}
      [,draw,text width=0.5cm,edge label={node[midway,left]{$1$}}]
      [,draw,text width=0.5cm,edge label={node[midway,right]{$0$}}]
    ]
  ]
]
\end{forest}

Além disso, onde eu colocaria se quisesse texto dentro de algumas caixas?

Answer 1

Com os poderososforestpacote:

\documentclass{article}
\usepackage{forest}

\begin{document}

\begin{forest}
for tree={parent anchor=south, child anchor=north},
s sep=30pt,
[
  [,draw,text width=3cm,edge label={node[midway,left=4pt]{$0$}}]
  [,shape=coordinate,edge label={node[midway,right]{$1$}}
    [,draw,text width=2cm,edge label={node[midway,left]{$0$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right]{$1$}}
      [,draw,text width=1cm,edge label={node[midway,left]{$0$}}]
      [,draw,text width=1cm,edge label={node[midway,right]{$1$}}]
    ]
  ]
]
\end{forest}

\end{document}

Usando os valores para l, l sep(para distância vertical), s sep(para distância horizontal) você pode alterar a geometria da árvore (por favor consulte a documentação do pacote para uma explicação sobre essas chaves). Um pequeno exemplo::

\documentclass{article}
\usepackage{forest}

\begin{document}

\begin{forest}
for tree={parent anchor=south, child anchor=north},
for tree={l =-0ex}
[,s sep=3cm
  [,draw,text width=3cm,edge label={node[midway,above left=0pt]{$0$}}]
  [,s sep=1.5cm,shape=coordinate,edge label={node[midway,above right]{$1$}}
    [,draw,text width=2cm,edge label={node[midway,left=8pt]{$0$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right=8pt]{$1$}}
      [,draw,text width=1cm,edge label={node[midway,left=6pt]{$0$}}]
      [,draw,text width=1cm,edge label={node[midway,right=6pt]{$1$}}]
    ]
  ]
]
\end{forest}

\end{document}

Se as caixas tiverem texto, é melhor definir um estilo para elas para garantir que todas tenham a mesma altura:

\documentclass{article}
\usepackage{forest}

\begin{document}
\forestset{
myempty/.style={
  draw,
  text width=#1,
  minimum height=16pt,
  anchor=north
  }
}

\begin{forest}
for tree={parent anchor=south, child anchor=north},
for tree={l =2ex}
[,s sep=1cm
  [texta,myempty=3cm,edge label={node[midway,above left=0pt]{$0$}}]
  [,s sep=1cm,shape=coordinate,edge label={node[midway,above right]{$1$}}
    [textb,myempty=2cm,edge label={node[midway,left=8pt]{$0$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right=8pt]{$1$}}
      [textc,myempty=1cm,edge label={node[midway,left=6pt]{$0$}}]
      [textd,myempty=1cm,edge label={node[midway,right=6pt]{$1$}}]
    ]
  ]
]
\end{forest}

\end{document}