沪教版（2019）选修1 数据与数据结构第四单元 二叉树本章综合与测试精品课堂检测

这是一份沪教版（2019）选修1 数据与数据结构第四单元 二叉树本章综合与测试精品课堂检测，共3页。
第四单元练习题及参考答案1.假设有一个八位二进制编码，通过图4-13所示二叉树的后序遍历可以得到该二进制编码，请写出该编码。参考答案：01000110分析：后序遍历是先访问左子树，再访问右子树，最后访问根节点（对于子树也采用此规则遍历）。对上述二叉树进行后序遍历的过程如下图所示。 2.已知算术表达式8-(6-4)*2+5,构建并画出表达式二叉树，将该算术表达式转换成前缀表达式，尝试利用前缀表达式完成计算。参考答案：表达式二叉树如下图所示。前缀表达式：＋－8＊－６４２５前缀表达式的计算过程如下所示：＋－8＊－６４２５　　　＊２２　－８４＋４５９分析：对表达式二叉树进行先序遍历可以得到前缀表达式。对上图所示二叉树的先序遍历过程，如下图所示，对应的前缀表达式为＋－8＊－６４２５。 3.在先序遍历序列中添加空子树，标记后可以唯一确定二叉树。已知某二叉树带标记的先序序列为：ABD∳EF∳∳C∳∳手，画出该二叉树，并写出它的中序遍历和后序遍历序列。参考答案：表达式二叉树如下图所示。中序遍历序列：ＤＢＦＥＣＧＡ后序遍历序列：ＤＦＧＣＥＢＡ分析：对上图所示二叉树的中序遍历和后序遍历过程如下图所示。　　　　　　　　　中序遍历　　　　　　　　　　　　　　　　后序遍历