Как создать несбалансированное двоичное дерево, разветвляющееся вправо?

Question

Изображение того, что я хочу:

Для тех, кому интересно: эта конкретная цифра взята изЭта статья(Я не смог найти свободно доступную версию) и показываетk-ведра(квадраты), охватывающие все более крупный префикс двоичного пространства идентификаторов.

Я был бы очень признателен, если бы кто-нибудь предложил, как сделать такое дерево:

• Каждый лист — это ведро/квадрат.
• Только у листьев есть ведра.
• Дерево разветвляется вправо, оставляя каждую ветвь вдвое меньше места, чем предыдущая.

Редактировать

Я немного подправил некоторые цифры в блестящем ответе Гонсало Медины, чтобы приблизиться к тому, что мне нужно, но должен признаться, что я понятия не имею, что происходит и как работает код.

Теперь мне бы хотелось сделать дерево шире, чтобы ящики не перекрывали друг друга по вертикальной оси.

\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}

Кроме того, куда мне его поместить, если я захочу разместить текст внутри некоторых полей?

Answer 1

С мощнымforestупаковка:

\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}

Используя значения для l, l sep(для вертикального расстояния), s sep(для горизонтального расстояния) вы можете изменить геометрию дерева (пожалуйста, обратитесь к документации пакета для объяснения этих ключей). Небольшой пример::

\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}

Если в полях должен быть текст, лучше определить для них стиль, чтобы убедиться, что все они будут иметь одинаковую высоту:

\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}