資源簡(jiǎn)介

(共16張PPT)
利用二叉樹實(shí)現(xiàn)信息加密
項(xiàng)目挑戰(zhàn)
信息加密是保證信息安全的重要手段，加密的方法有很多，其中利用二叉樹的遍歷生成新的信息串序列，是典型的生成法加密，加密性能比較高。
項(xiàng)目背景
學(xué)校創(chuàng)新社團(tuán)將舉辦信息安全競(jìng)賽，你和同學(xué)決定參加“利用二叉樹實(shí)現(xiàn)信息加密”的競(jìng)賽項(xiàng)目。
你(甲方)以二叉樹作為載體按照指定的規(guī)則對(duì)一個(gè)二進(jìn)數(shù)序列進(jìn)行加密；之后將二叉樹的遍歷序列和密文發(fā)送給同學(xué)。
同學(xué)(乙方)綜合各種信息推導(dǎo)出該二叉樹的結(jié)構(gòu)，完成解密。
項(xiàng)目任務(wù)
項(xiàng)目分析
1.構(gòu)建合適的二叉樹，用數(shù)組表示，左孩子邊用“0”表示，右孩子邊用“1”表示。
2.甲方將向乙方發(fā)送二叉樹的前序和中序遍歷序列。
知識(shí)準(zhǔn)備
前序遍歷序列：ABDEGHCFIJ
中序遍歷序列：DBGEHACIJF
后序遍歷序列：DGHEBJIFCA
1.寫出如圖所示二叉樹的前序、中序和后序遍歷序列
知識(shí)準(zhǔn)備
2.前序遍歷: ABDGCEFH； 中序遍歷: DGBAECHF
A A
B B
D D
G G
C C
E E
F F
H H
D G B A E C H F
知識(shí)準(zhǔn)備
0
1 2
3 4 5 6
7 8 9 10 11 12 13
數(shù)組索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13
數(shù)組元素 A B C D 　 E F 　 G 　 　 　 　 H
1.若當(dāng)前節(jié)點(diǎn)的索引是index，則
左孩子節(jié)點(diǎn)的索引是
右孩子節(jié)點(diǎn)的索引是
2.若某節(jié)點(diǎn)索引indxe是奇數(shù)，
則說明其是
反之則是
其父節(jié)點(diǎn)的索引是
2*index+2
2*index+1
左孩子節(jié)點(diǎn)
右孩子節(jié)點(diǎn)
(index-1)//2
√
√
√
√
√
√
項(xiàng)目實(shí)施（甲）
1.構(gòu)建合適的二叉樹，并用數(shù)組表示
2.基于二叉樹，寫出前序和中序遍
歷序列，并發(fā)送給乙
3.基于二叉樹，對(duì)二進(jìn)制數(shù)序列進(jìn)行
加密，將加密后的密文發(fā)給乙方
項(xiàng)目實(shí)施（乙）
1.根據(jù)甲方發(fā)來的前序和中序遍
歷序列，推導(dǎo)出二叉樹的形態(tài)
2.依據(jù)加密規(guī)則，基于推導(dǎo)出的
二叉樹形態(tài)，對(duì)密文進(jìn)行解密
抽象與建模（甲）
從二叉樹的根節(jié)點(diǎn)開始，遍歷二進(jìn)制數(shù)序列，找準(zhǔn)對(duì)應(yīng)的左孩子或右孩子節(jié)點(diǎn)。
若孩子節(jié)點(diǎn)為空，則其父節(jié)點(diǎn)編號(hào)即為本輪的密文，同時(shí)回到根節(jié)點(diǎn)開始下一輪編碼。
若二進(jìn)制數(shù)序列遍歷結(jié)束，則當(dāng)前節(jié)點(diǎn)編號(hào)即為本輪的密文。
設(shè)計(jì)算法（甲）
根據(jù)抽象與建模，依據(jù)加密規(guī)則，設(shè)計(jì)如下算法：
1.從二叉樹的根節(jié)點(diǎn)開始，遍歷二進(jìn)制數(shù)序列，若為“0”則遍歷二叉樹的左孩子節(jié)點(diǎn)，若為“1”則遍歷右孩子節(jié)點(diǎn)。
2.若孩子節(jié)點(diǎn)非空，繼續(xù)遍歷二進(jìn)制數(shù)序列；若孩子節(jié)點(diǎn)為空，其父節(jié)點(diǎn)編號(hào)即為本輪的密文，結(jié)束本輪編碼，同時(shí)回到根節(jié)點(diǎn)，重新開始新一輪的遍歷。
3.若二進(jìn)制數(shù)序列遍歷結(jié)束，當(dāng)前節(jié)點(diǎn)編號(hào)即為本輪的密文，加密過程結(jié)束。
算法演示（甲）
01010
7
5
編寫程序（甲）
算法演示（乙）
75
10
010
編寫程序（乙）
項(xiàng)目總結(jié)
1 準(zhǔn)確描述二叉樹的各種遍歷序列
3 加密規(guī)則 ，能夠準(zhǔn)確生成密文
2 各種遍歷序列，推導(dǎo)出二叉樹的形態(tài)
4 加密規(guī)則，結(jié)合二叉樹的形態(tài)完成解密

展開更多......

收起↑