树的遍历问题

树的遍历问题【问题的提出】给定一棵树，则可以得到它的DFS和BFS序列。给定一棵树，则可以得到它的DFS和BFS序列。DFS序列为：1,2,4,5,3,6,9,7,8。所谓BFS，就是从根节点开始扩展，深度小的优先。对于同一个节点若干个儿子，编号小的优先扩展。所谓DFS，就是从根节点开始扩展，深度大的优先。对于同一个节点若干个儿子，编号小的优先扩展。请特别注意：同一个节点的若干儿子，编号小的优先扩展。这就是说对于-棵树，存在唯一的BFS和DFS遍历序列。但是对于给定的BFS和DFS序列，是不是存在唯一的树和他们对应呢？比如一棵树的BFS序列是(1,2,3,4)，DFS序列是(1,2,3,4)，那么这棵树可以是:有四棵不同的树可以与给定的BFS,DFS序列对应。根据这个模型，可以设计出一些问题。【构造可行解】构造性问题给定BFS和DFS序列，求任意一棵原树。(或者判断无解)我们按照DFS序列的顺序来构造。很显然DFS[1]=BFS[1]=根，DFS⑵=BFS[2]=根的最小编号儿子。以DFS[1]作为根，DFS[2]作为根的儿子，就构成了一棵规模为2的树。

现在假设DFS的前k-1个节点已经建好了树Tk-1。下面考虑把第k个节点(DFS[k])插入到树Tk-1中构成Tk。(k>=3)因为DFS[1],DFS[2],..,DFS[k]这些点中，DFS[k]是在深度遍历中最后访问到的点，所以DFS[k]在Tk中的位置必然是“极右路径”上最末段的点。也就是说Tk是通过在Tk[的极右路径上插入DFS[k]而得到的。可以设Tk_]的极右路径是a1,a2,…，at(t>=2)。设DFS[k]在BFS序列中的前驱是v。显然a1=根=BFS[1]。因为k>=3，所以DFS[k]乏DFS⑵同时DFS[2]=BFS[2],于是就有DFS[k]#BFS⑵。也就是说DFS[k]在BFS序列中的位置不可能是2,所以v^BFS[1]，即v^%。下面分三种情况讨论。第一种情况：存在i(2<=i<t),满足a.=voDFS[k]DFS[k]DFS[k]别无选择，只能给ai1做儿子。请注意：这种情况下DFS[k]必须大于半因为如果DFS[k]<a.，根据“编号小的儿子先遍历”规则，DFS[k]在a.之前就应该已经被遍历。矛盾。因此，如果在这种情况下发现DFS[k]<ai，就可以判定无解了。第二种情况：at=v，且at>DFS[k]。从理论上说，可以有两种插入DFS[k]的方式。但是第二种方案必须满足DFS[k]>at。这显然和我们的条件矛盾。因此在第二种情况下，插入方式也是唯一的。第三种情况：at=v，且at<DFS[k]。此时有点棘手。

DFS[k]DFS[k]DFS[k]DFS[k]因为at<DFS[k]，所以两种情况都是有可能发生的。到底应该取哪种呢？还是都去试探呢？都去试探一次自然是对的，但是复杂度将会很高，相当于是在搜索。我们可以从两种插入方案对以后的影响来分析问题：第一个方案中，如果要让DFS[k]最终成为at的“BFS后继”，就要求at的“右边”、DFS[k]的“左边”不能有任何东西。这实际上就是对以后的插入过程做了一个深度限制。反观第二个方案，不管之前、之后的点如何插入树中，DFS[k]都铁定是at的“BFS后继”了。所以第二个方案对之后的插入没有任何影响。因此我们从直观上来看，应该选择第二个方案插入。严谨的看，如果第一种方案最终构造成功了可行解：DFS[k]DFS[k]必然因为DFS[k]是at的“BFS后继"，所以在at的这一深度上，at“右边”不存在任何点（否则如果存在，at的后继就会是它、而不是DFS[k]）必然这样的话，可以把DFS[k]往上“提”：DFS[k]

DFS[k]经过调整之后，无论BFS还是DFS序列，都不会改变。也就是说如果方案一可以构造出可行解，方案二也必然可以构造出可行解。所以我们可以大胆的选择方案二插入。ai=v。DFS[k]ai=v。DFS[k]这时只能把DFS[k]插在at之后。综上，对所有的情况，我们都能找到唯一的方式插入，最终得到一棵树T。从构造的过程看，Tn肯定完全满足DFS序列。反过来，只要问题有解，TnTOC\o"1-5"\h\z一定也可以符合BFS序列（因为构造过程中每一步都是必要的）。n最后只要检验Tn的BFS序列和输入的BFS序列是否相同，即可判断问题是否有解。n进一步的很容易发现，Tn不仅是一组任意解，它也是深度最小的解。（这一点很重要）n【进一步的扩展】现在把问题扩展一下计数问题给定一棵树的BFS和DFS序列，问有多少棵树满足要求。从构造的角度讲，能造成多解的只有上面提到的“第三种情况”。DFS[k]DFS[k]DFS[k]DFS[k]如果采用左边的方案，必须满足两个条件:1、已经插入的点中，不存在比at深度大的点。（如果存在，DFS[k]的“BFS前驱”就变成了它，而不是at）。2、以后插入的点，深度都必须小于at的深度。（如果存在深度和at相同

的点，at的后继就会是这个点，而不是DFS[k]）上一节提到了，根据本文已经提出的方法构造，生成的是深度最小的树。而第二点正好要求“以后的点深度都必须小于气的深度”。所以，如果我们在插入DFS[k]的时候采取了第一种插入方案，那么要检验这种插入方案是不是可行，只要把以后的点都按之前提出的正常方法插入即可。如果最后得到的树的BFS序列仍然和输入的BFS序列全等，那么就证明在第k步的时候选择第一种方案是可行的。我们首先把深度最小的树按照上一节提出的方法构造出来。不可调整点（、不可调整点），/上、不可调整点图中黑色点是插入过程中的第一种情况，红色点是第二种情况，蓝色点是第三种情况，黄色是第四种情况。从理论上说，蓝色点都有两种插入方式，但是可以明显的看到，最左边的那个蓝色点是“无可选择”的。如果把它往下调，就违反了上面提出的第二条“以后插入的点，深度都必须小于at的深度”。因为后面的点插入都是按照第一节提出的基本构造法进行的，所以得到的是“深度最小的树”；如果连深度最小的树都不能满足“深度小于at的深度”，其他的插入方式就更加不用提了。就上面那棵树而言，可“调整”的点如下图蓝点所示：有5个点，每个点都有2种插入方式，也就是25=32棵不同的树。观察上面用粗红线条框出来的部分，除了每一层的第一个点，其他的点都是“可调整点”。这个用红线框出来的部分有一个奇妙的性质：它的BFS和DFS序列完全相

令L=max{xIBFS[n-x+1],BFS[n-x+2],…,BFS[n]这些点的诳；5和BFS序列相应在数列BFS[n-L+1],BFS[n-L+2],…，