问题
单项选择题
已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( )。
A.acbed
B.decab
C.deabc
D.cedba
答案
参考答案:D
解析: 中序遍历的递归算法如下:①遍历左子树;②访问根结点;③遍历右子树。前序遍历的递归算法如下:①访问根结点;②遍历左子树;③遍历右子树。后序遍历的递归算法如下:①遍历左子树;②遍历右子树;③访问根结点。由后序遍历结果dabec可知c是根结点,且无右子树。再由左子树的后序遍历结果dabe可知,e是左子树的根结点,且由左子树的中序遍历结果deba可知,d是左子树的左子树结点,b和a是左子树的右子树结点。再次由后序遍历结果ab可知,a是左子树结点。b是根结点。至此,各结点在树中的位置已完全确定。