☰

如何创建每个节点上都有链接列表的二叉搜索树？

tag-icon • tag-icon tikz-qtree
如何创建每个节点上都有链接列表的二叉搜索树？

我正在尝试创建一个在每个节点上都有链接列表的二叉搜索树，类似于图片，但不需要蓝色箭头。我目前正在使用它tikz-qtree来创建我的树。

当前树：

\tikzset{every tree node/.style={minimum width=2em,draw,circle},
     blank/.style={draw=none},
     edge from parent/.style=
     {draw, edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}},
     level distance=1.5cm}
\begin{tikzpicture}
  \Tree
  [.2,1
    [.1,2
      [.0,2
        \edge[blank]; \node[blank]{};
        [.0,3
          \edge[blank]; \node[blank]{};
          [.0,4 ]
        ]
      ]
      [.1,4 ]
    ]
    [.2,2 ]
  ]
  \end{tikzpicture}

带链接列表的 BST

答案1

以下是我的做法。此解决方案定义了一种forest样式binary search tree。

对于树中的每个节点，可以在右侧或左侧排版第二个节点，以包含列表。如果需要，应以以下形式指定节点的内容

<content of main node>:<content of secondary node>

由于本例中所有节点的内容都包含逗号，因此格式

{<content of main node>}:{<content of secondary node>}

是需要的。翻译代码并添加一些辅助节点，例如，

\begin{forest}
  binary search tree,
  [{2,1}:{1,1}
    [{1,2}:{0,1}
      [{0,2}:{2,2}
        [,phantom]
        [{0,3}:{1,4}
          [,phantom]
          [{0,4}:{-3,0}]
        ]
      ]
      [{1,4}:{0,-1}]
    ]
    [{2,2}:{-1,1}]
  ]
\end{forest}

生产

二叉搜索树

您说蓝色/绿色箭头不是必需的，所以我将树保留为纯色。但是，如果需要，可以使用tikz或键轻松添加这些箭头。tikz+

完整代码：

\documentclass[border=10pt,multi,tikz]{standalone}
\usepackage{forest}
\forestset{%
  list me/.style={draw, no edge},
  list node/.style={%
    if level=0{%
      label={[draw, anchor=east, label distance=5pt]left:{#1}},
    }{%
      if n=1{%
        insert before={[{#1}, list me]},
      }{%
        if={strequal((content("!u1")),"")}{%
          for nodewalk={fake=u,n=1}{%
            insert before={[{#1},phantom]},
          },
        }{},
        insert after={[{#1}, list me]},
      },
    },
  },
  binary search tree/.style={%
    for tree={%
      circle,
      draw,
    },
    delay={%
      for tree={%
        split option={content}{:}{content,list node},
      },
    },
    before typesetting nodes={%
      where content={}{%
        if nodewalk valid={s}{%
          content/.wrap pgfmath arg={##1}{content("!s")},
        }{},
      }{},
    },
  },
}
\begin{document}
\begin{forest}
  binary search tree,
  [{2,1}:{1,1}
    [{1,2}:{0,1}
      [{0,2}:{2,2}
        [,phantom]
        [{0,3}:{1,4}
          [,phantom]
          [{0,4}:{-3,0}]
        ]
      ]
      [{1,4}:{0,-1}]
    ]
    [{2,2}:{-1,1}]
  ]
\end{forest}
\end{document}

相关内容