类似 Knuth 的《计算机编程艺术》第 3 卷中的多路树

Question

我想知道是否有人知道如何绘制像 Knuth 的《计算机编程艺术》第 3 卷第 484 页那样的多路树？

它看起来像一个圆形的盒子，其中键的值向左/逆时针旋转 90 度，叶节点为小方块，指针指向位于键中间的下一个节点。

Answer 1

使用的基本方法TikZ：

\documentclass{article}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{positioning}

\newcommand\Rot[2][90]{%
  \rotatebox[origin=c]{#1}{#2}}
\begin{document}

\begin{tikzpicture}[
  node distance=2cm and 1cm,
  mynoder/.style={draw,rounded corners},
  mysq/.style={draw}
]
\node[mynoder,text depth=0.4cm] (root) 
  {\quad$\cdots$\ \ \Rot{$031$}\qquad\Rot{$067$}\qquad\Rot{$097$}\ \ $\cdots$\quad\null};
\node[mynoder,below = of root.south west,anchor=west,text depth=0.8cm] (left) 
  {\Rot{$041$}\quad\Rot{$057$}\quad\Rot{$059$}};
\node[mynoder,below = of root.south east,anchor=east,text depth=0.8cm] (right) 
  {\Rot{$041$}\quad\Rot{$057$}\quad\Rot{$059$}};

\draw ([xshift=-10pt]root.center) -- (left);
\draw ([xshift=10pt]root.center) -- (right);
\foreach \Nodo in {left,right}
{
  \foreach \Corr in {-15,-5,5,15}
  {
    \path ([yshift=-0.2cm,xshift=\Corr]\Nodo.center) -- ++(0,-1.5cm) node[mysq] (\Nodo\Corr) {};
    \draw ([yshift=-0.2cm,xshift=\Corr]\Nodo.center) -- (\Nodo\Corr);
  }
}
\end{tikzpicture}

\end{document}