问题 单项选择题

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

A.acbed

B.decab

C.deabc

D.cedba

答案

参考答案:D

解析: 中序遍历的递归算法如下:①遍历左子树;②访问根结点;③遍历右子树。前序遍历的递归算法如下:①访问根结点;②遍历左子树;③遍历右子树。后序遍历的递归算法如下:①遍历左子树;②遍历右子树;③访问根结点。由后序遍历结果dabec可知c是根结点,且无右子树。再由左子树的后序遍历结果dabe可知,e是左子树的根结点,且由左子树的中序遍历结果deba可知,d是左子树的左子树结点,b和a是左子树的右子树结点。再次由后序遍历结果ab可知,a是左子树结点。b是根结点。至此,各结点在树中的位置已完全确定。

单项选择题
问答题 简答题