一. 二叉树的中序遍历是:HDMIBJNEAFKCG,后序遍历是HMIDNJEBKFGCA,那么它的前序遍历是什么?
前序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树
中序遍历:首先遍历左子树,然后访问跟节点,最后遍历右子树
后序遍历:首先遍历左子树,然后遍历右子树,最后访问根节点
又因为题目中已经给出了
- 中序遍历:HDMIBJNEAFKCG
- 后序遍历:HMIDNJEBKFGCA
step 1:
从后序遍历中可知,最后一个必然是根节点,因此A是根。再根据中序遍历,HDMIBJNE是A的左子树部分,FKCG是右子树部分
step 2:
再根据后序遍历KFGC,所以C是根,同样的方法,K是F的右子树。这样右子树部分就出来了。
sten 3:
根据后序遍历HMIDNJEB,所以B是根;HDMI是B的左子树,JNE是B的右子树;依次类推就可得到整体的二叉树
所以前序遍历的结果就是:
ABDHIMEJNCFKG