数据结构与虚拟仪器结合教学案例——基于二叉树的图像加密

马竹娟，余新宏，吴德钊，杨 坤

（1.安徽农业大学经济技术学院，合肥 230011；2.安徽涉外经济职业学院，合肥 230001）

1 引言

数据结构在计算机科学中有着举足轻重的作用，不仅是计算机专业的核心课程，也是其他理工类专业如机械、电子等的选修课程。大多数学生在学习该课程时感到课程过于抽象，难以理解，甚至有学生错误的认为数据结构与计算机的应用关系不大。为了提高学生的学习兴趣，拓宽知识面，在教学中加深数据结构与应用的联系，本文结合虚拟仪器实验平台的优势，以二叉树在图像信息加密中的应用为例，形成课堂案例教学，将二叉树的性质、存储结构，以及遍历方法等应用到图像信息的加密中，既活跃课堂气氛，也极大的提高了学生的学习兴趣。

2 相关知识

树型结构是用来表示一对多的重要模型，其中二叉树是一种特殊的树型结构，其特殊性在于：其一，二叉树中的任意结点至多有2棵子树。其二，二叉树的子树有左右之分。因此二叉树通常可以表示成三个相对独立的部分，即根、左子树、右子树。其中，左子树和右子树也是符合本定义的二叉树。显然，二叉树的定义是一个递归的定义[1]。对二叉树的遍历的讨论，即如何确定一条搜索路径，使得能够对二叉树中的每个结点进行一次访问且只访问一次。由于对二叉树根结点访问时机不同，通常可以将遍历方法分为三种：先序遍历、中序遍历和后序遍历。这三种遍历方法也是递归进行的，可以证明，由二叉树的中序和先序遍历序列或者中序和后序遍历序列可以唯一确定一棵二叉树[2]。

3 图像加密

数字图像加密技术可以在信息传输领域起到隐藏信息的作用，从而提高安全性。一个图像可以看成是一个M×N个像素组成的矩阵，以3×3的矩阵为例，如下所示：

3.1 图像加密方法

将加密二叉树的中序遍历序列转换成对应的二维矩阵，以该矩阵所形成的图像即为加密图像。

例如，加密二叉树的中序遍历序列为：bhdeiafcg

由该矩阵构成的图像即为加密图像。

本文采用虚拟仪器实验平台对本算法进行实现，通过虚拟实验平台向学生展示原始图像和加密图像的对比，如图2所示：

图2 原始图对加密图对比

3.2 图像解密方法

解密的过程是加密的逆操作。具体步骤如下：

（1）接收方需获得加密图和加密二叉树的后序遍历序列。（2）接收方从秘密通道获得密钥，即由原始图像的二维矩阵所构成的原二叉树的中序遍历序列。（3）接收方将加密图转换成二维矩阵，以行序为主的顺序读取矩阵中的数据，所获得的序列即为加密二叉树的中序遍历序列。（4）根据加密二叉树的中序、后序遍历序列，确定加密二叉树树形，从而获得加密二叉树的先序遍历序列。（5）由于加密二叉树的先序遍历序列与原图像所构成的完全二叉树相同，结合密钥，唯一确定与原始图像相对应的完全二叉树。（6）将用于存储完全二叉树的一维数组转换成二维矩阵，最终恢复原图。

4 实际应用

在实际通信中，甲方将加密图发给乙方，并公开一个后序遍历序列，乙接收后向甲方确认回复，男方再通过秘密渠道向乙方发送密钥，即原二叉树的中序遍历序列。甲方获得三方信息，可根据上述解密过程可以恢复原图。该方法也可以用于文字信息加密，我方密钥管理，数字认证等，可应用于商业、军事等多个领域。

5 结束语

案例教学将理论与实际应用相结合，大大提高了学生的学习兴趣，不仅有利于学生对课堂理论知识的掌握，也激发了学生对计算机技术的探索欲望。