408数据结构第5章：二叉树遍历序列题——技巧、判断与真题型总结

适用考研408数据结构章节第5章 树与二叉树重点题型已知两种遍历求第三种遍历判断一棵二叉树能否唯一确定已知前序和后序判断中序可能/不可能判断“前序与后序互逆”时二叉树的结构性质一、先把三种遍历顺序记死前序根 - 左 - 右 中序左 - 根 - 右 后序左 - 右 - 根最重要的两个定位前序第一个结点 根 后序最后一个结点 根而中序的作用是用根结点把序列切成左子树和右子树所以这类题最核心的一句话是前序/后序负责找根中序负责切左右。二、哪两种遍历能唯一确定二叉树这是408非常常见的概念题。已知遍历是否一般能唯一确定二叉树前序 中序能后序 中序能前序 后序一般不能原因很简单。如果有中序一旦知道根就能立刻知道根左边 左子树 根右边 右子树但只有前序和后序时如果某个结点只有一个孩子就无法判断这个孩子究竟是左孩子 还是 右孩子所以有中序基本能还原 没中序一般不唯一。三、题型1已知前序 中序求后序例如中序ABCD 前序CABD要求后序。解题过程前序第一个结点一定是根所以根为C在中序序列中找到 CAB | C | D因此左子树AB 右子树D左子树有2个结点所以从前序去掉根 C 后左子树前序AB 右子树前序D继续看左子树前序AB 中序AB前序第一个 A 是根。在中序中A | B说明 A 没有左孩子B 是 A 的右孩子。整棵树为C / \ A D \ B按照后序左 - 右 - 根左子树后序BA右子树D最后访问根 CBADC所以后序 BADC四、已知前序 中序的固定模板以后不需要重新想直接按这个流程1. 前序第一个元素找根 2. 在中序中找到根 3. 中序按根切成 左子树 | 根 | 右子树 4. 根据左右子树结点数量 去切前序序列 5. 对左右子树重复上述过程 6. 最后按题目要求写出后序五、题型2已知后序 中序求前序方法完全类似只改一个地方后序最后一个元素 根然后仍然使用中序左子树 | 根 | 右子树去切分。所以记忆前序找第一个根 后序找最后一个根 中序负责切左右六、题型3前序 后序判断中序是否可能例如前序ABCD 后序DCBA这时候不能直接说“可以唯一还原”。因为前序 后序 一般不能唯一确定二叉树但我们可以根据它们判断树的大致结构。前序A B C D后序D C B A二者正好互为逆序这说明整棵树实际上退化成了一条链A | B | C | D但是每一条边到底向左还是向右并不唯一。例如A \ B \ C \ D可以。下面这样也可以A / B / C / D甚至左右可以混合。所以前序 后序确定的是“结点先后关系” 但不一定确定每个单孩子结点的左右方向。七、怎么判断中序序列可能/不可能继续以上例前序ABCD 后序DCBA可能出现的中序并不是任意排列。对于这棵单链树每一个结点只有一个孩子。如果孩子是左孩子中序 子树 根如果孩子是右孩子中序 根 子树所以可以递归地产生合法中序。例如可能出现ABCD BCDA DCBA CDBA但CBDA无法通过这种“单链左右选择”产生因此不可能。这类题的技巧是前序后序若互逆 - 先判断为单链结构 - 再逐项验证中序是否能由“左挂/右挂”得到八、题型4前序和后序正好相反树满足什么条件这是性质判断题。若前序A B C D 后序D C B A则说明每个结点至多只有一个孩子。因为只要某个结点同时拥有左、右两个孩子前序和后序中左右子树的整体顺序关系就不可能完全互逆。所以这种树会退化成一条链。如果共有 n 个结点树高 n因此遇到题目若二叉树前序遍历和后序遍历正好相反 则该树满足什么条件优先想到退化成单链 - 高度 结点数注意不能说“所有结点都没有左孩子” 也不能说“所有结点都没有右孩子”因为链既可以向左也可以向右还可能左右混合。九、为什么“前序 后序”一般不能唯一确定看最简单的例子前序AB 后序BA可能是A / B也可能是A \ B两棵树前序都为 AB 后序都为 BA所以不能唯一确定。真正缺少的信息就是B 是左孩子还是右孩子这也是所有“前序后序不唯一”问题的本质。十、考试中最常见的三类题1. 已知前序 中序求后序固定前序找根 中序切分 递归2. 已知后序 中序求前序固定后序最后找根 中序切分 递归3. 已知前序 后序判断可能性第一反应一般不能唯一确定然后再看题目是否有特殊条件。例如前序和后序互逆马上联想到单链树 高度 结点数十一、选择题秒杀技巧技巧1有中序先切不要先画整棵树。先写左子树 | 根 | 右子树很多题直接就出来了。技巧2前序看头后序看尾前序第一个 根 后序最后一个 根这是最稳定的定位方法。技巧3前序 后序先判断“不唯一”除非题目额外给条件否则前序 后序不要直接唯一还原。技巧4前后互逆先想“链”看到前序ABCD... 后序...DCBA先想到每个结点最多一个孩子也就是树退化成链十二、常见错误错误1把中序的第一个结点当根错误。中序不能直接确定根。只有先知道根是谁才能利用中序切左右。错误2看到前序后序就开始唯一画树错误。前序后序一般不唯一错误3前后互逆就认为只能全左或全右错误。左右方向可以混合。真正确定的是每个结点至多只有一个孩子错误4切序列时只看字符不看子树结点数量例如中序切出左子树有3个结点那么去切前序/后序时也必须严格取3个结点。十三、考场统一流程遇到遍历序列题先问三个问题1. 根是谁 2. 能不能利用中序切左右 3. 这两种遍历能不能唯一确定然后分类前序中序 - 前序找根中序切分 后序中序 - 后序找根中序切分 前序后序 - 一般不唯一 - 再根据题目额外条件判断十四、10秒速记前序根左右 中序左根右 后序左右根 前序第一个是根 后序最后一个是根 前中唯一 后中唯一 前后一般不唯一 前后互逆 树退化成链 高度 结点数十五、最后只背三句话先找根 有中序就切分 没中序一般不唯一。这三句话基本覆盖408中绝大多数二叉树遍历序列选择题。