在二叉树中链接表兄弟

在二叉树中链接表兄弟

我手工构建了这棵二叉树中一些堂兄弟、堂兄弟和堂兄弟对之间的水平链接。我想要一个 tikz 解决方案。特定链接可以硬编码。如果我可以尝试使用线宽,那就太好了。

在此处输入图片描述

编辑:以下是确定有联系的堂兄弟姊妹的方法。

在二叉树中,如果一对节点位于 $N$ 下 $k+1$ 层,并且 $N$ 是它们最近的共同祖先,则它们就是节点 $N$ 的 $k$ 堂兄弟。$0$ 堂兄弟是兄弟姐妹。有 $2^{2k}$ 对 $k$ 堂兄弟,因为您可以通过从 $N$ 以下的树的左半部分选择一个堂兄弟和从右半部分选择一个堂兄弟来形成这样的一对。

在这些配对中,我们挑选出 $2^k$ 对 \emph{亲密
堂兄弟}。如果你将 $N$ 以下 $k+1$ 级的节点编号为左半部分和右半部分的 $1,2,\ldots,2k$,那么亲密的 $k$ 级堂兄弟就是配对

(2,1),(4,2),\ldots,(2k,k)

该图显示了节点 1(实线)和节点 3(虚线)的亲密表兄弟对。

梅威瑟:

%Tree showing kissing cousins
\documentclass{standalone}
\usepackage{tikz-qtree}
\begin{document}
\begin{tikzpicture}[every tree node/.style={draw,circle},
   level distance=1.25cm,sibling distance=.05cm, 
   edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}]

\Tree [.1 
    [.2  
      [.4
        [.8
          [.16
          ]
          [.24
          ]
        ]
        [.12
          [.32
          ]
          [.36
          ]
        ]
      ] 
      [.6 
        [.16
          [.36
          ]
          [.48
          ]
        ]
        [.18
          [.52
          ]
          [.54
          ]
        ]
      ] 
    ]
    [.3
      [.8 
        [.18
          [.41
          ]
          [.54
          ]
        ]
        [.24
          [.66
          ]
          [.72
          ]
        ]
      ] 
      [.9
        [.26
          [.60
          ]
          [.78
          ]
        ]
        [.27
          [.80
          ]
          [.81
          ]
        ]
      ] 
    ] ]
\end{tikzpicture}
\end{document}

答案1

这里有一个建议。你可以制作单个条目节点,然后普通 Ti 就可以访问这些节点Z 命令。为了简化一点,我定义了一种进行 U 形连接的样式。当然,您可以根据需要调整线条样式(宽度、颜色、虚线)。(编辑:修复了连接重叠的问题。)

\documentclass[border=3.14mm]{standalone}
\usepackage{tikz-qtree}
\usetikzlibrary{calc}
\begin{document}
\tikzset{connect u/.style=
{to path={let \p1=($(\tikztotarget)-(\tikztostart)$),
\n1={ifthenelse(\x1>0,-85,-95)},
\n2={ifthenelse(\x1>0,-95,-85)}
in 
(\tikztostart.\n1) -- ++(0,-#1) -|  (\tikztotarget.\n2)
}}}
\begin{tikzpicture}[every tree node/.style={draw,circle},
   level distance=1.25cm,sibling distance=.05cm, 
   edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},
   remember picture]
\Tree [.1 
    [.2  
      [.4
        [.8
          [.16
          ]
          [.\node(24a){24}; 
          ]
        ]
        [.\node(12){12}; 
          [.32
          ]
          [.\node(36){36};
          ]
        ]
      ] 
      [.\node(6){6}; 
        [.16
          [.36
          ]
          [.\node(48){48};
          ]
        ]
        [.\node(18a){18}; 
          [.52
          ]
          [.\node(54a){54};
          ]
        ]
      ] 
    ]
    [.3
      [.\node(8){8};  
        [.\node(18b){18}; 
          [.\node(41){41};
          ]
          [.\node(54b){54};
          ]
        ]
        [.\node(24b){24}; 
          [.\node(66){66};
          ]
          [.\node(72){72};
          ]
        ]
      ] 
      [.9
        [.\node(26){26}; 
          [.\node(60){60};
          ]
          [.\node(78){78};
          ]
        ]
        [.27
          [.80
          ]
          [.81
          ]
        ]
      ] 
    ] ]
