吉林省专升本数据结构习题、参考答案及解析
——二叉树的遍历和构造
1、已知一棵二叉树如下图所示，请写出该二叉树的前序、中序、后序、层序遍历序列。
参考答案
前序遍历：ABDCEFGH
中序遍历：BDACGFHE
后序遍历：DBGHFECA
层序遍历：ABCDEFGH
解析：前序遍历是D(根)L(左子树)R(右子树)的顺序，左右子树也需要进行前序遍历。中序遍历是LDR顺序，后序遍历是LRD顺序。层序遍历是从上层到下层同层之间从左到右的顺序进行遍历。
2、已知一棵二叉树的前序和中序遍历序列分别是ABCDEFH和BCAEDFH，构造该二叉树，并写出后序遍历序列。
参考答案
后序遍历序列：CBEHFDA
二叉树的遍历及应用实验报告解析： 1）、前序遍历的顺序是DLR，所以序列的第一个结点是根结点。
2）、中序遍历的顺序是LDR，在前序确定了根结点的情况下，中序序列能区分左右子树。
3）、左右子树的构造方法重复1、2即可。
3、已知一棵二叉树的中序和后序遍历序列分别是ACBEFDG和CFEGDBA，构造该二叉树，并写出前序遍历序列。
参考答案
前序遍历：ABCDEFG
解析：后序和中序构造二叉树的方法参考前序和中序构造二叉树的方法。后序遍历LRD顺序，确定序列的最后一个元素是根结点，再用中序分左右子树。
4、已知一棵表达式树的前序遍历序列和中序遍历序列分别是-*+abcd和a+b*c-d。构造该表达式树，并写出后序遍历序列。
参考答案
后序遍历：ab+c*d-
解析：表达式树的分支结点应该是+-*/这类运算符，而叶子结点放abcd这些操作数。在一些题目中会出现重复使用的运算符，通过这个性质就能区分出正确的表达式树。
5、已知一棵表达式树的中序遍历序列和后序遍历序列分别是a+b*c-d+e/f和ab+c*de+f/-。构造该表达式树，并写出前序遍历序列。
前序遍历：-*+abc/+def

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。