㈠ 哈夫曼樹的結點總個數一定是偶數嗎
不是，哈夫曼節點總數一定是奇數。
除葉子節點外，其他節點都有左右子節點，再加上根節點，所以是奇數
㈡ 對於給定的一組權值W={1, 3, 7, 8, 14},建立哈夫曼樹.
五個權值是137814
(1)從小到大排序137814(這是有序序列)
(2)每次提取最小的兩個結點,取結點1和結點3,組成新結點N4,其權值=1+3=4,
取數值較小的結點作為左分支,1作為左分支,而3就作為右分支.
(3)將新結點N4放入有序序列,保持從小到大排序:
N47814
(4)重復步驟(2),提取最小的兩個結點,N4與結點7組成新結點N11,其權值=4+7=11,
N4數值較小,作為左分支,而結點7就作為右分支.
(5)將新結點N11放入有序序列,保持從小到大排序:
8N1114
(6)重復步驟(2),提取最小的兩個結點,結點8與N11組成新結點N19,其權值=8+11=19,
結點8的數值較小,作為左分支,N11就作為右分支.
(7)將新結點N19放入有序序列,保持從小到大排序:
14N19
(8)重復步驟(2),提取剩下的兩個結點,結點14與N19組成新結點N33,其權值=14+19=33,
數值較小的結點14作為左分支,N19就作為右分支.
有序序列已經沒有結點,最後得到"哈夫曼樹":
N33
/
14N19
/
8N11
/
N47
/
13
帶權路徑長度(WPL):
根結點N33到結點14的路徑長度是1,結點14的帶權路徑長度是14*1
根結點N33到結點8的路徑長度是2,結點8的帶權路徑長度是8*2
根結點N33到結點7的路徑長度是3,結點7的帶權路徑長度是7*3
根結點N33到結點3的路徑長度是4,結點3的帶權路徑長度是3*4
根結點N33到結點1的路徑長度是4,結點1的帶權路徑長度是1*4
所以,哈夫曼樹的帶權路徑長度(WPL)等於
14*1+8*2+7*3+3*4+1*4=67
哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N33到結點14,經歷一次左分支,結點14的編碼就是0
從根結點N33到結點8,先經歷右分支,後經歷左分支,結點8的編碼就是10
從根結點N33到結點7,先後經歷三次右分支,結點7的編碼就是111
從根結點N33到結點3,先經歷兩次右分支,再經歷左分支,最後經歷右分支,結點3的編碼就是1101
從根結點N33到結點1,先經歷兩次右分支,再經歷兩次左分支,結點1的編碼就是1100
得出所有結點的"哈夫曼編碼":
權值14:0
權值8:10
權值7:111
權值3:1101
權值1:1100
//C語言測試程序(來自其他網友)
//
//輸入構造哈夫曼樹中帶權葉子結點數(n)：5
//輸入5個整數作為權值：137814
//可以得出哈夫曼樹的廣義表形式,帶權路徑長度,以及哈夫曼編碼.
#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};
//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}
//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}
//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf(" ");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}
intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf(" ");
printf("哈夫曼樹的帶權路徑長度： ");
printf("=");
printf(" =%d ",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼： ");
HuffManCoding(fbt,0);
return0;
}
㈢ 我們有個數據結構的哈夫曼編碼解碼的課程設計，你能幫幫我嗎
樹和哈夫曼樹實驗報告
一．實驗目的
練習樹和哈夫曼樹的有關操作，和各個演算法程序，理解哈夫曼樹的編碼和解碼
二．實驗環境
Microsoft visual c++
三．實驗問題描述
1. 問題描述：建立一棵用二叉鏈表方式存儲的二叉樹，並對其進行遍歷（先序、中序和後序），列印輸出遍歷結果。
基本要求：從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），並將此二叉樹按照「樹狀形式」列印輸出，然後對其進行遍歷（先序、中序和後序），最後將遍歷結果列印輸出。在遍歷演算法中要求至少有一種遍歷採用非遞歸方法。
測試數據：
ABCØØDEØGØØFØØØ（其中Ø表示空格字元）
輸出結果為：
先序：ABCDEGF
先序：CBEGDFA
先序：CGEFDBA
2. 問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮簡訊息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接受端將傳來的數據進行解碼（復原）。對於雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/解碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/解碼系統。
基本要求：(至少完成功能1-2）
一個完整的系統應具有以下功能：
I：初始化（Initialization）。從終端讀入字元集大小n，以及n個字元和n個權值，建立哈夫曼樹，並將它存於文件hfmTree中。
基本要求：
E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然後將結果存入文件CodeFile中。
D：解碼（Decoding )。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行解碼，結果存入文件TextFile中。
P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字元形式的編碼文件寫入文件CodePrint中。
T：印哈夫曼樹（TreePrinting）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字元形式的哈夫曼樹寫入文件TreePrint中。
測試數據：
設權值w=（5，29，7，8，14，23，3，11），n=8。
按照字元『0』或『1』確定找左孩子或右孩子，則權值對應的編碼為：
5：0001，29：11，7：1110，8：1111
14：110，23：01，3：0000，11：001
用下表給出的字元集和頻度的實際統計數據建立哈夫曼樹，並實現以下報文的編碼和解碼：「THIS PROGRAM IS MY FAVORITE」。
四．實驗主要程序流
實驗題目一主要程序：
1．
void CreatBiTree(BitTree *bt)//用擴展先序遍歷序列創建二叉樹，如果是#當前樹根置為空，否則申請一個新節點//
{
char ch;
ch=getchar();
if(ch=='.')*bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreatBiTree(&((*bt)->LChild));
CreatBiTree(&((*bt)->RChild));
}
}
2．void Visit(char ch)//訪問根節點
{
printf("%c ",ch);
}
3．
void PreOrder(BitTree root)
{
if (root!=NULL)
{
Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
4． void InOrder(BitTree root)
{
if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
5．int PostTreeDepth(BitTree bt) //後序遍歷求二叉樹的高度遞歸演算法//
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild); //求左子樹的深度
hr=PostTreeDepth(bt->RChild); //求右子樹的深度
max=hl>hr?hl:hr; //得到左、右子樹深度較大者
return(max+1); //返回樹的深度
}
else return(0); //如果是空樹，則返回0
}
6．void PrintTree(BitTree Boot,int nLayer) //按豎向樹狀列印的二叉樹 //
{
int i;
if(Boot==NULL) return;
PrintTree(Boot->RChild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",Boot->data);
PrintTree(Boot->LChild,nLayer+1);
}
7．void main()
{
BitTree T;
int h;
int layer;
int treeleaf;
layer=0;
printf("請輸入二叉樹中的元素(以擴展先序遍歷序列輸入,其中.代表空子樹):\n");
CreatBiTree(&T);
printf("先序遍歷序列為:");
PreOrder(T);
printf("\n中序遍歷序列為:");
InOrder(T);
printf("\n後序遍歷序列為:");
PostOrder(T);
h=PostTreeDepth(T);
printf("\此二叉樹的深度為:%d\n",h);
printf("此二叉樹的橫向顯示為：\n");
PrintTree(T,layer);
}
實驗二主要程序流：
1．int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n**********************歡迎使用哈夫曼編碼/解碼系統**********************\n";
cout<<"*您可以進行以下操作: *\n";
cout<<"*1.建立哈夫曼樹 *\n";
cout<<"*2.編碼(源文已在文件ToBeTra中，或鍵盤輸入) *\n";
cout<<"* 3.解碼(碼文已在文件CodeFile中) *\n";
cout<<"* 4.顯示碼文 *\n";
cout<<"* 5.顯示哈夫曼樹 *\n";
cout<<"* 6.退出 *\n"; cout<<"***********************************************************************\n";
cout<<"請選擇一個操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感謝使用本系統!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
2．// 建立哈夫曼樹函數
// 函數功能：建立哈夫曼樹（調用鍵盤建立哈夫曼樹或調用從文件建立哈夫曼樹的函數）
void HuffmanTree::CreateHuffmanTree()
{char Choose;
cout<<"你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？";
cin>>Choose;
if(Choose=='2') { //鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
}
}
3. // 從鍵盤建立哈夫曼樹函數
// 函數功能：從鍵盤建立哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){
int Num;
cout<<"\n請輸入源碼字元集個數：";
cin>>Num;
if (Num<=1) {
cout<<"無法建立少於2個葉子結點的哈夫曼樹。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
for(int i=0;i<Num;i++) {//讀入哈夫曼樹的葉子結點信息
cout<<"請輸入第"<<i+1<<"個字元值";
getchar();
Node[i].sourcecode=getchar(); //源文的字元存入字元數組Info[]
getchar();
cout<<"請輸入該字元的權值或頻度";
cin>>Node[i].weight; //源文的字元權重存入Node[].weight
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
Node[i].code="\0";
}
for(int j=Num;j<2*Num-1;j++) {//循環建立哈夫曼樹內部結點
int pos1,pos2;
int max1,max2;
pos2=pos1=j;
max2=max1=numeric_limits<int>::max( );
//在所有子樹的根結點中，選權重最小的兩個根結點，pos1最後應指向權重最小的根結點的下標
//pos2最後應指向權重第二小的根結點的下標
//max1存放當前找到的權重最小的根結點的權重
//max2存放當前找到的權重第二小的根結點的權重
for(int k=j-1;k>=0;k--) {
if (Node[k].parent==-1){//如果是某棵子樹的根結點
if (Node[k].weight<max1){ //發現比當前最大值還大的權重
max2=max1;
max1=Node[k].weight;
pos2=pos1;
pos1=k;
}
else
if(Node[k].weight<max2){ //發現比當前次大值還大的次大權重
max2=Node[k].weight;
pos2=k;
}
}//if (Node[j].parent==-1)
} //for
//在下標i處新構造一個哈夫曼樹的內部結點，其左、右孩子就是以上pos1、pos2所指向的結點
Node[pos1].parent=j;
Node[pos2].parent=j;
Node[j].lchild=pos1;
Node[j].rchild=pos2;
Node[j].parent=-1;
Node[j].weight=Node[pos1].weight+Node[pos2].weight;
} //for
//產生所有葉子結點中字元的編碼
for (int m=0;m<Num;m++) {
//產生Node[i].sourcecode的編碼，存入Node[i].code中
int j=m;
int j1;
while(Node[j].parent!=-1) { //從葉結點開始往根結點走，每往上走一層，就產生一位編碼存入code[]
j1=Node[j].parent;
if(Node[j1].lchild==j)
Node[m].code.insert(0,"0");
else
Node[m].code.insert(0,"1");
j=j1; }}
cout<<"哈夫曼樹已成功構造完成。\n";
//把建立好的哈夫曼樹寫入文件hfmTree.dat
char ch;
cout<<"是否要替換原來的哈夫曼樹文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打開文件
if(fop.fail()) {
cout<<"\n哈夫曼樹文件打開失敗，無法將哈夫曼樹寫入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先寫入哈夫曼樹的葉子結點個數
for(int n=0;n<2*Num-1;n++) { //最後寫入哈夫曼樹的各個結點（存儲在Node[]中）
fop.write((char*)&Node[n],sizeof(Node[n]));
flush(cout); }
fop.close(); //關閉文件
cout<<"\n哈夫曼樹已成功寫入hfmTree.dat文件。\n";}
4. // 從文件建立哈夫曼樹函數
// 函數功能：從文件建立哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::CreateHuffmanTreeFromFile(){
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼樹文件hfmTree.dat打開失敗，無法建立哈夫曼樹。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼樹文件中的數據有誤，葉子結點個數少於2個，無法建立哈夫曼樹。\n";
fip.close();
return;
}
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼樹已從文件成功構造完成。\n";
}
5. // 編碼函數
// 函數功能：為哈夫曼樹編碼
//函數參數：無
//參數返回值：無
void HuffmanTree::Encoder()
{
if(Node==NULL) { //內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}//if
char *SourceText; //字元串數組，用於存放源文
//讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入
char Choose;
cout<<"你要從文件中讀入源文(按1)，還是從鍵盤輸入源文(按2)？";
cin>>Choose;
if(Choose=='1') {
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) {
cout<<"源文文件打開失敗!無法繼續執行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次讀文件只統計文件中有多少個字元，將字元數存入k
fip1.close();
SourceText=new char[k+1]; //申請存放源文的字元數組空間
ifstream fip2("ToBeTran.txt"); //第二次讀源文文件，把內容寫入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
}
else { //從鍵盤輸入源文
string SourceBuff;
cin.ignore();
cout<<"請輸入需要編碼的源文(可輸入任意長，按回車鍵結束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
cout<<"需編碼的源文為：";
cout<<SourceText<<endl;
//開始解碼
ofstream fop("CodeFile.dat",ios::trunc); //打開碼文存放文件
int k=0;
while(SourceText[k]!='\0') //源文串中從第一個字元開始逐個編碼
{
int i;
for(i=0;i<LeafNum;i++){ //找到當前要編碼的源文的字元在哈夫曼樹Node[]中的下標
if(Node[i].sourcecode==SourceText[k]) { //將對應編碼寫入碼文文件
fop<<Node[i].code;
break;
};
}
if (i>=LeafNum) {
cout<<"源文中存在不可編碼的字元。無法繼續執行。\n"<<endl;
fop.close();
return;
}
k++; //源文串中的字元後移一個
}
fop.close();
cout<<"已完成編碼，碼文已寫入文件CodeFile.dat中。\n\n";
}
6. // 解碼函數
// 函數功能：對哈夫曼樹進行解碼
//函數參數：無
//參數返回值：無
void HuffmanTree::Decoder()
{//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
//將碼文從文件CodeFile.dat中讀入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail()) {
cout<<"沒有碼文，無法解碼。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch)){
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"經解碼得到的源文為：";
ofstream fop("TextFile.dat");
int j=LeafNum*2-1-1; //j指向哈夫曼樹的根
int i=0; //碼文從第一個符號開始，順著哈夫曼樹由根下行，按碼文的當前符號決定下行到左孩子還是右孩子
while(CodeStr[i]!='\0') { //下行到哈夫曼樹的葉子結點處，則譯出葉子結點對應的源文字元
if(CodeStr[i]=='0')
j=Node[j].lchild;
else
j=Node[j].rchild;
if(Node[j].rchild==-1) { //因為哈夫曼樹沒有度為1的結點，所以此條件等同於Node[j]為葉結點
cout<<Node[j].sourcecode; //屏幕輸出譯出的一個源文字元
fop<<Node[j].sourcecode;
j=LeafNum*2-1-1; //j再指向哈夫曼樹的根
}
i++;
}
fop.close();
cout<<"\n解碼成功且已存到文件TextFile.dat中。\n\n";
}
7. // 輸出碼文函數
// 函數功能：從文件中輸出哈夫曼樹的碼文
//函數參數：無
//參數返回值：無
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"沒有碼文文件，無法顯示碼文文件內容。\n";
return;
}
while(fip.get(ch))
{cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
8. // 輸出函數
// 函數功能：從內存或文件中直接輸出哈夫曼樹
//函數參數：無
//參數返回值：無
void HuffmanTree::PrintHuffmanTree()
{
//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return; }}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
㈣ 二叉樹遍歷演示
四、 遍歷二叉樹 二叉樹是一種非線性的數據結構，在對它進行操作時，總是需要逐一對每個數據元素實施 操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。所謂遍歷二叉樹就 是按某種順序訪問二叉樹中的每個結點一次且僅一次的過程。這里的訪問可以是輸出、比 較、更新、查看元素內容等等各種操作。
二叉樹的遍歷方式分為兩大類：一類按根、左子樹和右子樹三個部分進行訪問；另一類按 層次訪問。下面我們將分別進行討論。
1、 按根、左子樹和右子樹三部分進行遍歷 遍歷二叉樹的順序存在下面6種可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三種順序在左右子樹之間均是先右子樹後左子樹，這與人們先左後右的習慣不同，因此，往往不予採用。餘下的三種順序TLR、LTR和LRT根據根訪問的位置不同分別被稱為先序遍歷、中序遍歷和後序遍歷。（1）先序遍歷若二叉樹為空，則結束遍歷操作；否則訪問根結點；先序遍歷左子樹；先序遍歷右子樹。（2）中序遍歷若二叉樹為空，則結束遍歷操作；否則中序遍歷左子樹；訪問根結點；中序遍歷右子樹。（3）後序遍歷若二叉樹為空，則結束遍歷操作；否則後序遍歷左子樹；後序遍歷右子樹；訪問根結點。例如。以下是一棵二叉樹及其經過三種遍歷所得到的相應遍歷序列二叉樹的兩種遍歷方法：（1）對一棵二叉樹中序遍歷時，若我們將二叉樹嚴格地按左子樹的所有結點位於根結點的左側，右子樹的所有結點位於根右側的形式繪制，就可以對每個結點做一條垂線，映射到下面的水平線上，由此得到的順序就是該二叉樹的中序遍歷序列
（2）任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，這條包線對於理解二叉樹的遍歷過程很有用。 由此可以看出：（1）遍歷操作實際上是將非線性結構線性化的過程，其結果為線性序列，並根據採用的遍歷順序分別稱為先序序列、中序序列或後序序列；（2）遍歷操作是一個遞歸的過程，因此，這三種遍歷操作的演算法可以用遞歸函數實現。（1）先序遍歷遞歸演算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild);
}（2）中序遍歷遞歸演算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}（3）後序遍歷遞歸演算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
} 2 、按層次遍歷二叉樹 實現方法為從上層到下層，每層中從左側到右側依次訪問每個結點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。
void LevelOreder(QBTree BT) {
for (i=1;i<=BT.n;i++)
if (BT.elem[i]!='#') Visite(BT.elem[i]);
}二叉樹用鏈式存儲結構表示時，按層遍歷的演算法實現訪問過程描述如下：訪問根結點，並將該結點記錄下來；若記錄的所有結點都已處理完畢，則結束遍歷操作；否則重復下列操作。取出記錄中第一個還沒有訪問孩子的結點，若它有左孩子，則訪問左孩子，並將記錄下來；若它有右孩子，則訪問右孩子，並記錄下來。 在這個演算法中，應使用一個隊列結構完成這項操作。所謂記錄訪問結點就是入隊操作； 而取出記錄的結點就是出隊操作。這樣一來，我們的演算法就可以描述成下列形式：（1）訪問根結點，並將根結點入隊；（2）當隊列不空時，重復下列操作：從隊列退出一個結點；若其有左孩子，則訪問左孩子，並將其左孩子入隊；若其有右孩子，則訪問右孩子，並將其右孩子入隊；void LevelOrder(BTree *BT) {
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p); //訪問根結點，並將根結點入隊
while (!QueueEmpty(Q)) { //當隊非空時重復執行下列操作
DeQueue(&Q,&p); //出隊
if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p->Lchild); //處理左孩子<br> if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //處理右孩子<br> }
}
五、典型二叉樹的操作演算法 1、 輸入一個二叉樹的先序序列，構造這棵二叉樹 為了保證唯一地構造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉 樹的位置上填補一個特殊的字元，比如，'#'。在演算法中，需要對每個輸入的字元進行判 斷，如果對應的字元是'#'，則在相應的位置上構造一棵空二叉樹；否則，創建一個新結 點。整個演算法結構以先序遍歷遞歸演算法為基礎，二叉樹中結點之間的指針連接是通過指針 參數在遞歸調用返回時完成。演算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch=='#') return NULL; //構造空樹
else { BT=(BTree)malloc(sizeof(BTLinklist)); //構造新結點
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //構造左子樹
BT->rchild =Pre_Create_BT( ); //構造右子樹
return BT;
}
} 2、 計算一棵二叉樹的葉子結點數目 這個操作可以使用三種遍歷順序中的任何一種，只是需要將訪問操作變成判斷該結點是否 為葉子結點，如果是葉子結點將累加器加1即可。下面這個演算法是利用中序遍歷實現的。演算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT->child,&count); //計算左子樹的葉子結點個數
if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
Leaf(BT->rchild,&count); //計算右子樹的葉子結點個數
}
} 3、 交換二叉樹的左右子樹 許多操作可以利用三種遍歷順序的任何一種，只是某種遍歷順序實現起來更加方便一 些。而有些操作則不然，它只能使用其中的一種或兩種遍歷順序。將二叉樹中所有結點的左右子樹進行交換這個操作就屬於這類情況。演算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchild<->BT->rchild;
}
} 4 、求二叉樹的高度 這個操作使用後序遍歷比較符合人們求解二叉樹高度的思維方式。首先分別求出左右子樹 的高度，在此基礎上得出該棵樹的高度，即左右子樹較大的高度值加1。演算法：int hight(BTree BT) { //h1和h2分別是以BT為根的左右子樹的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
} 六、樹、森林與二叉樹的轉換 1、 樹、森林轉換成二叉樹 將一棵樹轉換成二叉樹的方法： 將一棵樹轉換成二叉樹實際上就是將這棵樹用孩子兄弟表示法存儲即可，此時，樹中的每個結點最多有兩個指針：一個指針指向第一個孩子，另一個指針指向右側第一個兄弟。當你將這兩個指針看作是二叉樹中的左孩子指針和孩子右指針時，就是一棵二叉樹了。 特點：一棵樹轉換成二叉樹後，根結點沒有右孩子。 將森林轉換成二叉樹的方法與一棵樹轉換成二叉樹的方法類似，只是把森林中所有樹的根 結點看作兄弟關系，並對其中的每棵樹依依地進行轉換。 2 、二叉樹還原成樹或森林 這個過程實際上是樹、森林轉換成二叉樹的逆過程，即將該二叉樹看作是樹或森林的孩子兄弟表示法。比如，若二叉樹為空，樹也為空；否則，由二叉樹的根結點開始，延右指針向下走，直到為空，途經的結點個數是相應森林所含樹的棵數；若某個結點的左指針非空，說明這個結點在樹中必有孩子，並且從二叉樹中該結點左指針所指結點開始，延右指針向下走，直到為空，途經的結點個數就是這個結點的孩子數目。
第 3 節 哈夫曼樹及其應用 1、哈夫曼樹的定義及特點
在二叉樹中，一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。這三棵二叉樹的帶權路徑長度分別為：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼樹的一個重要特點是：沒有度為1的結點。
2、構造哈夫曼樹的過程：
（1）將給定的n個權值{w1,w2,...,wn}作為n個根結點的權值構造一個具有n棵二叉樹的森林{T1,T2,...,Tn}，其中每棵二叉樹只有一個根結點；（2）在森林中選取兩棵根結點權值最小的二叉樹作為左右子樹構造一棵新二叉樹，新二叉樹的根結點權值為這兩棵樹根的權值之和；（3）在森林中，將上面選擇的這兩棵根權值最小的二叉樹從森林中刪除，並將剛剛新構造的二叉樹加入到森林中；（4）重復上面（2）和（3），直到森林中只有一棵二叉樹為止。這棵二叉樹就是哈夫曼樹。 例如： 假設有一組權值{5,29,7,8,14,23,3,11}，下面我們將利用這組權值演示構造哈夫曼樹的過程。
它的帶權的路徑長度為：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定樹 在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響著 程序的執行效率。例如，編制一個程序，將百分制轉換成五個等級輸出。大家可能認為 這個程序很簡單，並且很快就可以用下列形式編寫出來：if (socre<60) printf("bad");
else if (socre<70) printf("pass");
else if (score<80) printf("general");
else if (score<90) printf("good");
esle printf("very good"); 在實際應用中，往往各個分數段的分布並不是均勻的。下面就是在一次考試中某門課程的各分數段的分布情況：
4．前綴編碼 在電文傳輸中，需要將電文中出現的每個字元進行二進制編碼。在設計編碼時需要遵守兩 個原則：（1）發送方傳輸的二進制編碼，到接收方解碼後必須具有唯一性，即解碼結果與發送方發送的電文完全一樣；（2）發送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。
（1）等長編碼 這種編碼方式的特點是每個字元的編碼長度相同（編碼長度就是每個編碼所含的二進制位 數）。假設字元集只含有4個字元A，B，C，D，用二進制兩位表示的編碼分別為00，01，10，11。若現在有一段電文為：ABACCDA，則應發送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文後，將按兩位一段進行解碼。這種編碼的特點是解碼簡單且具有唯一性，但編碼長度並不是最短的。（2）不等長編碼 在傳送電文時，為了使其二進制位數盡可能地少，可以將每個字元的編碼設計為不等長的，使用頻度較高的字元分配一個相對比較短的編碼，使用頻度較低的字元分配一個比較長的編碼。例如，可以為A，B，C，D四個字元分別分配0，00，1，01，並可將上述電文用二進制序列：000011010發送，其長度只有9個二進制位，但隨之帶來了一個問題，接收方接到這段電文後無法進行解碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即解碼不唯一，因此這種編碼方法不可使用。（1）利用字元集中每個字元的使用頻率作為權值構造一個哈夫曼樹；（2）從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，並從根到葉子方向形成該葉子結點的編碼。假設有一個電文字元集中有8個字元，每個字元的使用頻率分別為{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，現以此為例設計哈夫曼編碼。
哈夫曼編碼設計過程為：
（1）為方便計算，將所有字元的頻度乘以100，使其轉換成整型數值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的數值作為葉子結點的權值構造一棵哈夫曼樹，如圖5-27所示；
（3）由此哈夫曼樹生成哈夫曼編碼，如圖5-28所示。
最後得出每個字元的編碼為：比如，發送一段編碼：0000011011010010， 接收方可以准確地通過解碼得到：⑥⑥⑦⑤②⑧。
㈤ 帶權9.1.3.5.6的五個葉子生成的哈夫曼樹，帶權路徑長度怎麼算
五個葉子的權值是91356
(1)將權值從小到大排序後是13569(這是有序序列)
(2)每次提取最小的兩個節點,取節點1和節點3,組成新節點N4,其權值=1+3=4,
節點1的數值較小,作為左分支,節點3就作為右分支.
(3)將新節點N4放入有序序列,保持從小到大排序:
N4569(節點1和3已經提取掉)
(4)重復步驟(2),提取最小的兩個節點,N4與節點5組成新節點N9,其權值=4+5,
N4的數值較小,作為左分支,節點5就作為右分支.
(5)將新節點N9放入有序序列,保持從小到大排序:
69N9(注意,要將新節點N9排在後,如果順序是6N99則會有不同的結果)
(6)重復步驟(2),完成剩下的節點,最後,得到"哈夫曼樹":
N24
/
N9N15
//
N4569
/
13
根節點N24到節點9的路徑長度是2,節點9的帶權路徑長度是9*2
根節點N24到節點6的路徑長度是2,節點6的帶權路徑長度是6*2
如此類推,可以得出其它節點的帶權路徑長度.
所以,哈夫曼樹的帶權路徑長度WPL等於
9*2+6*2+5*2+3*3+1*3=52
哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根節點N24到節點9,先後經歷兩次右分支,節點9的編碼就是11
從根節點N24到節點6,先經歷右分支,再經歷左分支,節點6的編碼就是10
從根節點N24到節點5,先經歷左分支,再經歷右分支,節點5的編碼就是01
如此類推,可以得出所有的節點的"哈夫曼編碼":
權值9:11
權值6:10
權值5:01
權值3:001
權值1:000
//C語言測試程序
//輸入構造哈夫曼樹中帶權葉子結點數n：5
//輸入5個整數作為權值：91356
//可以得出哈夫曼樹的帶權路徑長度,以及哈夫曼編碼.
#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};
//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}
//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}
//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf(" ");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}
intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數n：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf(" ");
printf("哈夫曼樹的帶權路徑長度： ");
printf("=");
printf(" =%d ",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼： ");
HuffManCoding(fbt,0);
return0;
}
㈥ 1、建立二叉樹，並進行先序、中序和後序遍歷。 2、求二叉樹的深度及葉子結點的個數。 3、構造哈夫曼樹及哈
0是初始節點數
輸入時請一次性輸完ABCффDEфGффFффф在按ENTER鍵 不要輸入一個按一下
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //結點的最大個數
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結點類型
typedef BinTNode *BinTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點
T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //訪問結點
Preorder(T->lchild); //先序遍歷左子樹
Preorder(T->rchild); //先序遍歷右子樹
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍歷左子樹
printf("%c",T->data); //訪問結點
Inorder(T->rchild); //中序遍歷右子樹
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //後序遍歷左子樹
Postorder(T->rchild); //後序遍歷右子樹
printf("%c",T->data); //訪問結點
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹，返回根結點
do { //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //先判斷節點數是否已有。不用再先選擇4，求出該樹的結點數。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //輸入菜單序號（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //後序遍歷
break;
case 4: depth=TreeDepth(root); //求樹的深度及葉子數
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
㈦ 計算哈夫曼編碼
六個權值(頻率)是0.040.060.130.250.280.33
(1)從小到大排序0.040.060.130.250.280.33(這是有序序列)
(2)每次提取最小的兩個結點,取結點0.04和結點0.06,組成新結點N0.10,其權值=0.04+0.06=0.10,
取數值較小的結點作為左分支,結點0.04為左分支,結點0.06為右分支.
(3)將新結點N0.10放入有序序列,保持從小到大排序:
N0.100.130.250.280.33
(4)重復步驟(2),提取最小的兩個結點,N0.10與結點0.13組成新結點N0.23,其權值=0.10+0.13=0.23,
N0.10的數值較小,作為左分支,結點0.13就作為右分支.
(5)將新結點N0.23放入有序序列,保持從小到大排序:
N0.230.250.280.33
(6)重復步驟(2),提取最小的兩個結點,N0.23與結點0.25組成新結點N0.48,其權值=0.23+0.25=0.48,
N0.23的數值較小,作為左分支,結點0.25就作為右分支.
(7)將新結點N0.48放入有序序列,保持從小到大排序:
0.280.33N0.48
(8)重復步驟(2),提取最小的兩個結點,結點0.28與結點0.33組成新結點N0.61,其權值=0.28+0.33=0.61,
結點0.28的數值較小,作為左分支,結點0.33就作為右分支.
(9)將新結點N0.61放入有序序列,保持從小到大排序:
N0.48N0.61
(10)重復步驟(2),提取剩下的兩個結點,N0.48與N0.61組成新結點N1.09,其權值=0.48+0.61=1.09,
數值較小的N0.48作為左分支,N0.61就作為右分支.
有序序列已經沒有結點,得到"哈夫曼樹":
N1.09
/
N0.48N0.61
//
N0.230.250.280.33
/
N0.100.13
/
0.040.06
帶權路徑長度(WPL):
根結點N1.09到結點0.33的路徑長度是2,結點0.33的帶權路徑長度是0.33*2
根結點N1.09到結點0.28的路徑長度是2,結點0.28的帶權路徑長度是0.28*2
根結點N1.09到結點0.25的路徑長度是2,結點0.25的帶權路徑長度是0.25*2
根結點N1.09到結點0.13的路徑長度是3,結點0.13的帶權路徑長度是0.13*3
根結點N1.09到結點0.06的路徑長度是4,結點0.06的帶權路徑長度是0.06*4
根結點N1.09到結點0.04的路徑長度是4,結點0.04的帶權路徑長度是0.04*4
所以,哈夫曼樹的帶權路徑長度(WPL)等於
0.33*2+0.28*2+0.25*2+0.13*3+0.06*4+0.04*4=2.51
哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N1.09到結點0.33,先後經歷兩次右分支,結點0.33的編碼就是11
從根結點N1.09到結點0.28,先經歷右分支,後經歷左分支,結點0.28的編碼就是10
從根結點N1.09到結點0.25,先經歷左分支,後經歷右分支,結點0.25的編碼就是01
從根結點N1.09到結點0.13,先經歷兩次左分支,後經歷右分支,結點0.13的編碼就是001
從根結點N1.09到結點0.06,先經歷三次左分支,後經歷右分支,結點0.06的編碼就是0001
從根結點N1.09到結點0.04,先後經歷四次左分支,結點0.04的編碼就是0000
得出所有結點的"哈夫曼編碼":
字元f(頻率0.33):11
字元e(頻率0.28):10
字元d(頻率0.25):01
字元c(頻率0.13):001
字元b(頻率0.06):0001
字元a(頻率0.04):0000
//C語言測試程序(來自其他網友)
//
//輸入構造哈夫曼樹中帶權葉子結點數(n)：6
//輸入6個整數作為權值：4613252833(將頻率的小數形式改為整數形式)
//可以得出哈夫曼樹的廣義表形式,帶權路徑長度,以及哈夫曼編碼.
#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};
//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}
//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}
//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf(" ");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}
intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf(" ");
printf("哈夫曼樹的帶權路徑長度： ");
printf("=");
printf(" =%d ",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼： ");
HuffManCoding(fbt,0);
return0;
}
㈧ 已知葉子結點的權值集合w=2,2,3,3,5,8 構造哈夫曼樹並計算帶權路徑長度
六個權值是2(0)2(1)3(0)3(1)58
注意:第一個"2"的順序在前,所以寫成2(0),第二個"2"的順序在後,所以寫成2(1),
同理,兩個"3"分別寫成3(0),3(1)
(1)從小到大排序2(0)2(1)3(0)3(1)58(這是有序序列)
(2)每次提取最小的兩個結點,取結點2(0)和結點2(1),組成新結點N4,其權值=2+2=4,
取數值較小的結點作為左分支,盡管兩個結點的數值一樣,但是,
把順序在前的2(0)作為左分支,而2(1)就作為右分支.
(3)將新結點N4放入有序序列,保持從小到大排序:
3(0)3(1)N458
(4)重復步驟(2),提取最小的兩個結點,結點3(0)與結點3(1)組成新結點N6,其權值=3+3=6,
結點3(0)與結點3(1)的數值一樣,但是,結點3(0)的順序在前,所以,
把結點3(0)作為左分支,而結點3(1)就作為右分支.
(5)將新結點N6放入有序序列,保持從小到大排序:
N45N68
(6)重復步驟(2),提取最小的兩個結點,N4與結點5組成新結點N9,其權值=4+5=9,
N4的數值較小,作為左分支,5就作為右分支.
(7)將新結點N9放入有序序列,保持從小到大排序:
N68N9
(8)重復步驟(2),提取最小的兩個結點,N6與結點8組成新結點N14,其權值=6+8=14,
N6作為左分支,結點8就作為右分支.
(9)將新結點N4放入有序序列,保持從小到大排序:
N9N14
(10)重復步驟(2),提取剩下的兩個結點,N9與N14組成新結點N23,其權值=9+14=23,
數值較小的N9作為左分支,N14就作為右分支.
有序序列已經沒有結點,最後得到"哈夫曼樹":
N23
/
N9N14
//
N45N68
//
2(0)2(1)3(0)3(1)
帶權路徑長度(WPL):
根結點N23到結點8的路徑長度是2,結點8的帶權路徑長度是8*2
根結點N23到結點5的路徑長度是2,結點3的帶權路徑長度是5*2
根結點N23到結點3(0)的路徑長度是3,結點3(0)的帶權路徑長度是3*3
根結點N23到結點3(1)的路徑長度是3,結點3(1)的帶權路徑長度是3*3
根結點N23到結點2(0)的路徑長度是3,結點2(0)的帶權路徑長度是2*3
根結點N23到結點2(1)的路徑長度是3,結點2(1)的帶權路徑長度是2*3
所以,哈夫曼樹的帶權路徑長度(WPL)等於
8*2+5*2+3*3+3*3+2*3+2*3=56
哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N23到結點8,先後經歷兩次右分支,結點8的編碼就是11
從根結點N23到結點5,先經歷左分支,後經歷右分支,結點5的編碼就是01
從根結點N23到結點3(0),先經歷右分支,後經歷兩次左分支,結點3(0)的編碼就是100
從根結點N23到結點3(1),先經歷右分支,後經歷左分支,最後經歷右分支,結點3(1)的編碼就是101
從根結點N23到結點2(0),先後經歷三次左分支,結點2(0)的編碼就是000
從根結點N23到結點2(1),先經歷兩次左分支,最後經歷右分支,結點2(1)的編碼就是001
得出所有結點的"哈夫曼編碼":
權值8:11
權值5:01
權值3(0):100
權值3(1):101
權值2(0):000
權值2(1):001
//C語言測試程序(來自其他網友)
//
//輸入構造哈夫曼樹中帶權葉子結點數(n)：6
//輸入6個整數作為權值：223358
//可以得出哈夫曼樹的廣義表形式,帶權路徑長度,以及哈夫曼編碼.
#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};
//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}
//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}
//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf(" ");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}
intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf(" ");
printf("哈夫曼樹的帶權路徑長度： ");
printf("=");
printf(" =%d ",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼： ");
HuffManCoding(fbt,0);
return0;
}