⑴ 簡述哈夫曼樹的性質。
哈 夫 曼 樹
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所指結點，然後再從原二叉排序樹中刪去該直接前趨或後繼。
⑵ 赫夫曼樹
註：第一題 huffman 樹以及 huffman編碼
我將第二題與第三題與用鄰接矩陣存儲圖相關的操作放在了一起完成
第三題則是利用鄰接表
1.第一題
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define LEN 8
#define MAXLEAF 6 // 最大葉子結點數目
#define MAXNODE (MAXLEAF*2)-1
typedef float ElemType;
typedef struct /* this structure stores the information of code */
{
int start; /* 存放編碼的起始位置右至左（高位至低位）*/
int bit[LEN]; /* 存放 huffman編碼 */
}HCode;
typedef HCode HuffCode[MAXLEAF];
typedef struct /* huffman tree結點的結構 */
{
int parent;
int LChild;
int RChild;
ElemType weight;
}HNode;
typedef HNode Huffman[MAXLEAF*2-1];
void createHuffmanTree(Huffman h,int leaves,ElemType *weight)
{
int i,j;
for(i=0;i<leaves*2-1;i++) /* 初始化huffman tree */
{
(h+i)->parent=-1;
(h+i)->LChild=-1;
(h+i)->RChild=-1;
(h+i)->weight=0;
}
for(i=0;i<leaves;i++) /* 給葉子賦權重 */
{
(h+i)->weight=*(weight+i);
}
/* 上一個循環葉子已經帶權,下面這個循環用來生成新根
* 新根數量為n-1
*/
for(i=0;i<leaves-1;i++)
{
ElemType m1, m2;
int m1_pos, m2_pos;
m1=m2=65536; /* m1存放最小的權值m2存放次小的權值 */
m1_pos=m2_pos=0; /* m1存放最小的權值對應下標m2存放次小的權值對應下標*/
for(j=0;j<leaves+i;j++)
{
if((h+j)->weight<m1&&(h+j)->parent==-1)
{
m2=m1;
m1=(h+j)->weight;
m2_pos=m1_pos;
m1_pos=j;
}
else if((h+j)->weight<m2&&(h+j)->parent==-1)
{
m2=(h+j)->weight;
m2_pos=j;
}
}
(h+leaves+i)->parent=-1; // 生成新根，無雙親-1
(h+leaves+i)->LChild=m1_pos; // 新根左孩子在數組中的下標
(h+leaves+i)->RChild=m2_pos; // 新根右孩子在數組中的下標
(h+m1_pos)->parent=leaves+i; // 原根的父親位置
(h+m2_pos)->parent=leaves+i; // 原根的父親位置
(h+leaves+i)->weight=m2+m1;
}
}
void huffmancode(Huffman h,HuffCode code,int leaves)
{
int i,j,p,c;
HCode hf;
/*從葉子結點開始向上回溯 從而計算出huffman code */
for(i=0;i<leaves;i++)
{
c=i;
p=h[i].parent;
hf.start=LEN-1;
while(p!=-1)
{
if(h[p].LChild==c)
{
hf.bit[hf.start]=0;
}
else
{
hf.bit[hf.start]=1;
}
--hf.start;
c=p;
p=h[c].parent;
}
for(j=hf.start+1;j<LEN;j++)
{
code[i].bit[j]=hf.bit[j];
}
code[i].start=hf.start+1;
}
}
void printhuffmantree(Huffman h,int leaves)
{
int i;
for(i=0;i<leaves*2-1;i++)
{
printf("weight=%-3.2f",h[i].weight);
printf("parent=%-3d",h[i].parent);
printf("LChild=%-3d",h[i].LChild);
printf("RChild=%-3d\n",h[i].RChild);
}
}
void printhuffcode(HuffCode hcode,char characters[])
{
int i,j;
for(i=0;i<strlen(characters);i++)
{
printf("%c的huffman編碼:",characters[i]);
for(j=hcode[i].start;j<LEN;j++)
{
printf("%d",hcode[i].bit[j]);
}
printf("\n");
}
}
int main(void)
{
Huffman h;
HuffCode hcode;
char characters[]={"abcdef"}; /* 待編碼的字元 */
ElemType weights[]={0.3,0.7,0.4,0.5,0.9,0.1}; /* 字元出現的頻率 */
createHuffmanTree(h,strlen(characters),weights);
printhuffmantree(h,strlen(characters));
huffmancode(h,hcode,sizeof(characters));
printhuffcode(hcode,characters);
system("pause");
return 0;
}
2.第二題 代碼如下，以及使用說明
例如有如下的圖
a->b
/ \
|
c
首先輸入頂點與弧的數目
3 2
提示輸入頂點
abc
輸入弧（弧頭弧尾）
ab
ca
那些插入以及刪除的操作已經放入主函數
顧回車後可以看到進行相關操作後圖的變化
#include<stdio.h>
#include<stdlib.h>
#define MAXVERT 10 // 需要在圖中進行插入操作所以設定一個最大值
#define INFINITE 32767
#define ERROR -1
#define FALSE 0
#define OK 1
typedef int ElemType;
enum maritype{DG,UDG,DN,UDN};
typedef struct
{
char vertex[MAXVERT];
ElemType arc[MAXVERT][MAXVERT];
int ArcNum;
int VertexNum;
}adjacentMatrix;
int locate(adjacentMatrix *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->VertexNum;i++)
{
if(G->vertex[i]==v)
{
k=i;
break;
}
}
return(k);
}
void init(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
G->arc[i][j]=0;
}
}
}
void createDN(adjacentMatrix *G)
{
int i,j,k;
char v1,v2,blank;
printf("請輸入頂點與弧的數目 \n");
scanf("%d%d",&G->VertexNum,&G->ArcNum);
init(G);
printf("請輸入頂點（用字母表示）:\n");
getchar();
for(i=0;i<G->VertexNum;i++)
{
scanf("%c",&G->vertex[i]);
}
getchar();
for(i=0;i<G->ArcNum;i++)
{
printf("請輸入弧%d的弧頭與弧尾",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
G->arc[j][k]=1;
}
}
int InsertVex(adjacentMatrix *G,char v) /* insert vertex */
{
int i;
if(G->VertexNum>MAXVERT-1)
{
return(FALSE);
}
G->vertex[G->VertexNum++]=v;
for(i=0;i<G->VertexNum;i++)
{
G->arc[i][G->VertexNum-1]=G->arc[G->VertexNum-1][i]=0;
}
return(OK);
}
int InsertAar(adjacentMatrix *G,char v,char w) //插入邊
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(FALSE);
}
G->arc[i][j]=1;
return(OK);
}
int DeleteVex(adjacentMatrix *G,char v) //（刪除頂點）
{
int i, k;
k=locate(G,v);
if(k==-1)
{
printf("The vertex has not found\n");
return(FALSE);
}
for(i=k;i<G->VertexNum;i++)
{
G->vertex[i]=G->vertex[i+1];
}
--G->VertexNum;
return(OK);
}
int DeleteArc(adjacentMatrix *G,char v,char w)
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(ERROR);
}
G->arc[i][j]=0;
return(OK);
}
void degree(adjacentMatrix *G)
{
int i, j, odsum, idsum, zero=0;
for(i=0;i<G->VertexNum;i++)
{
odsum=0;
idsum=0;
for(j=0;j<G->VertexNum;j++)
{
odsum+=G->arc[i][j];
idsum+=G->arc[j][i];
}
if(!odsum)
{
++zero;
}
printf("頂點 %c 的出度與入度是",G->vertex[i]);
printf("%3d%3d\n",odsum,idsum);
}
printf("度為0的頂點 %d\n",zero);
}
void print(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
printf("%8c",G->vertex[i]);
}
printf("\n");
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
if(!j)
{
printf("%c",G->vertex[i]);
}
printf("%8d",G->arc[i][j]);
}
printf("\n");
}
}
int main(void)
{
int k;
char v, w;
adjacentMatrix G;
createDN(&G);
print(&G); // 鄰接矩陣列印
degree(&G); // 求所有頂點出度入度 及度為0的點
InsertVex(&G,'f'); // 插入頂點f
InsertAar(&G,'f','c'); // 插入邊 fc
degree(&G); // 觀察插入邊頂點後度的變化
print(&G); // 鄰接矩陣列印
DeleteArc(&G,'f','c'); // 刪除邊 fc
print(&G); // 鄰接矩陣列印 觀察變化
DeleteVex(&G,'a'); // 刪除頂點a
print(&G); // 鄰接矩陣列印 觀察刪除頂點a後變化
system("pause");
return(0);
}
3.使用同上 示例圖也如上所畫 使用方式也基本一直
按你的要求只輸出 頂點的出度入度以及度為0的頂點
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR -1
#define FALSE 0
#define OK 1
typedef char VertexType;
typedef struct ArcNode // 邊表的結構
{
int adjvex; // 與頂點相鄰接的頂點在表頭結點表（圖中）的位置
struct ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode // 表頭結點表的結構
{
VertexType data;
ArcNode *firstarc;
}VertexNode;
typedef struct // 存放圖信息的結構
{
int vexnum, arcnum; // 頂點與弧的數目
VertexNode vertex[MAX_VERTEX_NUM];
}Adjlist;
int locate(Adjlist *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->vexnum;i++)
{
if(G->vertex[i].data==v)
{
k=i;
break;
}
}
return(k);
}
void createDG(Adjlist *G)
{
int i, j, k;
char v1, v2;
ArcNode *s;
printf("輸入頂點與弧的數目 \n");
scanf("%d%d",&G->vexnum,&G->arcnum);
getchar();
printf("請輸入頂點（用字母表示）:");
for(i=0;i<G->vexnum;i++) // 生成表頭結點表
{
scanf("%c",&G->vertex[i].data);
G->vertex[i].firstarc=NULL;
}
getchar();
for(i=0;i<G->arcnum;i++)
{
printf("請輸入第%d條邊的信息 弧尾與弧頭:",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=k;
s->nextarc=G->vertex[j].firstarc;
G->vertex[j].firstarc=s;
}
}
void od(Adjlist *G)
{
int odsum, i;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表頭結點表
{
odsum=0;
p=G->vertex[i].firstarc;
while(p)
{
++odsum;
p=p->nextarc;
}
printf("\n%c的出度是:%d\n ",G->vertex[i].data,odsum);
}
}
void ind(Adjlist *G)
{
int insum, i, j, k;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表頭結點表
{
insum=0;
for(j=0;j<G->vexnum;j++)
{
if(i==j)
{
continue;
}
p=G->vertex[j].firstarc;
while(p)
{
if(p->adjvex==i)
{
++insum;
}
p=p->nextarc;
}
}
printf("\n%c的入度是:%d\n ",G->vertex[i].data,insum);
}
}
int main(void)
{
Adjlist G;
int i;
createDG(&G);
od(&G);
ind(&G);
system("pause");
return(0);
}