经典指数          
原因
1164
浏览数
0
收藏数
 

二叉树的前序遍历是:-+abc*de/f,后序遍历是:bad*c+f/e-,则层序遍历和中序遍历依次为

     举报   纠错  
 
切换
1 个答案
首先,这道题所给序列中的字符没有实际含义,不能以符号的原本含义来推理本题(因为在尝试将后序序列当作算术表达式的后缀式来进行计算验证时,最终存储操作数的栈未能清空); 接下来,常规的解题思路当然还是先还原出二叉树,当然只由先、后序遍历序列是不能确定一棵树的,但是我们可以还原出树的大致轮廓,过程如下: 确定树的根节点:“先序的首字符” 和 “后序的尾字符” 相同,为树的根节点; 判断树的左、右子树节点集合:设先序顺序为 "根 - 左右(A)",后序顺序为 “左右(B) - 根”,则 A 的首字符A-Head为某子树的根节点(如果两子树均存在,它是左树的根,但是如果有一棵子树不存在,那边我们就无法判断它是谁的根),在B序列中找出A-Head的位置,若B中A-Head位于尾部,则说明有一棵子树为空(但是我们无法判断是左还是右,画图时需要以竖直向下的边连接根与子树,表明子树的左右位置无法确定),而若A-Head位于B中间的某个位置,则该位置便是左右子树序列的分界点,左右子树的节点序列由此确定; 递归判断:左右子树的序列与主序列具有相同性质,递归直至确定了叶子节点; 本题还原出来的二叉树结构如下图所示,它的层次遍历序列是确定的,但是中序遍历序列由于无法确定节点b关于a的左右位置,b在左,则b先输出,b在右,则a先输出,所以本题选项A、B均正确:
 
切换
撰写答案
扫描后移动端查看本题