⑴ 簡述哈夫曼樹的性質。
哈 夫 曼 樹
2.9 二叉樹的應用
2.9.1 哈夫曼樹及應用
哈夫曼樹又稱最優樹（二叉樹），是一類帶權路徑最短的樹。構造這種樹的演算法最早是由哈夫曼(Huffman)1952年提出，這種樹在信息檢索中很有用。
結點之間的路徑長度：從一個結點到另一個結點之間的分支數目。
樹的路徑長度：從樹的根到樹中每一個結點的路徑長度之和。
結點的帶權路徑長度：從該結點到樹根之間的路徑長度與結點上權的乘積。
樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，記作：
WPL為最小的二叉樹就稱作最優二叉樹或哈夫曼樹。
完全二叉樹不一定是最優二叉樹。
哈夫曼樹的構造：
（1）根據給定的n個權值{w1,w2,...,wn}構造n棵二叉樹的集合F={T1,T2,...,Tn}，其中Ti中只有一個權值為wi的根結點，左右子樹為空；
（2）在F中選取兩棵根結點的權值為最小的數作為左、右子樹以構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為左、右子樹上根結點的權值之和。
（3）將新的二叉樹加入到F中，刪除原兩棵根結點權值最小的樹；
（4）重復（2）和（3）直到F中只含一棵樹為止，這棵樹就是哈夫曼樹。
例1：
例2：
結點的存儲結構:
構造哈夫曼樹的演算法說明：
#define n /* 葉子總數 */
#define m 2*n-1 /* 結點總數 */
證：由性質3，葉子結點數 n0=n2+1，故哈夫曼樹結點總數為 n0+n2=n0+(n0-1)=2*n0-1
例3 在解某些判定問題時，利用哈夫曼樹獲得最佳判定演算法。
（a)
WPL=0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15
（b)(c)
WPL=0.4*1+0.3*2+0.15*3+0.05*4+0.1*4=2.05 WPL=0.05*3+0.15*3+0.4*2+0.3*2+0.1*2=2.2
哈夫曼編碼
從哈夫曼樹根結點開始，對左子樹分配代碼「0」，右子樹分配代碼「1」，一直到達葉子結點為止，然後將從樹根沿每條路徑到達葉子結點的代碼排列起來，便得到了哈夫曼編碼。
例，對電文 EMCAD 編碼。若等長編碼，則
EMCAD => 000001010011100 共15位
設各字母的使用頻度為 {E,M,C,A,D}={1,2,3,3,4}。用頻度為權值生成哈夫曼樹，並在葉子上標注對應的字母，樹枝分配代碼「0」或「1」:
各字母的編碼即為哈夫曼編碼： EMCAD => 000001011011 共12位
2.9.2 二叉排序樹
二叉排序樹是一種特殊結構的二叉樹，它作為一種表的組織手段，通常被稱為樹表。可以作為一種排序和檢索的手段。
定義 二叉排序樹或是空樹，或是具有下述性質的二叉樹：其左子樹上所有結點的數據值均小於根結點的數據值；右子樹上所有結點的數據值均大於或等於根結點的數據值。左子樹和右子樹又各是一棵二叉排序樹。
對二叉排序樹，若按中序遍歷就可以得到由小到大的有序序列。如上圖，中序遍歷得：
{2，3，4，8，9，9，10，13，15，18}
二叉排序樹的生成
對任意一組數據元素序列{R1,R2,...,Rn}，要生成一棵二叉排序樹的過程為：
（1）令R1為二叉樹的根；
（2）若R2<R1，令R2為R1左子樹的根結點，否則R2為R1右子樹的根結點；
（3）對R3,...,Rn結點的插入方法同上。
例，數據元素序列{10，18，3，8，12，2，7，3}，其生成二叉排序樹的過程如下：
二叉排序樹中結點的刪除
要求刪除一個結點後的二叉樹仍是一棵二叉排序樹。演算法思想，分以下幾種情況考慮：
（1）被刪除的結點是葉子結點，則只需修改其雙親結點的指針既可；
（2）被刪除結點p只有左子樹pL或右子樹pR，此時只要使左子樹pL或右子樹pR成為p雙親結點q的左子樹或右子樹即可。
（3）若被刪除結點p的左、右子樹均非空，有兩種做法：
*
令pL直接鏈接到q的左（或右）孩子鏈域上，pR鏈接到p結點中序前趨結點s上（s是pL最右下的結點）；
*
以p結點的直接中序前趨或後繼替代p所指結點，然後再從原二叉排序樹中刪去該直接前趨或後繼。
⑵ 關於哈夫曼編碼試題的計算
太復雜了，樓主一會記得多給我點分！謝謝啦！
先設權w=(31,22,18,14,10,4,1),n=7,則m=13,按照哈夫曼演算法可以構造一棵哈夫曼樹如下：
100
40 60
22 18 31 29
14 15
10 5
4 1
末端結點為22，18，31，14，10，4，1，你自己把上面的加上線連成一棵二叉樹就行，記得左分支標0，右分支標1（為了得出後面的哈夫曼編碼HC）
然後需要列出HT初態表和HT終態表，如下：
HT初態表 HT終態表
weight parent lchild rchild weight parent lchild rchild
1 31 0 0 0 31 12 0 0
2 22 0 0 0 22 11 0 0
3 18 0 0 0 18 11 0 0
4 14 0 0 0 14 10 0 0
5 10 0 0 0 10 9 0 0
6 4 0 0 0 4 8 0 0
7 1 0 0 0 1 8 0 0
8 - 0 0 0 5 9 6 7
9 - 0 0 0 15 10 5 8
10 - 0 0 0 29 12 4 9
11 - 0 0 0 40 13 2 3
12 - 0 0 0 60 13 1 10
13 - 0 0 0 100 0 11 12
最後得出哈夫曼編碼HC：
1——>10
2——>00
3——>01
4——>110
5——>1110
6——>11110
7——>11111
平均碼字長度為（0.31＋0.22＋0.18）×2＋0.14×3＋0.1×4
＋（0.04＋0.01）×5＝2.47
編碼效率為[（1－0.01）×3＋0.01×2]/2.47=1.21
解答完畢！
補充：對於其中的編碼效率問題本人有點淡忘，我選擇的是用
普通平均編碼長度除上了哈夫曼平均編碼長度得出，不知對否。
辛苦半天，望樓主能賜我分數，不勝感激！
註：提交後發現格式不太規整，對於哈夫曼樹誰是誰的左孩子、右孩子比較容易分出（左右孩子結點相加可知父親結點），對於HT初態表和HT終態表1列1列的看就行！其中數字第一列為序號，從第2列到第9列分別對應HT初態表的weight parent lchild rchild 和HT終態表的weight parent lchild rchild 。
⑶ 數據結構樹和二叉樹的實際應用
數據結構樹和二叉樹的實際應用：哈夫曼編碼。
利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮簡訊息傳輸的時間，降低傳輸成本。根據哈夫曼編碼的原理，編寫一個程序，在用戶輸入結點權值的基礎上求哈夫曼編碼。
從鍵盤輸入若干字元及每個字元出現的頻率，將字元出現的頻率作為結點的權值，建立哈夫曼樹，求出各字元的哈夫曼編碼。
要求：輸出存放哈夫曼樹的數組HT的初態和終態；輸出每個字元的哈夫曼編碼；輸入由上述若干字元組成的字元串，對電文進行編碼並輸出；輸入電文的哈夫曼編碼，進行解碼並輸出。
在計算機科學中，樹是用來模擬具有樹狀結構性質的數據集合。它是由n（n>=0）個有限節點組成一個具有層次關系的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。(n = 0 時稱為空樹)
特點有：每個節點有零個或多個子節點；沒有父節點的節點稱為根節點；每一個非根節點有且只有一個父節點；除了根節點外，每個子節點可以分為多個不相交的子樹。
二叉樹的性質：
二叉樹的第ii層至多擁有2i−12i−1個節點數, ii>=1)；
深度為 kk的二叉樹至多總共有 2k−12k−1 個節點數,(kk>=1)；
對任何一棵非空的二叉樹TT，如果其葉片(終端節點)數為 n0n0，分支度為22的節點數為 n2n2，則 n0=n2+1。
(3)哈夫曼樹ht存儲結構初態和終態擴展閱讀：
樹狀圖由n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹；
單個結點是一棵樹，樹根就是該結點本身。
設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱T1,T2,..,Tk為結點n的子樹。
空集合也是樹，稱為空樹。空樹中沒有結點。
⑷ 什麼是哈夫曼樹呢
夫曼樹是帶權路徑長度最小的二叉樹，用途是平均查找信息的代價最小。
普通二叉樹的用途也普通，比較通用，就是信息存儲和查找。
普通二叉樹可能有的只有一個子節點，而哈夫曼樹一定有兩個。
⑸ 哈夫曼樹HT存儲結構的初態和末態怎麼寫
定義哈夫曼樹與編碼的存儲結構與數據類型
typedef struct
{
char data;//節點值
int weight; //權重
int parent; //雙親節點
int lchild; //左孩子節點
int rchild; //右孩子節點
} HTNode;
typedef struct
{
char cd[N]; //存放哈夫曼碼
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //創建哈夫曼樹
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根據哈夫曼樹計算每個元素的哈夫曼編碼
void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出每個元素的哈夫曼編碼
⑹ 哈夫曼樹的構造是什麼
哈夫曼樹構造：結構化的Huffman演算法生成的Huffman樹子樹都是有序的，所以一般生成Huffman樹時都為節點排序，即使這樣結果也不唯一。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
歷史
1951年，哈夫曼在麻省理工學院（MIT）攻讀博士學位，他和修讀資訊理論課程的同學得選擇是完成學期報告還是期末考試。
導師羅伯特·法諾（Robert Fano）出的學期報告題目是：查找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。
哈夫曼使用自底向上的方法構建二叉樹，避免了次優演算法香農-范諾編碼（Shannon–Fano coding）的最大弊端──自頂向下構建樹。
1952年，於論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Rendancy Codes）中發表了這個編碼方法。
⑺ 哈夫曼樹的建立
。。作業吧，運行可用，自己再試試。
//huffman_h.h 哈夫曼樹的頭文件
#include"iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef char ElemType;
typedef struct{
ElemType elem;
unsigned int weight;
unsigned int parent,lchild,rchild,tag;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // 保存符號信息;
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
int i;
s1=s2=0;
for(i=1;i<=n;i++){
if(HT[i].weight<HT[s2].weight&&HT[i].parent==0&&s2!=0){
if(HT[i].weight<HT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
}
if((s1==0||s2==0)&&HT[i].parent==0){
if(s1==0) s1=i;
else if(s2==0) {
if(HT[i].weight<HT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
} // end of else if
if(s1>s2) {i=s1; s1=s2; s2=i;}
// end of if
// end of for
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, Weight* &w, int n) {
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
//本函數實現選擇方式：從左往右選擇兩個小權值結點，結點信息在前面的為左子樹，其後為右子樹
//修改選擇方式：依序選擇兩個小權值結點，權值小的為左子樹。！！
int i, j, m, s1,s2;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].elem=w[i-1].elem;
HT[i].weight=w[i-1].m_weight;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼樹的構造過程如下所示：\n");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}//for
//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd = (char *)malloc((n+1)*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].tag = 0;
while (p) {
if (HT[p].tag==0) { // 向左
HT[p].tag = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].tag==1) { // 向右
HT[p].tag = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].tag = 0; p = HT[p].parent; --cdlen;
}//else
}//while
} // HuffmanCoding
/*
//--- 從葉子到根逆向求每個字元的哈夫曼編碼 ---
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
cd[n-1] = '\0'; // 編碼結束符。
for (i=1; i<=n; ++i) { // 逐個字元求哈夫曼編碼
start = n-1; // 編碼結束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 從葉子到根逆向求編碼
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 為第i個字元編碼分配空間
strcpy(HC[i], &cd[start]); // 從cd復制編碼(串)到HC
}
free(cd); // 釋放工作空間
*/
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].weight,HC[i]);
}
//主函數
//huffman.cpp
#include"huffman_h.h"
void main()
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;
printf("請輸入構建哈夫曼樹的結點數:" );
cin>>n; //cout<<endl;
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
//cout<<"請輸入第"<<i+1<<"個結點編號及其權值（如a 100）:"<<endl;
printf("請輸入結點編號及其權值（如a 100）:" );
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(HT,HC,w,n);
OutputHuffmanCode(HT,HC,n);
}
⑻ 數據結構 請問那個終態圖中 parent lchild rchild 這三行數據是怎樣算出來的。。。
typedef struct
{unsigned int weight;
unsigned int parent,lchild,rchild;
}htnode,*huffmantree;
typedef char *huffmantree;
演算法：
huffmantree crt_huffmantree(int *w,int n)
{huffmantree ht;
m=2*n-1;
ht=(huffmantree)malloc((m+1)*sizeof(htnode));
for(p=ht,i=1;i<=n;i++,p++,w++)
*p={*w,0,0,0};
for(;i<=m;i++,p++)
*p={0,0,0,0};
for(i=n+1;i<=m;i++)
{select(ht,i-1,s1,s2);
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
return ht;
}
帶權路徑長度：
w=(3+6+7+8)*4+(9+10+16+17)*3+24*2=300
(8)哈夫曼樹ht存儲結構初態和終態擴展閱讀：
構成初始集合
對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
選取左右子樹
在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
⑼ Huffman編碼，存儲結構的終結狀態是什麼意思怎麼來的
哈夫曼樹 在一般的數據結構的書中，樹的那章後面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如JPEG中就應用了哈夫曼編碼。