浙教版（2019）高中信息技术 选修1 项目挑战：利用二叉树实现信息加密 课件

这是一份浙教版（2019）高中信息技术 选修1 项目挑战：利用二叉树实现信息加密 课件，共16页。

利用二叉树实现信息加密项目挑战 信息加密是保证信息安全的重要手段，加密的方法有很多，其中利用二叉树的遍历生成新的信息串序列，是典型的生成法加密，加密性能比较高。项目背景学校创新社团将举办信息安全竞赛，你和同学决定参加“利用二叉树实现信息加密”的竞赛项目。你(甲方)以二叉树作为载体按照指定的规则对一个二进数序列进行加密；之后将二叉树的遍历序列和密文发送给同学。同学(乙方)综合各种信息推导出该二叉树的结构，完成解密。项目任务项目分析1.构建合适的二叉树，用数组表示，左孩子边用“0”表示，右孩子边用“1”表示。2.甲方将向乙方发送二叉树的前序和中序遍历序列。知识准备前序遍历序列：ABDEGHCFIJ中序遍历序列：DBGEHACIJF后序遍历序列：DGHEBJIFCA1.写出如图所示二叉树的前序、中序和后序遍历序列知识准备2.前序遍历: ABDGCEFH； 中序遍历: DGBAECHF 知识准备0 1 2 3 4 5 6 7 8 9 10 11 12 13 1.若当前节点的索引是index，则左孩子节点的索引是右孩子节点的索引是2.若某节点索引indxe是奇数，则说明其是 反之则是 其父节点的索引是2*index+22*index+1左孩子节点右孩子节点(index-1)//2√√√√√√项目实施（甲）1.构建合适的二叉树，并用数组表示2.基于二叉树，写出前序和中序遍 历序列，并发送给乙3.基于二叉树，对二进制数序列进行 加密，将加密后的密文发给乙方项目实施（乙）1.根据甲方发来的前序和中序遍 历序列，推导出二叉树的形态2.依据加密规则，基于推导出的 二叉树形态，对密文进行解密抽象与建模（甲）从二叉树的根节点开始，遍历二进制数序列，找准对应的左孩子或右孩子节点。若孩子节点为空，则其父节点编号即为本轮的密文，同时回到根节点开始下一轮编码。若二进制数序列遍历结束，则当前节点编号即为本轮的密文。设计算法（甲）根据抽象与建模，依据加密规则，设计如下算法：1.从二叉树的根节点开始，遍历二进制数序列，若为“0”则遍历二叉树的左孩子节点，若为“1”则遍历右孩子节点。2.若孩子节点非空，继续遍历二进制数序列；若孩子节点为空，其父节点编号即为本轮的密文，结束本轮编码，同时回到根节点，重新开始新一轮的遍历。3.若二进制数序列遍历结束，当前节点编号即为本轮的密文，加密过程结束。算法演示（甲）0101075编写程序（甲）算法演示（乙）7510010编写程序（乙）项目总结1 准确描述二叉树的各种遍历序列3 加密规则 ，能够准确生成密文2 各种遍历序列，推导出二叉树的形态4 加密规则，结合二叉树的形态完成解密