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

Question

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

Answer 1

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