如何排版前缀树（又名 trie）

Question

我目前正在尝试排版前缀树（也称为 trie）。我可以用 TiKZ 很好地制作一棵树，但我发现自己无法让前缀树节点以可接受的方式绘制。我附上了一张白板画的前缀树，其中包含单词“ghost”、“green”、“tan”、“trie”和“trie”。我似乎无法弄清楚如何让 TiKZ 绘制相同的树。任何帮助都将不胜感激。

我尝试过矩形分割，这样可以将节点分成上下两部分，但是如何细分下部呢？另外，如何让下部的箭头明确来自字母，而不是来自周围的节点？

Answer 1

这里真正的技巧是如何将外框放在内节点周围。您可能已经发现，不可能将一个嵌入\node另一个中\node。将一个嵌入另一个中也是一个很糟糕的想法tikzpicture（这似乎是解决这个问题的另一种方法。这是一个基于的解决方案马克·埃弗里特的回答这个问题tikz：一个固定宽度的大盒子，里面有较小的盒子。

它使用shapes.multipart库来分割树节点，使用fit库来在树节点周围放置外框。positioning和calc库用于计算外节点文本的位置和路径edge from parent，这样尽管树是在内部节点上构建的，但分支实际上连接在看起来像是外部节点边缘的点上。

更新：基于这个问题：如何使 tikz 多部分节点部分具有统一的大小？我添加了一些代码来使所有内部节点（拆分和单个）的大小统一。

\documentclass{article}
\usepackage{tikz-qtree}
\usetikzlibrary{fit,backgrounds,shapes.multipart,calc,positioning}
\begin{document}
\tikzset{
    sibling distance=2cm,
    level distance=2.5cm,
    split/.style={draw, 
        rectangle split, rectangle split parts=2,draw,inner
        sep=0pt,rectangle split horizontal,minimum size=3ex,text width=3ex,align=center,rectangle split part align=base},
    boxed/.style={draw,minimum size=3ex,inner sep=0pt,align=center},
    edge from parent/.style={draw, 
        edge from parent path={[->,thick]
        (\tikzparentnode)  -- ($(\tikzchildnode.north) + 25*(0pt,1pt)$) }}
}

\begin{tikzpicture}
\Tree [.\node[split] (M1) {g\nodepart{two}t}; 
                [.\node[split] (M2) {h\nodepart{two}r}; 
                    [.\node[boxed] (M3) {o};
                        [.\node[boxed] (M4) {s};
                            [.\node[boxed] (M5) {t}; 
                                [.\node[boxed] (E1) {};]
                            ]
                        ]
                    ]
                    [.\node[boxed] (M6) {e};
                        [.\node[boxed] (M7) {e};
                            [.\node[boxed] (M8) {n};
                                [.\node[boxed] (E2) {};]
                            ] 
                        ]
                    ]
                ]  
                [.\node[split]  (M9) {a\nodepart{two}r};
                    [.\node[boxed] (M10) {n};
                        [.\node[boxed] (E3) {};]
                    ]
                    [.\node[split] (M11) {e\nodepart{two}i};
                        [.\node[boxed] (M12) {e}; 
                            [.\node[boxed] (E4) {};]
                        ]
                        [.\node[boxed] (M13) {e};
                            [.\node[boxed] (E5) {};]
                        ] 
                    ]
                ]
            ]
\begin{pgfonlayer}{background}
\foreach \x in {1,...,13}{
    \node (A\x)  [above =5pt of M\x] {Middle};
    \node[draw,red,] [fit=(M\x) (A\x) ] {};}
\foreach \x in {1,...,5}{
    \node (B\x)  [above =5pt of E\x] {End};
    \node[draw,red,] [fit=(E\x) (B\x) ] {};}
\end{pgfonlayer}
\end{tikzpicture}
\end{document}