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