數(shù)據(jù)結(jié)構(gòu)與虛擬儀器結(jié)合教學(xué)案例
——基于二叉樹的圖像加密

馬竹娟，余新宏，吳德釗，楊 坤

（1.安徽農(nóng)業(yè)大學(xué)經(jīng)濟(jì)技術(shù)學(xué)院，合肥 230011；2.安徽涉外經(jīng)濟(jì)職業(yè)學(xué)院，合肥 230001）

1 引言

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中有著舉足輕重的作用，不僅是計(jì)算機(jī)專業(yè)的核心課程，也是其他理工類專業(yè)如機(jī)械、電子等的選修課程。大多數(shù)學(xué)生在學(xué)習(xí)該課程時(shí)感到課程過于抽象，難以理解，甚至有學(xué)生錯(cuò)誤的認(rèn)為數(shù)據(jù)結(jié)構(gòu)與計(jì)算機(jī)的應(yīng)用關(guān)系不大。為了提高學(xué)生的學(xué)習(xí)興趣，拓寬知識(shí)面，在教學(xué)中加深數(shù)據(jù)結(jié)構(gòu)與應(yīng)用的聯(lián)系，本文結(jié)合虛擬儀器實(shí)驗(yàn)平臺(tái)的優(yōu)勢(shì)，以二叉樹在圖像信息加密中的應(yīng)用為例，形成課堂案例教學(xué)，將二叉樹的性質(zhì)、存儲(chǔ)結(jié)構(gòu)，以及遍歷方法等應(yīng)用到圖像信息的加密中，既活躍課堂氣氛，也極大的提高了學(xué)生的學(xué)習(xí)興趣。

2 相關(guān)知識(shí)

樹型結(jié)構(gòu)是用來表示一對(duì)多的重要模型，其中二叉樹是一種特殊的樹型結(jié)構(gòu)，其特殊性在于：其一，二叉樹中的任意結(jié)點(diǎn)至多有2棵子樹。其二，二叉樹的子樹有左右之分。因此二叉樹通常可以表示成三個(gè)相對(duì)獨(dú)立的部分，即根、左子樹、右子樹。其中，左子樹和右子樹也是符合本定義的二叉樹。顯然，二叉樹的定義是一個(gè)遞歸的定義[1]。對(duì)二叉樹的遍歷的討論，即如何確定一條搜索路徑，使得能夠?qū)Χ鏄渲械拿總€(gè)結(jié)點(diǎn)進(jìn)行一次訪問且只訪問一次。由于對(duì)二叉樹根結(jié)點(diǎn)訪問時(shí)機(jī)不同，通常可以將遍歷方法分為三種：先序遍歷、中序遍歷和后序遍歷。這三種遍歷方法也是遞歸進(jìn)行的，可以證明，由二叉樹的中序和先序遍歷序列或者中序和后序遍歷序列可以唯一確定一棵二叉樹[2]。

3 圖像加密

數(shù)字圖像加密技術(shù)可以在信息傳輸領(lǐng)域起到隱藏信息的作用，從而提高安全性。一個(gè)圖像可以看成是一個(gè)M×N個(gè)像素組成的矩陣，以3×3的矩陣為例，如下所示：

3.1 圖像加密方法

將加密二叉樹的中序遍歷序列轉(zhuǎn)換成對(duì)應(yīng)的二維矩陣，以該矩陣所形成的圖像即為加密圖像。

例如，加密二叉樹的中序遍歷序列為：bhdeiafcg

由該矩陣構(gòu)成的圖像即為加密圖像。

本文采用虛擬儀器實(shí)驗(yàn)平臺(tái)對(duì)本算法進(jìn)行實(shí)現(xiàn)，通過虛擬實(shí)驗(yàn)平臺(tái)向?qū)W生展示原始圖像和加密圖像的對(duì)比，如圖2所示：

圖2 原始圖對(duì)加密圖對(duì)比

3.2 圖像解密方法

解密的過程是加密的逆操作。具體步驟如下：

（1）接收方需獲得加密圖和加密二叉樹的后序遍歷序列。（2）接收方從秘密通道獲得密鑰，即由原始圖像的二維矩陣所構(gòu)成的原二叉樹的中序遍歷序列。（3）接收方將加密圖轉(zhuǎn)換成二維矩陣，以行序?yàn)橹鞯捻樞蜃x取矩陣中的數(shù)據(jù)，所獲得的序列即為加密二叉樹的中序遍歷序列。（4）根據(jù)加密二叉樹的中序、后序遍歷序列，確定加密二叉樹樹形，從而獲得加密二叉樹的先序遍歷序列。（5）由于加密二叉樹的先序遍歷序列與原圖像所構(gòu)成的完全二叉樹相同，結(jié)合密鑰，唯一確定與原始圖像相對(duì)應(yīng)的完全二叉樹。（6）將用于存儲(chǔ)完全二叉樹的一維數(shù)組轉(zhuǎn)換成二維矩陣，最終恢復(fù)原圖。

4 實(shí)際應(yīng)用

在實(shí)際通信中，甲方將加密圖發(fā)給乙方，并公開一個(gè)后序遍歷序列，乙接收后向甲方確認(rèn)回復(fù)，男方再通過秘密渠道向乙方發(fā)送密鑰，即原二叉樹的中序遍歷序列。甲方獲得三方信息，可根據(jù)上述解密過程可以恢復(fù)原圖。該方法也可以用于文字信息加密，我方密鑰管理，數(shù)字認(rèn)證等，可應(yīng)用于商業(yè)、軍事等多個(gè)領(lǐng)域。

5 結(jié)束語

案例教學(xué)將理論與實(shí)際應(yīng)用相結(jié)合，大大提高了學(xué)生的學(xué)習(xí)興趣，不僅有利于學(xué)生對(duì)課堂理論知識(shí)的掌握，也激發(fā)了學(xué)生對(duì)計(jì)算機(jī)技術(shù)的探索欲望。