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

admin2013-02-04  51

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

选项 A、bdgcefha
B、gdbecfha
C、bdgaechf
D、gdbehfca

答案D

解析 中序遍历的递归算法定义:①遍历左子树;②访问根结点;③遍历右子树。前序遍历的递归算法定义:①访问根结点;②遍历左子树;③遍历右子树。后序遍历的递归算法定义:①遍历左子树;②遍历右子树;③访问根结点。根据前序遍历的结果可知,a是根结点。由中序遍历的结果dgbaechf可知,d、g、b是左子树的结点,e、c、h、f是右子树的结点。再由前序遍历的结果 bdg可知,b是a左边子树的根,由cefh可知,c是a右边子树的根。再由中序遍历的结果dgb可知,d、g是b左边子树的结点,b右边子树无结点。再由前序遍历结果dg可知,d为b左子树的根,g是以d为根的子树的右结点。至此,a的左子树已完全弄清楚了。同样的道理,可以弄清楚以c为根的子树的结点位置。所以可知后序遍历的结果是D。
转载请注明原文地址:https://kaotiyun.com/show/aNup777K
0

最新回复(0)