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

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

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

1 引言

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

2 相關(guān)知識

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

3 圖像加密

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

3.1 圖像加密方法

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

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

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

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

圖2 原始圖對加密圖對比

3.2 圖像解密方法

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

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

4 實際應(yīng)用

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

5 結(jié)束語

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