☰

前两种情况的代码

tag-icon • tag-icon tikz-pgf tikz-trees
前两种情况的代码

我尝试用我以前学过的方法表示 AVL，我发现这种方法比现在最常见的书籍更直观。下面显示了具有我感兴趣的特征的原始图像Niklaus Wirth 1986 年著作还有一些手写笔记。

虽然可视化可能很具体，但表示 AVL 是计算机科学的一般数据结构概念，其目的实际上是将此类绘图用作讲义。所以我相信它可以对更广泛的受众有用。

在此处输入图片描述

从这本书中，我试图准确地得到它所显示的内容：Some nodes as circles，，some as long vertical rectangles虚线突出显示树的底部，以及一个带有 X 的单个节点，表示要删除的节点。一些矩形停留在上方、内部和下方，如图所示。我一直试图将虚线表示为某种 tikz 节点并相应地定位，但没有成功。

在此处输入图片描述

从手写笔记中，我试图获取numbers around the nodes (-2, -1, h-1, etc)矩形上的字母“A、B、C、D”以及circle oriented arrows to indicate rotation direction。

我能够找到方法来表示数字另一个问题也试图代表树的三角形部分但将他们的最小示例修改为我想要的样子特别有挑战性。

答案1

基于 TikZforest包裹似乎可以相对高效地完成工作。以下示例应该可以帮助您入门。

我定义了两种节点样式，

  • circnode将节点格式化为圆形
  • rectnode=<num>将节点格式化为矩形，其高度等于<num>x.5cm

此外，我定义了一个宏\crossnode，用于将交叉框附加到指定位置（在您的示例中，这通常是(some rectnode.south)）

最后，手动绘制两条虚线并放在背景层上。

前两种情况的代码

\documentclass{article}
\usepackage{forest}
\usetikzlibrary{backgrounds}


\forestset{
  circnode/.style={circle,draw,minimum size=.5cm,inner sep=0},
  rectnode/.style={draw,minimum width=.5cm,fill=white,minimum height=#1*.5cm,child anchor=north,anchor=north},
}
\newcommand\crossnode[2][anchor=north]{
  \node(temp)[draw,fill=white,minimum size=.5cm,yshift=\pgflinewidth,#1]at(#2){};
  \draw(temp.north west)--(temp.south east) (temp.north east)--(temp.south west);
}

\begin{document}
\begin{forest}
  for tree={l+=.5cm,s sep=1cm},
  [
    [B,circnode
      [A,circnode
        [,rectnode=3,name=n][,rectnode=3]
      ]
      [,rectnode=3]
    ]
  ]
  \crossnode[anchor=north]{n.south}
  \begin{scope}[on background layer]
    \draw[dashed,thin] let \p1=(temp.north), \p2=(current bounding box.west), \p3=(current bounding box.east) in
    (\x2-.5cm,\y1)--(\x3+.5cm,\y1) (\x2-.5cm,\y1+.5cm)--(\x3+.5cm,\y1+.5cm);
  \end{scope}
\end{forest}

\begin{forest}
  for tree={l+=.5cm,s sep=1cm},
  [
    [C,circnode
      [A,circnode,
        [,rectnode=3]
        [B,circnode
          [,rectnode=2,name=n1]
          [,rectnode=2,name=n2]
        ]
      ]
      [,rectnode=3]
    ]
  ]
  \crossnode{n1.south}
  \crossnode{n2.south}
  \begin{scope}[on background layer]
    \draw[dashed,thin] let \p1=(temp.north), \p2=(current bounding box.west), \p3=(current bounding box.east) in
    (\x2-.5cm,\y1)--(\x3+.5cm,\y1) (\x2-.5cm,\y1+.5cm)--(\x3+.5cm,\y1+.5cm);
  \end{scope}
\end{forest}
\end{document}

输出

在此处输入图片描述

相关内容