以{8，5，3，2，9，11，2}为叶子结点的权值构造哈夫曼树，并求其带权路径长度。

答案是103，附截图

1.struct_tree.h

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

typedef struct tree
{
char data;
int weight;
struct tree *parent;
struct tree *Lchild;
struct tree *Rchild;
}bitnode,*bitree;

typedef struct node
{
char ch;
struct node *next;
}linknode,*linklist;

2.stack.h

typedef struct stack
{
bitree ch;
struct stack *next;
}linkstacknode,*linkstack;

linkstack initstack()
{
linkstack s;
s=(linkstack)malloc(sizeof(linkstacknode));
s->next=NULL;
return s;
}

linkstack clearstack(linkstack s)
{
s->next=NULL;
return s;
}

int isempty(linkstack s)
{
if(s->next==NULL)
return 1;
return 0;
}

int push(linkstack s,bitree ch)
{
linkstacknode *temp;
temp=(linkstacknode *)malloc(sizeof(linkstacknode));
if(temp==NULL)
return 0;
temp->ch=ch;
temp->next=s->next;
s->next=temp;
return 1;
}

int pop(linkstack s,bitree *ch)
{
linkstacknode *temp;
temp=s->next;
if(temp==NULL)
return 0;
s->next=temp->next;
*ch=temp->ch;
free(temp);
return 1;
}

int gettop(linkstack s,bitree *ch)
{
linkstacknode *temp;
temp=s->next;
if(temp==NULL)
return 0;
*ch=temp->ch;
return 1;
}

3.queue.h

typedef struct queue
{
bitree ch;
struct queue *next;
}linkqueuenode;

typedef struct
{
linkqueuenode *front;
linkqueuenode *rear;
}linkqueue;

linkqueue* initqueue()
{
linkqueue *q;
q=(linkqueue *)malloc(sizeof(linkqueue));
q->front=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(q->front!=NULL)
{
q->rear=q->front;
q->front->next=NULL;
return q;
}
return NULL;
}

int enterqueue(linkqueue *q,bitree ch)
{
linkqueuenode *newnode;
newnode=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(newnode!=NULL)
{
newnode->ch=ch;
newnode->next=NULL;
q->rear->next=newnode;
q->rear=newnode;
return 1;
}
return 0;
}

int deletequeue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
q->front->next=temp->next;
if(q->rear==temp)
q->rear=q->front;
*ch=temp->ch;
free(temp);
return 1;
}

int getqueue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
*ch=temp->ch;
return 1;
}

4.主程序

typedef struct queue
{
bitree ch;
struct queue *next;
}linkqueuenode;

typedef struct
{
linkqueuenode *front;
linkqueuenode *rear;
}linkqueue;

linkqueue* initqueue()
{
linkqueue *q;
q=(linkqueue *)malloc(sizeof(linkqueue));
q->front=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(q->front!=NULL)
{
q->rear=q->front;
q->front->next=NULL;
return q;
}
return NULL;
}

int enterqueue(linkqueue *q,bitree ch)
{
linkqueuenode *newnode;
newnode=(linkqueuenode *)malloc(sizeof(linkqueuenode));
if(newnode!=NULL)
{
newnode->ch=ch;
newnode->next=NULL;
q->rear->next=newnode;
q->rear=newnode;
return 1;
}
return 0;
}

int deletequeue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
q->front->next=temp->next;
if(q->rear==temp)
q->rear=q->front;
*ch=temp->ch;
free(temp);
return 1;
}

int getqueue(linkqueue *q,bitree *ch)
{
linkqueuenode *temp;
if(q->front==q->rear)
return 0;
temp=q->front->next;
*ch=temp->ch;
return 1;
}

（2+2）*5+3*4+5*3+（11+8+9）*2=20+12+15+56=103