填空题

某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是()。

正确答案

来源:www.examk.com

答案解析

根据二叉树的遍历规则,前序遍历是先访问其根节点,然后再依次遍历左右子树。中序遍历是先遍历左子树,再访问根节点,再遍历右子树。
该二叉树的前序遍历访问顺序是abdgcefh,由此可知根节点为a。由中序遍历访问顺序是dgbaechf,由此可知该二叉树的左子树有节点有dgb,右子树节点有echf。
在左子树中,先序遍历序b位于最前,而中序遍历序列中b位于最后,可知节点b无右子树,有左子树。
同理可知,在b的子树中,g只能是d的右孩子,且d无左孩子。
同理可得右子树的结构。
此二叉树的后序遍历序列为:gdbehfca