關于二叉樹的加密算法

摘 要：本文主要研究了關于二叉樹的加密算法，利用二叉樹的中序遍歷和先序遍歷（或后序遍歷）可以唯一確定一棵二叉樹來進行加密解密，并給出了基本算法，最后對算法的時間空間復雜度進行了一個簡單的說明，并說明了其在實際生活中的應用。

關鍵詞：二叉樹；加密；解密；先序遍歷；中序遍歷；后序遍歷

中圖分類號：TP309.7 文獻標識碼：A 文章編號：2096-4706（2018）10-0158-03

Abstract：This paper mainly studies the encryption algorithm of binary tree，which can uniquely determine a binary tree for encryption and decryption by using the middle-order traversal and the first-order traversal （ or the second-order traversal ） of the binary tree，and gives the basic algorithm. finally，it gives a simple explanation of the time-space complexity of the algorithm，and illustrates its application in real life.

Keywords：binary tree；encryption；decryption；first-order traversal；middle-order traversal；later-order traversal

0 引 言

在數據結構中，樹是一類非常重要的數據結構類型，其在生活中和理論中都有非常重要的應用。其中二叉樹是樹的一種特殊的結構，當然也是比較基礎又比較重要的數據結構。二叉樹有許多的性質，可以設計二進制數的前綴編碼，哈夫曼樹就是一個很典型的例子。關于二叉樹的三種遍歷：先序遍歷，中序遍歷，后序遍歷；這其中只需已知中序遍歷和另外任意一種遍歷就可以唯一確定一棵二叉樹，而根據先序遍歷和后序遍歷是無法確定一棵二叉樹的。因此，可以利用二叉樹的這些性質，實現對信息的加密和解密。因此本文介紹了利用二叉樹進行加密與解密的方法，并說明了利用多種遍歷實現密鑰的多方面保存。

1 樹與二叉樹

1.1 樹的定義

樹是N（N≥0）個結點的有限集合，N=0時，稱為空樹，這是一種特殊情況。在任意一顆非空樹中滿足：

（1）有且僅有一個特定的成為根的結點。

（2）當N>1時，其余結點可分為m（m>0）個互不相交的有限集合T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根節點的子樹。

1.2 二叉樹的定義

二叉樹是另一種樹形結構，其特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。……