信息技术选修1 数据与数据结构4.1 树与二叉树教案设计

这是一份信息技术选修1 数据与数据结构4.1 树与二叉树教案设计，共2页。教案主要包含了竞赛前准备，竞赛实施阶段，结论与建议等内容，欢迎下载使用。

一、竞赛前准备
为了便于进行加密解密竞赛任务，甲乙双方共同熟悉加密规则。
1．加密规则
构建二叉树，按照左孩子边用“0”、右孩子边用“1”表示，将一个二进制序列加密成明文。以教材中下图为例：
如果明文为：1001101010110时，加密后的密文为：54879。具体加密的方法可以参照教材P110。
2．熟悉二叉树的三种遍历
二叉树有前序遍历、中序遍历和后序遍历，对于上图，它的三种遍历为：
前序遍历：124735869
中序遍历：274158396
后序遍历：742859631
3．熟悉由二种遍历确定一棵树
由二叉树的遍历规则知，当知道这棵树的前序遍历和中序遍历，或者后序遍历和中序遍历，就可以确定唯一的树。比如：
前序：13254
中序：23145
则这棵树为：
4．解密
在构建好的树上，按照“0”为左，“1”为右的方式，由密文逐步推出二进制序列的明文。
二、竞赛实施阶段
1．甲方
= 1 \* GB3 ①构建二叉树
根据竞赛需要，设想一棵二叉树，可以在纸上（或电脑上）准备好。
= 2 \* GB3 ②构建明文和密文
在上述的二叉树的基础上，按照“0”为左，“1”为右的方式，设想一个明文，并根据加密规则，得到密文串。
= 3 \* GB3 ③遍历
对上述二叉树进行前序遍历和中序遍历，得到两个遍历序列。
将密文和两个遍历序列发给乙方。
2．乙方
= 1 \* GB3 ①确定二叉树
依据甲方发过来的二个遍历序列，描绘出该二叉树。
= 2 \* GB3 ②解密
根据加密规则，对密文解密，得到明文。
三、结论与建议
本项目利用二叉树的三种遍历，结合左“0”右“1”的规则，得到一种加密方法。项目的实施过程中，要求学生掌握三种遍历，并能通过二种遍历确定唯一的一棵树。项目中，规则的熟悉尤其重要，建议让学生多熟悉竞赛规则，以此掌握三种遍历。