资源简介

教学设计
课程基本信息
课题 4 项目挑战 利用二叉树实现信息加密
教学目标
1.对于给定的问题，能自觉、主动地寻求恰当的方式来获取与处理信息。 2.根据实际任务的需要，恰当地选择数据结构，存储问题解决中的各种数据。 3.在解决问题的过程中，界定问题、抽象特征、建立模型，运用合理的方法形成解决问题的方案。
教学内容
教学重点： 1. 二叉树遍历的相关技能。 2. 加密与解密过程的实现。 教学难点： 1. 从问题中抽象出恰当的数据结构。 2. 设计程序实现信息加密和解密功能。
教学过程
1.情景导入： 学校创新社团将举办信息安全竞赛，你和同学决定参加“利用二叉树实现信息加密”的竞赛项目。你(甲方，也就是加密方)需以二叉树作为载体按照指定的规则对一个二进数序列进行加密；之后将二叉树的遍历序列和密文发送给同学。同学(乙方，也就是解密方)综合各种信息推导出该二叉树的结构，完成解密。 2.熟悉加密规则： 甲乙双方共同熟悉加密规则，同时做以下约定： (1)用数组表示二叉树，二叉树的左孩子边用“0”表示，右孩子边用“1”表示 (2)甲方将向乙方发送二叉树的前序和中序遍历序列 设计意图：熟悉加密规则，确定推导二叉树的依据。 3.知识储备： (1)正确书写二叉树的前序、中序和后序遍历序列。 (2)依据二叉树的前序和中序遍历序列，准确推导出二叉树的形态，并可以用数组表示。 通过观察分析各节点之间的索引关系，归纳总结如下结论： 若当前节点的索引是index，则其左孩子节点索引是2*index+1，右孩子节点索引是2*index+2 若某节点索引是奇数，则说明其是左孩子节点，反之则是右孩子节点。 若当前节点的索引是index，则其父节点索引是（index-1）//2 设计意图：掌握二叉树的前序遍历、中序遍历和后序遍历。角色互换，各个角色的技能提前掌握。 4.项目实施之前，甲乙双方需明确各自分工。 甲方需要完成以下内容： (1)构造合适的二叉树，并能用数组表示。 (2)模拟出该二叉树的三种遍历序列，并将前序和中序遍历序列发给乙方。 (3)基于该二叉树，对二进制数序列（明文）进行加密，并将加密后的密文发给乙方。 乙方需要完成以下内容： (1)根据甲方发来的二叉树的前序和中序遍历序列，推导出二叉树的形态。 (2)依据加密规则，基于推导出的二叉树形态，对密文进行解密。 设计意图：明确项目任务，逐步实施。 5.项目实施 (1)抽象与建模（甲方） 从二叉树的根节点开始，遍历二进制数序列，找准对应的左孩子或右孩子节点。 若孩子节点为空，则其父节点编号即为本轮的密文，同时回到根节点开始下一轮编码。 若二进制数序列遍历结束，则当前节点编号即为本轮的密文。 (2)设计算法（甲方） ①从二叉树的根节点开始，遍历二进制数序列，若为“0”则遍历二叉树的左孩子节点，若为“1”则遍历右孩子节点。 ②若节点非空，继续遍历二进制数序列；若节点为空，其父节点编号即为本轮的密文，结束本轮编码，同时回到根节点，重新开始新一轮的遍历。 ③若二进制数序列遍历结束，当前节点编号即为本轮的密文。加密过程结束。 (3)编写程序并测试（甲方） (4)设计算法（乙方） ①遍历密文，若该编码节点为左孩子节点则用字符“0”记录路径，若为右孩子节点则用字符“1”记录路径，自下至上直至找到根节点为止，逆序记录路径串，路径串即为该编码解密出的二进制数序列（明文）。 ②继续遍历密文，将各轮解密出的二进制数序列（明文）进行迭代，直至密文遍历结束，最后输出解密出的二进制数序列（明文）。解密过程结束。 (5)编写程序并测试（乙方） 设计意图：甲方与乙方合作实现加密和解密过程，验证结果的正确性，若有误，需反演并找出错误原因，弥补知识漏洞。 6.项目总结 最后从熟悉加密规则、构建二叉树、如何生成明文、如何解密等方面进行总结回顾，编写成果报告。

展开更多......

收起↑