沪教版（2019）选修1第四单元 二叉树 练习及参考答案

中小学教育资源及组卷应用平台
第四单元练习题及参考答案
1.假设有一个八位二进制编码，通过图4-13所示二叉树的后序遍历可以得到该二进制编码，请写出该编码。
参考答案：
01000110
分析：
后序遍历是先访问左子树，再访问右子树，最后访问根节点（对于子树也采用此规则遍历）。对上述二叉树进行后序遍历的过程如下图所示。
2.已知算术表达式8-(6-4)*2+5,构建并画出表达式二叉树，将该算术表达式转换成前缀表达式，尝试利用前缀表达式完成计算。
参考答案：
表达式二叉树如下图所示。
前缀表达式：＋－8＊－６４２５
前缀表达式的计算过程如下所示：
＋－8＊－６４２５
　　　＊２２
　－８４
＋４５
９
分析：
对表达式二叉树进行先序遍历可以得到前缀表达式。对上图所示二叉树的先序遍历过程，如下图所示，对应的前缀表达式为＋－8＊－６４２５。
3.在先序遍历序列中添加空子树，标记后可以唯一确定二叉树。已知某二叉树带标记的先序序列为：ABD EF C 手，画出该二叉树，并写出它的中序遍历和后序遍历序列。
参考答案：
表达式二叉树如下图所示。
中序遍历序列：ＤＢＦＥＣＧＡ
后序遍历序列：ＤＦＧＣＥＢＡ
分析：
对上图所示二叉树的中序遍历和后序遍历过程如下图所示。
　　　
　　　　　　中序遍历　　　　　　　　　　　　　　　　后序遍历
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)