问答题
假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。【武汉大学2000三、1】【东南大学2000一、1(6分)】【大连理工大学2005二、3(20／4分)】【中国海洋大学2007一、5(8分)】
【正确答案】正确答案：按层次遍历，第一个结点(若树不空)为根，该结点在中序序列中把序列分成左右两部分——左子树和右子树。若左子树不空，层次序列中第二个结点是左子树的根；若左子树为空，则层次序列中第二个结点是右子树的根。对左、右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。该题型的算法参见下面算法设计题第52题。
【答案解析】