\draw[thick] (6) -- (8);  
\draw[thick] (12) edge[connect u=3pt] (18b);   
\draw[thick] (18a) edge[connect u=6pt] (24b);  
\draw[densely dashed] (24b) -- (26);    
\draw[thick] (24a) edge[connect u=3pt] (41);   
\draw[thick] (36) edge[connect u=6pt] (54b);   
\draw[thick] (48) edge[connect u=9pt] (66);    
\draw[thick] (54a) edge[connect u=12pt] (72);   
\draw[densely dashed] (54b) edge[connect u=3pt] (60);   
\draw[densely dashed] (72) edge[connect u=6pt] (78);    
\end{tikzpicture}
\end{document}

在此处输入图片描述

当然我有偏见,但我可能会改用森林。这可以让我们更清楚地看到二元结构。使用@cfr 的这个回答很不错,可以以二进制方式命名二进制中的节点。例如,2级别 2 的节点(按照此约定,最上面的节点具有级别 1)将被称为node-1,其右侧的节点称为node-2。在级别 3,最左侧的节点名为node-1-1,然后是node-1-2,然后node-2-1是 和node-2-2,依此类推。这种表示法似乎使堂兄弟的概念更加合理:堂兄弟有相同数量的1s 和2s。特别是,您不必为节点发明名称,forest 会为您完成这项工作,然后绘制堂兄弟连接非常容易。甚至可以自动化,但不幸的是我不准确理解“堂兄弟”的定义,而且您似乎还想要不同的线条样式,所以我手动完成。

\documentclass[border=10pt,multi,tikz]{standalone}
\usepackage[edges]{forest}
\usetikzlibrary{calc}
\begin{document}
\tikzset{connect u/.style=
{to path={let \p1=($(\tikztotarget)-(\tikztostart)$),
\n1={ifthenelse(\x1>0,-85,-95)},
\n2={ifthenelse(\x1>0,-95,-85)}
in 
(\tikztostart.\n1) -- ++(0,-#1) -|  (\tikztotarget.\n2)
}}}
\begin{forest}
for tree={
    align=center,
    draw,
    circle,
    l sep'+=15pt,
  },
  my label/.style={alias=node-#1,
    % uncomment this if you want to see the node names
    %label={[anchor=south east]above:#1},
  },
  before typesetting nodes={
    for descendants={
      temptoksa/.option=n,
      for nodewalk={
        while={>On>{level}{1}}{u,+temptoksa=-,+temptoksa/.option=n}
      }{},
      my label/.register=temptoksa,
    },
  }
[1 
    [2  
      [4
        [8
          [16
          ]
          [24
          ]
        ]
        [12
          [32
          ]
          [36
          ]
        ]
      ] 
      [6 
        [16
          [36
          ]
          [48
          ]
        ]
        [18
          [52
          ]
          [54
          ]
        ]
      ] 
    ]
    [3
      [8 
        [18
          [41
          ]
          [54
          ]
        ]
        [24
          [66
          ]
          [72
          ]
        ]
      ] 
      [9
        [26
          [60
          ]
          [78
          ]
        ]
        [27
          [80
          ]
          [81
          ]
        ]
      ] 
    ] 
 ]
\draw[thick] (node-2-1) -- (node-1-2);
\draw[thick] (node-1-1-2) edge[connect u=3pt] (node-2-1-1);   
\draw[thick] (node-1-2-2) edge[connect u=6pt] (node-2-1-2);  
\draw[densely dashed] (node-2-1-2) -- (node-2-2-1);    
\draw[thick] (node-1-1-1-2) edge[connect u=3pt] (node-2-1-1-1);   
\draw[thick] (node-1-1-2-2) edge[connect u=6pt] (node-2-1-1-2);   
\draw[thick] (node-1-2-1-2) edge[connect u=9pt] (node-2-1-2-1);   
\draw[thick] (node-1-2-2-2) edge[connect u=12pt] (node-2-1-2-2);   
\draw[densely dashed] (node-2-1-1-2) edge[connect u=3pt] (node-2-2-1-1);   
\draw[densely dashed] (node-2-1-2-2) edge[connect u=6pt] (node-2-2-1-2);    
\end{forest}
\end{document}

在此处输入图片描述

相关内容