[計算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)06gj(參考版)
2024-10-22 04:11本頁面
【正文】 要求有編碼過程和解碼過程。 本章作業(yè) Huffman 編碼的譯碼過程。 赫夫曼編碼和譯碼 樹的計數(shù) 已知二叉樹的遍歷序列： 前序序列為 ABECDFGHIJ， 中序序列為 EBCDAFHIGJ， 求其樹的構(gòu)成以及后序遍歷序列 E B F C G H A D I J E B F C G HI A D J E B F CD HIGJ A EBCD FHIGJ A 前序序列為 ABECDFGHIJ， 中序序列為 EBCDAFHIGJ 二叉樹構(gòu)造 本章小結(jié) 遍歷二叉樹的 算法與實(shí)現(xiàn)。 哈夫曼編碼 電文 ABACCDA 01001101101110 14位 A B C D 0 10 110 111 B C D A 0 1 0 1 0 1 用二叉樹設(shè)計前綴碼 ? 電文 ABACCDA 字符出現(xiàn)的頻度 A 3次 B 1次 C 2次 D 1次 構(gòu)造一棵權(quán)為 {3， 1， 2， 1} 的赫夫曼樹 A B C D 0 110 10 111 電文 0110010101110 13位 C B D A 0 1 0 1 0 1 赫夫曼編碼設(shè)計示例 由于赫夫曼樹中沒有度為 1的結(jié)點(diǎn) (這類樹又稱嚴(yán)格的 (strict)(或正則的 )二叉樹 )；則一棵有 n個葉子結(jié)點(diǎn)的赫夫曼樹共有 2n1個結(jié)點(diǎn) (因 n2=n01)，可以存儲在一個大小為 2n1的一維數(shù)組中。 哈夫曼編碼是一種不等長的二進(jìn)制編碼。約定左分支表示字符‘ 0’，右分支便是字符‘ 1’，以分支字符串作為該葉子結(jié)點(diǎn)字符的編碼。 在一個字符集中，任何一個字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為 前綴編碼 。該樹即為赫夫曼樹。 (3)在 F中刪除這兩棵樹，同時將新得到的二叉樹加入 F中。 a60 b=‘E’ a70 b=‘D’ a80 b=‘C’ a90 b=‘B’ b=‘A’ 100個學(xué)生中 5個不及格 15個 60幾分 40個 70幾分 30個 80幾分 10個 90幾分 5 15 40 30 10 需比較5+2*15+3*40+4*30+4*10 =315次 帶權(quán)路徑長度的例子 (1)根據(jù)給定的 n個權(quán)值 {w1,w2,…,w n}，構(gòu)成 n棵二叉樹的集合 F={T1,T2,…,T n}， Ti 為只有一個結(jié)點(diǎn)的樹，其權(quán)為 wi。 else if(a90) b=‘B’。 else if(a70) b=‘D’。,wn的二叉樹中，帶權(quán)路徑長度 WPL最小的二叉樹。 樹的帶權(quán)路徑長度 所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為 WPL= 。 給結(jié)點(diǎn)賦予的特定數(shù)值，稱為該 結(jié)點(diǎn)的權(quán) 。 樹的路徑長度 樹根到各結(jié)點(diǎn)路徑長度之和。 路徑長度 路徑上的分支數(shù)目。 森林轉(zhuǎn)換成二叉樹 A B C D E F G H I A B C D E F G H I A B C D E F G H I 森林所對應(yīng)的二叉樹 哈夫曼樹，以稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。 (3)旋轉(zhuǎn)：將樹作適當(dāng)?shù)男D(zhuǎn)。 存儲表示 可以分為三步： (1)連線：相鄰兄弟間連線。 struct CSNode *firstchild,*nextsibling。 //根的位置和結(jié)點(diǎn)數(shù) }CTree, *PCTree。 typedef struct{ //樹結(jié)構(gòu) CTNode nodes[MAX_TREE_SIZE]。 struct EdgeNode *firstchild。 }EdgeNode。 childk A 3 B 2 C 0 D 1 E 0 F 0 G 2 H 0 I 0 A B C D E F H I G 0 1 2 3 4 5 6 7 8 A B C ^ D E ^ F ^ G H ^ I ^ 1 2 3 ^ 7 8 ^ 4 5 ^ 6 ^ A B C D E F H I G //樹的孩子鏈表存儲表示 typedef struct EdgeNode{//孩子鏈表中結(jié)點(diǎn)的結(jié)構(gòu) int child。 存儲結(jié)構(gòu) data degree child1 child2 int r,n。 //結(jié)點(diǎn)的雙親位置域 }PTNode。 0 1 2 3 4 5 6 7 8 A 1 B 0 C 0 D 0 E 1 F 1 G 3 H 6 I 6 A B C D E F H I G 雙親表示法 //樹的雙親表存儲表示 define MAX_TREE_SIZE 100 typedef struct PTNode {//樹中結(jié)點(diǎn)的結(jié)構(gòu) TElemType data。 }BiTreeNode,*BiThrTree。 struct BiTreeNode *lchild,*rchild。 0 lchild 域指示結(jié)點(diǎn)的左孩子 ltag={ 1 lchild 域指示結(jié)點(diǎn)的前驅(qū) 0 rchild 域指示結(jié)點(diǎn)的右孩子 rtag={ 1 rchild 域指示結(jié)點(diǎn)的后繼 這種結(jié)構(gòu)叫做 線索鏈表 ,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索 .加上線索的二叉樹稱之為 線索二叉樹 . rchild rtag data ltag lchild 線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu) （ 了解 ） //二叉樹的二叉線索存儲表示 typedef enum{Link,Thread}PointerTag。 ?規(guī)定：若結(jié)點(diǎn)有左子樹，則其 lchild域指示其左孩子，否則令 lchild指示其前驅(qū)； 若結(jié)點(diǎn)有右子樹，則其 rchild域指示其右孩子，否則令
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1