题目
请写出下面二叉树[1]的先序、中序、后序遍历序列。A. B CB. D E FC. G H I J
请写出下面二叉树[1]的先序、中序、后序遍历序列。
A. B C
B. D E F
C. G H I J
题目解答
答案
A. B C
解析
本题考查二叉树的先序、中序、后序遍历的知识。解题思路是根据三种遍历方式的规则,对给定的二叉树进行遍历操作。
- 先序遍历规则:根节点 -> 左子树 -> 右子树。
- 中序遍历规则:左子树 -> 根节点 -> 右子树。
- 后序遍历规则:左子树 -> 右子树 -> 根节点。
根据题目所给的二叉树结构(这里可推测出二叉树的层次结构为:根节点是A,A的左子节点是B,右子节点是C;B的左子节点是D,右子节点是E;C的左子节点是F;D的左子节点是G,右子节点是H;E的左子节点是I,右子节点是J),下面进行详细的遍历计算:
先序遍历
- 从根节点A开始,先访问根节点A。
- 接着遍历A的左子树,左子树的根节点是B,访问B。
- 再遍历B的左子树,根节点是D,访问D。
- 遍历D的左子树,根节点是G,访问G。
- G没有左子树和右子树,回到D,遍历D的右子树,根节点是H,访问H。
- 回到B,遍历B的右子树,根节点是E,访问E。
- 遍历E的左子树,根节点是I,访问I。
- 遍历I的右子树,根节点是J,访问J。
- 回到A,遍历A的右子树,根节点是C,访问C。
- 遍历C的左子树,根节点是F,访问F。
所以先序遍历序列为:A -> B -> D -> G -> H -> E -> I -> J -> C -> F。
中序遍历
- 从根节点A的左子树开始,先遍历B的左子树,B的左子树的根节点是D,D的左子树的根节点是G,访问G。
- 回到D,访问D。
- 遍历D的右子树,根节点是H,访问H。
- 回到B,访问B。
- 遍历B的右子树,先遍历E的左子树,E的左子树的根节点是I,访问I。
- 回到E,访问E。
- 遍历E的右子树,根节点是J,访问J。
- 回到A,访问A。
- 遍历A的右子树,先遍历C的左子树,根节点是F,访问F。
- 回到C,访问C。
所以中序遍历序列为:G -> D -> H -> B -> I -> E -> J -> A -> F -> C。
后序遍历
- 从根节点A的左子树开始,先遍历B的左子树,B的左子树的根节点是D,D的左子树的根节点是G,G没有左子树和右子树,访问G。
- 遍历D的右子树,根节点是H,H没有左子树和右子树,访问H。
- 回到D,访问D。
- 遍历B的右子树,先遍历E的左子树,E的左子树的根节点是I,I没有左子树和右子树,访问I。
- 遍历E的右子树,根节点是J,J没有左子树和右子树,访问J。
- 回到E,访问E。
- 回到B,访问B。
- 遍历A的右子树,先遍历C的左子树,根节点是F,F没有左子树和右子树,访问F。
- 回到C,访问C。
- 回到A,访问A。
所以后序遍历序列为:G -> H -> D -> I -> J -> E -> B -> F -> C -> A。