數據結構與虛擬儀器結合教學案例
——基于二叉樹的圖像加密

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

（1.安徽農業大學經濟技術學院，合肥 230011；2.安徽涉外經濟職業學院，合肥 230001）

1 引言

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

2 相關知識

樹型結構是用來表示一對多的重要模型，其中二叉樹是一種特殊的樹型結構，其特殊性在于：其一，二叉樹中的任意結點至多有2棵子樹。其二，二叉樹的子樹有左右之分。因此二叉樹通?？梢员硎境扇齻€相對獨立的部分，即根、左子樹、右子樹。其中，左子樹和右子樹也是符合本定義的二叉樹。顯然，二叉樹的定義是一個遞歸的定義[1]。對二叉樹的遍歷的討論，即如何確定一條搜索路徑，使得能夠對二叉樹中的每個結點進行一次訪問且只訪問一次。由于對二叉樹根結點訪問時機不同，通?？梢詫⒈闅v方法分為三種：先序遍歷、中序遍歷和后序遍歷。這三種遍歷方法也是遞歸進行的，可以證明，由二叉樹的中序和先序遍歷序列或者中序和后序遍歷序列可以唯一確定一棵二叉樹[2]。

3 圖像加密

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

3.1 圖像加密方法

將加密二叉樹的中序遍歷序列轉換成對應的二維矩陣，以該矩陣所形成的圖像即為加密圖像。

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

由該矩陣構成的圖像即為加密圖像。

本文采用虛擬儀器實驗平臺對本算法進行實現，通過虛擬實驗平臺向學生展示原始圖像和加密圖像的對比，如圖2所示：

圖2 原始圖對加密圖對比

3.2 圖像解密方法

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

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

4 實際應用

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

5 結束語

案例教學將理論與實際應用相結合，大大提高了學生的學習興趣，不僅有利于學生對課堂理論知識的掌握，也激發了學生對計算機技術的探索欲望。