樹(shù)和二叉樹(shù)ppt課件(2)(編輯修改稿)
2025-05-26 02:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 權(quán)值 W={ 5, 6, 2, 9,7 } 構(gòu)造哈夫曼樹(shù)并設(shè)計(jì)哈夫曼編碼 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 11 100 101 第四步 : 圖 525 構(gòu)造 哈夫曼樹(shù)并設(shè)計(jì) 編碼 補(bǔ)充習(xí)題 1. 一棵哈夫曼樹(shù)有個(gè) m葉子結(jié)點(diǎn) ,則其結(jié)點(diǎn)總數(shù)為_(kāi)_______. 2. 設(shè)電文中出現(xiàn)的字母為 A， B， C， D和 E，每個(gè)字母在電文中出現(xiàn)的次數(shù)分別是 6， 23， 3， 5，和 12，按哈夫曼編碼，則字母 C的編碼應(yīng)是（） A． 10 B. 110 3. 設(shè)給定權(quán)集 W={2， 3， 4， 7， 8， 9}，試構(gòu)造關(guān)于 w的一棵哈夫曼樹(shù)，并求其加權(quán)路徑長(zhǎng)度 WPL. 4. 有一份電文中共使用 5個(gè)字符： a,b,c,d,e,他們的出現(xiàn)頻率依次為 4， 7， 5， 2， 9，試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)（請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的哈夫曼編碼。 5. 如下圖所示 ,以數(shù)據(jù)集 {4， 5， 6， 7， 10， 12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)成的哈夫曼樹(shù)為 ____，其帶權(quán)路徑長(zhǎng)度為 ____。 應(yīng)用舉例 查詢(xún)二叉樹(shù)中某個(gè)結(jié)點(diǎn) 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 求二叉樹(shù)的深度 (后序遍歷 ) 由前序 +中序序列構(gòu)造二叉樹(shù) 創(chuàng)建二叉樹(shù)的二叉鏈表存儲(chǔ) 1). 在二叉樹(shù)不空的前提下 ,和根結(jié)點(diǎn)的元素進(jìn)行比較 ,若相等 ,則找到返回 該結(jié)點(diǎn) 。 2). 否則在左子樹(shù)中進(jìn)行查找 ,若找到 ,則返回該結(jié)點(diǎn) 。 3). 否則繼續(xù)在右子樹(shù)中進(jìn)行查找 ,若找到 ,則返回該結(jié)點(diǎn) ,否則返回空。 查詢(xún)二叉樹(shù)中某個(gè)結(jié)點(diǎn) 分三步進(jìn)行 : BiTree search (BiTree *bt, elemtype x) { // 在 bt為根結(jié)點(diǎn)的二叉樹(shù)中查找元素 x BiTree p。p=bt。 if (pdata==x) return bt。 //查找成功返回 if (btlchild!=NULL) return (search(plchild,x))。 if (btrchild!=NULL) return (search(prchild,x))。 return NULL。 //查找失敗 } 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 中序遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 因此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為 :若是葉子結(jié)點(diǎn)，則計(jì)數(shù)器增 1。分三種情況 : 1)二叉樹(shù)為空 ,則葉子結(jié)點(diǎn)數(shù)為 0. 2)若只一個(gè)根結(jié)點(diǎn) ,則葉子結(jié)點(diǎn)數(shù)為 1. 3)若二叉樹(shù)非空 ,分別統(tǒng)計(jì)左 ,右子樹(shù)中葉子結(jié)點(diǎn)數(shù) . void CountLeaf (BiTree *bt, int count ) { if (bt!=NULL ) { if ((!bt
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1