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