我们知道,对于二叉树而言,给定的前序遍历和中序遍历能够唯一确定一棵树。那么对于拥有超过两个子节点的一般树而言,前序遍历和中序遍历是否也与树的结构具有一一对应的关系呢?换句话说,对于一棵一般树的元组(前序遍历,中序遍历),它是否唯一对应一棵树,或者会存在多棵树拥有相同的前序遍历和中序遍历的元组?
中序遍历(先访问左子树,再访问根节点,最后访问右子树)不能用于非二叉树(没有左子树和右子树)。显然,前序遍历不能唯一定义树。路径“A,B,C”和以A为根、B和C为子节点的树之间没有区别。然而,前序遍历和后序遍历的组合可以唯一定义树(假设所有节点都是唯一的)。我们可以通过归纳法来证明这一点。显然,空字符串可以唯一定义一个空树。现在,给定一个非空的前序遍历和后序遍历字符串,很明显,前序字符串中的第一个节点(后序字符串中的最后一个节点)是树的根节点R。现在我们需要做的就是识别根节点R的子节点所在的子树(以及相应的前序遍历和后序遍历字符串),因为我们可以通过归纳假设找到它们的结构。设RAaaaaaBbbbbb是前序字符串,aaaaaAbbbbbBR是后序字符串(a和b是任意节点)。显然,A是R的第一个子节点的根节点,因为它是前序字符串中的第一个后继节点。在后序遍历中,该子树以A结束(按照后序遍历的定义)。我们切掉该部分并发现R的第二个子节点必须是B。因为B是后序字符串中的最后一个节点,所以没有更多的子节点。现在我们有两个较小的子问题:Aaaaaa、aaaaaA和Bbbbbb、bbbbbB。我们可以通过归纳假设来解决它们。