树的遍历问题
发布时间：2023-04-06 12:57:06 来源：文档文库
小
中
大
字号：
树的遍历问题【问题的提出】给定一棵树，则可以得到它的DFS和BFS序列。比如：123945678BFS序列为：1,2,3,4,5,6,9,7,8。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，那么这棵树可以是：1111222323434434有四棵不同的树可以与给定的BFS,DFS序列对应。根据这个模型，可以设计出一些问题。【构造可行解】构造性问题给定BFS和DFS序列，求任意一棵原树。（或者判断无解）我们按照DFS序列的顺序来构造。很显然DFS[1]=BFS[1]=根，DFS[2]=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-1的极右路径上插入DFS[k]而得到的。可以设Tk-1的极右路径是a1,a2,…,at(t>=2。设DFS[k]在BFS序列中的前驱是v。显然a1=根=BFS[1]。因为k>=3 