关于二叉树的基本操作与输出哈夫曼编码的C语言程序

以下程序除汉字外均为在英文环境中编写，可直接复制到VC编程软件中运行。

#include #include

#include

#include //getch()所需

int num;

typedef struct node //定义二叉树的结构体 {

char data;

struct node *lchild,*rchild;

}BinTNode,*BinTree;

BinTree T;

typedef struct //定义哈夫曼的结构体 {

int weight;

int parent,lchild,rchild; }HTNode,*HuffmanTree;

HuffmanTree p;

typedef char * *HuffmanCode;

void CreateBinTree(BinTree &T) //建树 {

char ch; ch=getch(); if (ch==' ') { }

printf(\"_\"); T=NULL;

}

else { }

printf(\"%c\

T=(BinTNode *)malloc(sizeof(BinTNode)); T->data=ch;

CreateBinTree(T->lchild );

CreateBinTree(T->rchild );

void Preorder(BinTree &T) //先序遍历 { }

void P() //先序遍历的调用 {

system(\"cls\");

printf(\"先序遍历的结果如下：\\n\\n\\n\\n\"); Preorder(T); }

void Inorder(BinTree &T) //中序遍历 { }

void I() //中序遍历的调用 {

if(T)

{

Inorder(T->lchild); printf(\"%c\ Inorder(T->rchild); } if (T) {

printf(\"%c\ Preorder(T->lchild); Preorder(T->rchild); }

system(\"cls\"); printf(\"中序遍历的结果如下：\\n\\n\\n\\n\"); Inorder(T); }

void Postorder(BinTree &T) //后序遍历 {

if(T) { }

Postorder(T->lchild); Postorder(T->rchild); printf(\"%c\

}

void Po() //后序遍历的调用 {

system(\"cls\"); printf(\"后序遍历的结果如下：\\n\\n\\n\\n\"); Postorder(T); }

int Ylen(BinTree &T) //求叶子结点个数 {

if (T) { if(T->lchild==NULL&&T->rchild==NULL)

num++; Ylen(T->lchild); }

int Slen(BinTree &T) //求总结点个数 { if (T)

{

num++;

Slen(T->lchild);

Ylen(T->rchild);

}

return num;

}

Slen(T->rchild);

}

return num;

void l() //将总结点以及叶子结点的数目进行输出 {

system(\"cls\");

num=0;

printf(\"叶子结点的个数为：%d\\n\\n\\n\\n\ }

num=0;

printf(\"总结点的个数为：%d\\n\\n\\n\\n\

void m() //关于二叉树的操作总函数 {

int h;

system(\"cls\");

printf(\"创造一个二叉链表存储的二叉树\\n\");

printf(\"请以先序序列输入所有结点的字符（虚结点用空格字符表示）：\\n\");

CreateBinTree(T); system(\"cls\"); while (1) { }

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) //哈夫曼编码 {

}

printf(\" \\n\\n\\n\\n\"); printf(\"1.先序遍历\\n\");

printf(\"2.中序遍历\\n\"); printf(\"3.后序遍历\\n\");

printf(\"4.统计所见二叉树中叶子结点个数和结点总数\\n\\n\\n\\n\\n\\n\"); scanf(\"%d\switch (h) {

case 1:P();break; case 2:I();break; case 3:Po();break; case 4:l();break; }

printf(\"请输入操作的序号：\");

int i,j,start,f,m1; int c; char *cd;

if(n<=1) return; m1=2*n-1;

HT=(HuffmanTree)malloc((m1+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++w) { p->weight=*w; p->parent=0;

p->lchild=0; p->rchild=0;

}

for(;i<=m1;++i,++p) {

p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

for(i=n+1;i<=m1;++i) {

int min,s1,s2; min=10000;

for(j=1;j<=i-1;j++) {

if (HT[j].parent==0) {

if ((int)HT[j].weight<=(int)min) }

{

min=HT[j].weight; }

s1=j; }

min=100000; for(j=1;j<=i-1;j++) {

if(j!=s1)

{

if((int)HT[j].weight<=(int)min) {

if (HT[j].parent==0)

}

} }

min=HT[j].weight; s2=j;

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;

}

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); 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)); strcpy(HC[i],&cd[start]); } free(cd); }

void OutputHuffman() //哈夫曼编码输出 { int i; int n;

int Q[100];

HuffmanTree HT; HuffmanCode HC; system(\"cls\");

printf(\"请输入您想输入的字符个数：\"); scanf(\"%d\ for(i=0;i{ printf(\"请输入第%d个字符的权值：\\n\ scanf(\"%d\ }

HuffmanCoding(HT,HC,Q,n); for(i=1;i<=n;i++) {

printf(\"\\n\\n哈夫曼的编码分别为:\"); while (*HC[i]) {

printf(\"%c\ HC[i]++; }

}

}

void main() //主函数 {

int i; while (1) {

printf(\"\\n\\n 1.关于二叉树的建立与操作\\n\\n\"); printf(\"\\n\\n 2.实现哈夫曼编码\\n\\n\\n\\n\\n\\n\"); printf(\"请输入您想输入的操作编号：\"); scanf(\"%d\ switch (i) { } } }

case 1:m();break;

case 2:OutputHuffman();break;