- 2022tysc0306 的博客
二叉树的遍历
- 2024-9-5 13:29:11 @
给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG。请问这棵树的正确后序遍历结果是什么? A. EDBGFCA B. EDBGCFA C. DEBGFCA D. DBEGFCA
解析:
- 从前序遍历中,我们知道A是根节点。
- 在中序遍历中, A之前的部分DEB是左子树, A之后的部分CFG是右子树。3. 对于左子树DEB,从前序遍历中我们知道B是左子树的根节点。
- 在中序遍历中, B之前的部分DE是B的左子树。
- 对于左子树DE,从前序遍历中我们知道D是左子树的根节点, E是D的右子节点。
- 对于右子树CFG,从前序遍历中我们知道C是右子树的根节点。
- 在中序遍历中, C之后的部分FG是C的右子树。
- 对于右子树FG,从前序遍历中我们知道F是右子树的根节点, G是F的右子节点。