哈夫曼樹與樹的應(yīng)用-資料下載頁
2025-10-02 20:36本頁面
【導(dǎo)讀】把原二叉樹的結(jié)點都變?yōu)?。–度數(shù)為1，則增加一個分支，空二叉樹的擴充二叉樹規(guī)。二叉樹的帶權(quán)的外部路徑長度。對于一組非負(fù)實數(shù)｛w1,w2,w3,…這棵二叉樹就稱為哈夫。曼樹或最優(yōu)二叉樹。①構(gòu)造由m棵二叉樹組成的樹林F={T1,T2,…④重復(fù)2、3步驟，直至F中只剩一棵樹為止。structHtNode//*哈夫曼樹結(jié)點的結(jié)構(gòu)。哈夫曼樹可定義為：。,wn}，構(gòu)成n棵二叉樹的集合。,Tn}，其中每一棵二叉樹Ti中只有一個帶權(quán)為wi的。樹，且新二叉樹的根結(jié)點的權(quán)值為其左右子樹根結(jié)點權(quán)值之和。③在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。左右選擇不同，得到的HuffMan樹形態(tài)不同，但WPL相同。存儲結(jié)構(gòu)可以有多種，如二叉鏈表、三叉鏈表等。–rlink:右孩子存儲位置，對于外部結(jié)點，無孩子，設(shè)為-1。假定外部結(jié)點個數(shù)為m，則內(nèi)部結(jié)點個數(shù)必為m-1，因此。最后得到的HuffMan樹必定有2m-1個結(jié)點。structHtTree/*哈夫曼樹類型*/. 哈夫曼算法例：d={d1，d2，…，dm}w={2，3，5，7，11，13，17，19，23，29，
【正文】 – 長子 兄弟表示法 [孩子兄弟表示法 ] ? 樹林的存儲表示 Hu Junfeng 26 26 樹的父指針表示法 ? 方法： 用一組連續(xù)空間 ， 即一維數(shù)組存儲樹的結(jié)點 ， 結(jié)點存放的次序是任意的 ， 數(shù)組元素為結(jié)構(gòu)體類型 ， 結(jié)點類型定義為： struct ParTreeNode /* 樹中結(jié)點結(jié)構(gòu) */ { DataType info。 /* 結(jié)點中的元素 */ int parent。 /* 結(jié)點的父結(jié)點位置 */ }。 Hu Junfeng 27 27 struct ParTree { int MAXNUM。 int n。 /* 樹中結(jié)點的個數(shù) */ struct ParTreeNode *nodelist。 /* 存放樹中的結(jié)點 */ }。 typedef struct ParTree *PParTree。 /* 樹類型的指針類型 */ struct ParTree { struct ParTreeNode nodelist[MAXNUM]。 /* 存放樹中的結(jié)點 */ int n。 /* 樹中結(jié)點的個數(shù) */ }。 typedef struct ParTree *PParTree。 /* 樹類型的指針類型 */ Hu Junfeng 28 28 父指針表示特點 ? 結(jié)點順序存放，結(jié)點的位置由結(jié)點在數(shù)組中的下標(biāo)給出。根結(jié)點無父結(jié)點，因此其 parent為 1。 ? 優(yōu)點： ① 容易求根、找父結(jié)點及其所有的祖先； ② 能找到結(jié)點的子女和兄弟 ? 缺點： ① 沒有表示出結(jié)點之間的左右次序，無法求 最左子結(jié)點和右兄弟結(jié)點； ② 找結(jié)點的子女和兄弟 比較費事； Info parent a 1 b 0 c 0 d 1 e 1 f 2 g 2 h 4 i 4 j 4 Hu Junfeng 29 29 改進(jìn)的辦法 ?按一種周游次序在數(shù)組中存放結(jié)點，依次存放樹的先根序列
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1