早教吧 育儿知识 作业答案 考试题库 百科 知识分享

二叉树的遍历问题若某二叉树的前序遍历访问顺序为abdgcefh,中序遍历访问顺序是dgbaechf,则后序遍历的结点访问顺序是.

题目详情
二叉树的遍历问题
若某二叉树的前序遍历访问顺序为abdgcefh,中序遍历访问顺序是dgbaechf,则后序遍历的结点访问顺序是______.
▼优质解答
答案和解析
你好!首先,我们来看前序遍历为abdgcefh,根据前序遍历的规则(先根节点,其次遍历左子树,最好遍历右子树)可知,a为根节点.又知中序遍历访问顺序是dgbaechf,那么可以判断出左子树的结构:
a
/
g
/ \
d b
又根据中序遍历的规则(先中序遍历左子树,之后为根节点,最好中序遍历右子树)可得到整个二叉树的结构为:
a
/ \
g e
/ \ \
d b h
/ \
c f
既然推出了二叉树的结构图,那么要求后序遍历就显而易见了,已知后序遍历规则(先后序遍历左子树,再后序遍历右子树,最好访问根节点):abgcfhea
初学者最容易将中序遍历弄错,特别是在考虑如本题中e和f的位置时往往会把握不住,多练习几次,并且记住你就一定能做对的!因为我就是初学者.