Question

树的遍历的方法

Answer 1

为了将一棵树中所有结点按某种次序列表，只须对树根调用相应过程。例如对图7中的树进行前序遍历、中序遍历和后序遍历将分别得到前序列表：A B E F I J
C D G H；中序列表：E B I F J A C G D H；后序列表：E I J F B C G H D A。
下面介绍一种方法可以产生上述3种遍历方式的结点列表。设想我们从树根出发，依逆时针方向沿树的外缘绕行(例如围绕图7中的树绕行的路线如图8所示)。绕行途中可能多次经过同一结点。如果我们按第一次经过的时间次序将各个结点列表，就可以得到前序列表；如果按最后一次经过的时间次序列表，也就是在即将离开某一结点走向其父亲时将该结点列出，就得到后序列表。为了产生中序列表，要将叶结点与内部结点加以区别。叶结点在第一次经过时列出，而内部结点在第二次经过时列出。
在上述3种不同次序的列表方式中，各树叶之间的相对次序是相同的，它们都按树叶之间从左到右的次序排列。3种列表方式的差别仅在于内部结点之间以及内部结点与树叶之间的次序有所不同。
一棵树进行前序列表或后序列表有助于查询结点间的祖先子孙关系。假设结点v在后序列表中的序号(整数)为postorder(v)，我们称这个整数为结点v的后序编号。例如在图7中，结点E，I和J的后序编号分别为1，2和3。
结点的后序编号具有这样的特点：设结点v的真子孙个数为desc(v)，那么在以v为根的子树中的所有结点的后序编号恰好落在postorder(v)- desc(v)与postorder(v)之间。因此为了检验结点x是否为结点y的子孙，我们只要判断它们的后序编号是否满足：
postorder(y)-desc(y)≤postorder(x)≤postorder(y)
前序编号也具有类似的性质。