13. 二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是2 4 1 5 7 3 6,则该二叉树的后根遍历是( ).A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/08 15:54:21
![13. 二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是2 4 1 5 7 3 6,则该二叉树的后根遍历是( ).A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3](/uploads/image/z/10350071-71-1.jpg?t=13.+%E4%BA%8C%E5%8F%89%E6%A0%91T%2C%E5%B7%B2%E7%9F%A5%E5%85%B6%E5%85%88%E6%A0%B9%E9%81%8D%E5%8E%86%E6%98%AF1+2+4+3+5+7+6%EF%BC%88%E6%95%B0%E5%AD%97%E4%B8%BA%E7%BB%93%E7%82%B9%E7%9A%84%E7%BC%96%E5%8F%B7%2C%E4%BB%A5%E4%B8%8B%E5%90%8C%EF%BC%89%2C%E4%B8%AD%E6%A0%B9%E9%81%8D%E5%8E%86%E6%98%AF2+4+1+5+7+3+6%2C%E5%88%99%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%8E%E6%A0%B9%E9%81%8D%E5%8E%86%E6%98%AF%EF%BC%88++%EF%BC%89.A.+4+2+5+7+6+3+1+++++++++++B.+4+2+7+5+6+3+1++C.+7+4+2+5+6+3+1+++++++++++D.+4+2+7+6+5+3)
13. 二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是2 4 1 5 7 3 6,则该二叉树的后根遍历是( ).A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3
13. 二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是2 4 1 5 7 3 6,则该二叉树的后根遍历是( ).
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1
C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1
13. 二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是2 4 1 5 7 3 6,则该二叉树的后根遍历是( ).A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3
答案选B:4275631
解析:
由先序遍历1 2 4 3 5 7 6可知1为根节点,又由中根遍历2415736可知24为1的左子树,5736为1的右子树即:
1
24 5736
接着分析24的排序,由先跟遍历1243576,2在4前,所以2为根节点,又因为中根遍历也是24,所以4应为右子树,所以有:
1
2 5736
4
接着分析5736的情况.先跟遍历为1243576,3在576前,所以3为根节点;在跟就中根遍历5736可知57在左,6在右,即:
1
2 3
4 57 6
最后分析57的位置,有先根遍历和中根遍历都是57所以5为根节点,7为右子树.
由此得出最终树:
1
2 3
4 5 6
7
容易得到此二叉树的后序遍历为:
4275631,所以选B
(这个我以前自己总结过,只是不会证明,后来看了严蔚敏的《数据结构》第154页终于放心了,这种方法绝对可靠)