资源简介

(共16张PPT)
利用二叉树实现信息加密
项目挑战
信息加密是保证信息安全的重要手段，加密的方法有很多，其中利用二叉树的遍历生成新的信息串序列，是典型的生成法加密，加密性能比较高。
项目背景
学校创新社团将举办信息安全竞赛，你和同学决定参加“利用二叉树实现信息加密”的竞赛项目。
你(甲方)以二叉树作为载体按照指定的规则对一个二进数序列进行加密；之后将二叉树的遍历序列和密文发送给同学。
同学(乙方)综合各种信息推导出该二叉树的结构，完成解密。
项目任务
项目分析
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 加密规则，结合二叉树的形态完成解密

展开更多......

收起↑