已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( )。

admin2013-02-04  31

问题 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(    )。

选项 A、acbed
B、decab
C、deabc
D、cedba

答案8

解析 中序遍历的递归算法如下:①遍历左子树;②访问根结点;③遍历右子树。前序遍历的递归算法如下:①访问根结点;②遍历左子树;③遍历右子树。后序遍历的递归算法如下:①遍历左子树;②遍历右子树;③访问根结点。由后序遍历结果dabec可知c是根结点,且无右子树。再由左子树的后序遍历结果dabe可知,e是左子树的根结点,且由左子树的中序遍历结果deba可知,d是左子树的左子树结点,b和a是左子树的右子树结点。再次由后序遍历结果ab可知,a是左子树结点。b是根结点。至此,各结点在树中的位置已完全确定。
转载请注明原文地址:https://jikaoti.com/ti/Ecw0FFFM
0

最新回复(0)