我正在尝试改编以下信息在 tikz 森林顶部画线可视化二叉树的有序遍历。
我尝试定义一个按序遍历，模仿\forest@node@@foreachforest.sty 中的定义，但显然我做错了，因为下面的示例给出了“缺失数字，视为零”错误。我完全不确定我做错了什么。
目的是通过首先执行左子节点，然后是当前节点，然后是右子节点（递归）来进行遍历；我可以假设节点最多有两个子节点。
任何帮助都非常感谢！谢谢，
克里斯托夫
\documentclass{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta}
\makeatletter
\def\forest@node@@forself#1{%
\ifnum\forest@cn=0
\else
\forest@forthis{#1}%
\fi
}%
\def\forest@node@@foreachinorder#1#2#3{%
% #1 = do what
% #2 = @first/@last
% #3 = @last/@first
\ifnum\forestove{#2}=0
\else\@escapeif{%
\forest@forthis{%
\edef\forest@cn{\forestove{#2}}%
\forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
}%
}\fi
\forest@forthis{#1}%
\ifnum\forestove{#3}=0
\else\@escapeif{%
\forest@forthis{%
\edef\forest@cn{\forestove{#3}}%
\forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
}%
}\fi
}
\forestset{
define long step={tree in-order}{}{\forest@node@@foreachinorder{\forest@nodewalk@makestep}{@first}{@last}}
}
\makeatother
\forestset{%
declare keylist register={through},
through={},
circles tree/.style={%
for tree={circle, draw, fill=white, align=center},
},
tracing tree/.style={%
delay={%
for #1={%
if phantom={}{through+/.option=name},
}
},
before drawing tree={%
tikz+/.wrap pgfmath arg={%
\foreach \i [count=\j, remember=\i as \k] in {##1} \ifnum\j>1 \draw [densely dashed, -Stealth] (\k.west) -- (\i.west)\fi;
}{(through)}
},
}
}
\newcommand*\tracetree[1][tree]{%
\begin{forest}
circles tree,
tracing tree=#1,
[$a$
[$b$
[$d$
[$h$]
[,phantom]
]
[$e$
[$i$]
[$j$]
]
]
[$c$
[$f$
[,phantom]
[$k$]
]
[$g$]
]
]
\end{forest}%
}
\begin{document}
\tracetree[tree]
\end{document}
答案1
我快到了！我遗漏的主要内容是define long step尝试定义一种风格，它与其他树遍历方法（内置于 forest.sty）的定义方式不同。
在我使用的调用中加上define long step关闭自动样式生成的调用，这样它就可以正常工作了。下面的工作示例。
\documentclass{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta}
\makeatletter
\def\forest@node@@forself#1{%
\ifnum\forest@cn=0
\else
\forest@forthis{#1}%
\fi
}%
\def\forest@node@@foreachinorder#1#2#3{%
% #1 = do what
% #2 = @first/@last
% #3 = @last/@first
\ifnum\forestove{#2}=0
\else\@escapeif{%
\forest@forthis{%
\edef\forest@cn{\forestove{#2}}%
\forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
}%
}\fi
\forest@forthis{#1}%
\ifnum\forestove{#3}=0
\else\@escapeif{%
\forest@forthis{%
\edef\forest@cn{\forestove{#3}}%
\forest@node@@forself{\forest@node@@foreachinorder{#1}{#2}{#3}}%
}%
}\fi
}
\def\forest@node@foreachinorder#1{%
\forest@node@@foreachinorder{#1}{@first}{@last}%
}
\let\forest@nodewalkstephandler@styletrueorfalse\forest@nodewalkstephandler@stylefalse
\forestset{
define long step={tree in-order}{}{\forest@node@foreachinorder{\forest@nodewalk@makestep}}
}
\let\forest@nodewalkstephandler@styletrueorfalse\forest@nodewalkstephandler@styletrue
\makeatother
\forestset{%
declare keylist register={through},
through={},
circles tree/.style={%
for tree={circle, draw, fill=white, align=center},
},
tracing tree/.style={%
delay={%
for #1={%
if phantom={}{through+/.option=name},
}
},
before drawing tree={%
tikz+/.wrap pgfmath arg={%
\foreach \i [count=\j, remember=\i as \k] in {##1} \ifnum\j>1 \draw [densely dashed, -Stealth] (\k.west) -- (\i.west)\fi;
}{(through)}
},
}
}
\newcommand*\tracetree[1][tree]{%
\begin{forest}
circles tree,
tracing tree=#1,
[$a$
[$b$
[$d$
[$h$]
[,phantom]
]
[$e$
[$i$]
[$j$]
]
]
[$c$
[$f$
[,phantom]
[$k$]
]
[$g$]
]
]
\end{forest}%
}
\begin{document}
\tracetree[tree in-order]
\end{document}
答案2
确实不建议使用依赖 Forest 内部的代码。例如，\forestove不应使用。在某些情况下，软件包没有提供替代方案。但是，Forest 确实为许多这些宏提供了包装器，这些是更好的选择。特别是，当 Forest 更新时，您的代码不太可能中断。
话虽如此，我认为应该可以使用大多数更高级的功能来实现这一点，例如使用节点遍历等。我不确定下面的代码中是否有可行的算法。如果我理解了你的代码，我会尝试使用你的代码，但我没有。
和我知道我没有一个优雅的或特别简约的。
然而，我（终于！）得到了一个足以传达总体思想的。
我不太擅长弄清楚如何在树林里行走。
基本思想是使用标准 Forest 语法定义一些新的寄存器和选项。
declare boolean={two kids}{0},
declare count={ordered}{-1},
declare count register={ordering},
declare toks register={order list},
order list={},
ordering'=0,
order list类似于您的through。two kids用于标记具有两个子节点的节点，其第二个子节点不是幻影。ordered是用于排序的整数。（您实际上需要的只是一个布尔值，但我这样做是为了计数可用于标记节点，主要用于调试目的。）ordering是用于处理的整数。
\documentclass[border=10pt]{standalone}
\usepackage{forest}
\forestset{
declare boolean={two kids}{0},
declare count={ordered}{-1},
declare count register={ordering},
declare toks register={order list},
order list={},
ordering'=0,
define long step={in order walk}{}{
c,
if n children=0{tempcountb'=1}{tempcountb/.min={>O{ordered}}{descendants}},
until={> R_< {tempcountb}{0} }{
u,
tempcountb/.min={>O{ordered}}{descendants}
}
},
in order/.style={
for tree={
circle, draw, minimum size=5ex, align=center, inner sep=0pt, anchor=mid, math content
},
delay={
where={> On>{n children}{1} }{
if={> On= {!2.phantom}{1} }{}{two kids}
}{},
where phantom={ordered=100}{},
},
before typesetting nodes={
ordering'=0,
where n children=0{
if n=1{
for in order walk={
order me,
}
}{
for nodewalk={reverse=in order walk}{order me},
tempcounta'=0,
for nodewalk={
until={> R_< O_= | {tempcounta}{0} {level}{0} }{
u,
if nodewalk valid={2}{
tempcounta/.min={>{O}{ordered}}{2,tree}
}{}
}
}{order me},
},
}{}
},
order me/.style={
if={>O_<O_=&{ordered}{0}{phantom}{0}}{
ordering'+=1,
label/.register=ordering,
ordered/.register=ordering,
if={> R+tt= {order list}{} }{}{order list+={,}},
order list+/.option=name,
}{},
},
/tikz/every label/.style={red, font=\footnotesize},
tikz+={
\edef\tempa{\foresteregister{order list}}
\foreach \i [count=\j, remember=\i as \l] in \tempa \ifnum\j=1\else \draw [gray, densely dashed, ->] (\l.west) -- (\i.west)\fi;
},
},
}
\begin{document}
\begin{forest}
in order
[a
[b
[d
[h]
[,phantom]
]
[e
[i]
[j]
]
]
[c
[f
[,phantom]
[k]
]
[g]
]
]
\end{forest}
\end{document}
正如我所说，该算法并不简洁，但代码至少应该展示一种不太危险的解决问题的方法。
