樹和二叉樹ppt課件(2)-在線瀏覽
2025-06-16 02:58本頁面
【正文】 較高 ,對A,B,C,D的編碼分別為 :0,00,1,01,則電文總長 :14位的二進制串 :“ 00000110000110” ,長度縮短了但譯碼出現的困難 . 前綴編碼 :是指任何一個字符的編碼都不是另一個字符編碼的前綴 . 以每種字符在電文中出現的次數為 Wi,其編碼長度為 li,電文中可能出現的字符有 n種 ,則電文總長為 : n WPL =∑ wili i=1 正好是對應的哈夫曼樹的 以哈夫曼樹來設計的二進制前綴編碼使得電文總長最短 . 具體設計如下 : 將可能出現的字符作為葉子結點 ,電文中字符出現的頻率為各個葉子結點的權值 ,設計一棵哈夫曼樹 ,樹的 左分支 表示二進制數 0， 右分支 表示二進制數 1,則從根結點到每一個葉子結點（字符）的路經上分支字符組成的字符串，即為該字符的二進制前綴編碼 ,又稱為 哈夫曼編碼 . 例如 : 字符 A,B,C,D出現的頻率為, 夫曼 樹及哈 夫曼編碼。 5. 如下圖所示 ,以數據集 {4， 5， 6， 7， 10， 12，18}為結點權值所構成的哈夫曼樹為 ____，其帶權路徑長度為 ____。 2). 否則在左子樹中進行查找 ,若找到 ,則返回該結點 。 查詢二叉樹中某個結點 分三步進行 : BiTree search (BiTree *bt, elemtype x) { // 在 bt為根結點的二叉樹中查找元素 x BiTree p。 if (pdata==x) return bt。 if (btrchild!=NULL) return (search(prchild,x))。 //查找失敗 } 統計二叉樹中葉子結點的個數 算法基本思想 : 中序遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。分三種情況 : 1)二叉樹為空 ,則葉子結點數為 0. 2)若只一個根結點 ,則葉子結點數為 1. 3)若二叉樹非空 ,分別統計左 ,右子樹中葉子結點數 . void CountLeaf (BiTree *bt, int count ) { if (bt!=NULL ) { if ((!btlchild)amp。 (!btrchild)) count++。 CountLeaf( btrchild, count)。 //二叉樹為空 if (!Tlchild amp。 !Trchild) return 1。 n = CountLeaf( Trchild)。 } //else } // CountLe
教學課件相關推薦
鄂ICP備17016276號-1