[計(jì)算機(jī)軟件及應(yīng)用]ch-資料下載頁
2025-10-07 23:09本頁面
【正文】 ， 10，11，則上述電文的譯文為“ 0001000010100100111000”，總長為 22個(gè) bit。對(duì)方接收時(shí)，按二位一組進(jìn)行譯碼即可。 樹的應(yīng)用 ? 線索二叉樹 ? 1. 線索二叉樹的定義及結(jié)構(gòu) ? （ 1）線索二叉樹的定義 ? 可以把二叉樹中除第一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)；除最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接后繼結(jié)點(diǎn)。為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，可以利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的那些空指針域來指示。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索（ thread），加了線索的二叉樹稱為線索二叉樹。 樹的應(yīng)用 ? （ 2）線索二叉樹的結(jié)構(gòu) ? 一個(gè)具有 n個(gè)結(jié)點(diǎn)的二叉樹若采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，在 2n個(gè)指針域中只有 n1個(gè)指針域是用來存儲(chǔ)結(jié)點(diǎn)孩子的地址，而另外 n+1個(gè)指針域存放的都是 NULL。因此，可以利用某結(jié)點(diǎn)空的左指針域（ lchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)結(jié)點(diǎn)的存儲(chǔ)地址，利用結(jié)點(diǎn)空的右指針域（ rchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接后繼結(jié)點(diǎn)的存儲(chǔ)地址；對(duì)于那些非空的指針域，則仍然存放指向該結(jié)點(diǎn)左、右孩子的指針。這樣，就得到了一棵線索二叉樹。 樹的應(yīng)用 ? 2. 線索二叉樹的基本操作 ? （ 1）建立一棵中序線索二叉樹 ? （ 2）在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn) ? （ 3）在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn) ? （ 4）在中序線索二叉樹上查找任意結(jié)點(diǎn)在先序下的后繼 ? （ 5）在中序線索二叉樹上查找任意結(jié)點(diǎn)在后序下的前驅(qū) ? （ 6）在中序線索二叉樹上查找值為 x的結(jié)點(diǎn) 本章小結(jié) ? 樹是數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)章節(jié)，而其中的二叉樹又是本章的重點(diǎn)內(nèi)容。在這一章里要了解樹的定義熟悉二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)、遍歷、線索化和樹的存儲(chǔ)結(jié)構(gòu)、遍歷以及樹、森林與二叉樹的轉(zhuǎn)換，哈夫曼樹及哈夫曼編碼等內(nèi)容。算法的重點(diǎn)是二叉樹的遍歷及其有關(guān)應(yīng)用。這也是本章的難點(diǎn)。 ? 1. 樹的各種術(shù)語：如結(jié)點(diǎn)的度和樹的度，分支節(jié)點(diǎn)和葉子節(jié)點(diǎn)，孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)，結(jié)點(diǎn)的層數(shù)和樹的深度，有序樹和無序樹，森林等。 本章小結(jié) ? 2. 二叉樹的性質(zhì)、存儲(chǔ)方式、遍歷：要求熟練掌握二叉樹的性質(zhì)，二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照一定次序（從根結(jié)點(diǎn)起，從上層到下層，從左往右編號(hào)就得到了存放的次序）存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中 。用順序存儲(chǔ)方式對(duì)于完全二叉樹而言其結(jié)構(gòu)簡單又節(jié)省空間，但是對(duì)于一般二叉樹并不合適。因此樹的存儲(chǔ)結(jié)構(gòu)更多的是用鏈?zhǔn)酱鎯?chǔ)。結(jié)點(diǎn)的結(jié)構(gòu)為兩個(gè)指針域 lchild和rchild分別指向該結(jié)點(diǎn)的左孩子和右孩子，另有一個(gè)數(shù)據(jù)域 data存放結(jié)點(diǎn)數(shù)據(jù)。根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷 )，中序遍歷（或中根遍歷 )、后序遍歷（或后根遍歷）。 本章小結(jié) ? 3. 樹的存儲(chǔ)、樹和森林的轉(zhuǎn)換、遍歷：樹的存儲(chǔ)結(jié)構(gòu)：有雙親鏈表表示法，孩子鏈表表示法和孩子兄弟鏈表表示法。樹和森林及二叉樹的轉(zhuǎn)換：三者是惟一對(duì)應(yīng)的，它們之間的轉(zhuǎn)換辦法應(yīng)掌握。樹和森林因?yàn)槊總€(gè)結(jié)點(diǎn)有兩棵以上的子樹，因此不便于討論中根次序遍歷，但是其前序遍歷和后序遍歷還是應(yīng)該了解的。 本章小結(jié) ? 4. 哈夫曼樹和哈夫曼編碼：哈夫曼樹 (Huffman)，又稱最優(yōu)二叉樹。哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。（最優(yōu)前綴碼就是平均碼長最小的前綴碼）。哈夫曼編碼的構(gòu)造很容易，只要構(gòu)造好了哈夫曼樹，按分支情況在左路徑上寫代碼 0，右路徑上寫代碼 1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。 ? 5. 線索二叉樹的基本概念：為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，可以利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的那些空指針域來指示。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索 (thread)，加了線索的二叉樹稱為線索二叉樹。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1