中小学教育资源及组卷应用平台 第四单元练习题及参考答案 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)
~~ 您好，已阅读到文档的结尾了 ~~
