《关于二叉树的基本操作与输出哈夫曼编码的C语言程序》由会员分享，可在线阅读，更多相关《关于二叉树的基本操作与输出哈夫曼编码的C语言程序（7页珍藏版）》请在金锄头文库上搜索。
1、注：本程序主要是关于二叉树的一些基本操作，包括前序遍历，中序遍历，后序遍历以及求出总结点以及叶子结点的数目（本程序在输入时是默认以先序序列输入各个结点的数值。如果是其它方式，则三个遍历程序会有略微变化）以及哈夫曼编码的输出。以下程序除汉字外均为在英文环境中编写，可直接复制到 VC 编程软件中运行。#include #include #include #include /getch()所需int num;typedef struct node /定义二叉树的结构体char data;struct node *lchild,*rchild;BinTNode,*BinTree;BinTree T;t
2、ypedef 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;elseprintf(%c,ch);T=(BinTNode *)malloc(sizeof(BinTNode);T-data=ch;CreateBinTree(T-lchild );CreateBi
3、nTree(T-rchild );void Preorder(BinTree &T) /先序遍历if (T)printf(%c,T-data);Preorder(T-lchild);Preorder(T-rchild);void P() /先序遍历的调用system(cls);printf(先序遍历的结果如下：nnnn);Preorder(T);void Inorder(BinTree &T) /中序遍历if(T)Inorder(T-lchild);printf(%c,T-data);Inorder(T-rchild);void I() /中序遍历的调用system(cls);printf(中
4、序遍历的结果如下：nnnn);Inorder(T);void Postorder(BinTree &T) /后序遍历if(T)Postorder(T-lchild);Postorder(T-rchild);printf(%c,T-data);void Po() /后序遍历的调用system(cls);printf(后序遍历的结果如下：nnnn);Postorder(T);int Ylen(BinTree &T) /求叶子结点个数if (T)if(T-lchild=NULL&T-rchild=NULL)num+;Ylen(T-lchild);Ylen(T-rchild);return num;i
5、nt Slen(BinTree &T) /求总结点个数if (T)num+;Slen(T-lchild);Slen(T-rchild);return num;void l() /将总结点以及叶子结点的数目进行输出system(cls);num=0;printf(叶子结点的个数为：%dnnnn,Ylen(T);num=0;printf(总结点的个数为：%dnnnn,Slen(T);void m() /关于二叉树的操作总函数int h;system(cls);printf(创造一个二叉链表存储的二叉树n);printf(请以先序序列输入所有结点的字符（虚结点用空格字符表示）：n);CreateBi
6、nTree(T);system(cls);while (1)printf( nnnn);printf(1.先序遍历n);printf(2.中序遍历n);printf(3.后序遍历n);printf(4.统计所见二叉树中叶子结点个数和结点总数nnnnnn);printf(请输入操作的序号：);scanf(%d,switch (h)case 1:P();break;case 2:I();break;case 3:Po();break;case 4:l();break;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) /
7、哈夫曼编码int i,j,start,f,m1;int c;char *cd;if(nweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=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 (HTj.parent=0)if (int)HTj.weight=(int)min)min=HTj.weight;s1=j;min=100000;for(j=1;j=i-1;j+)if(j!=s1)if (H
8、Tj.parent=0)if(int)HTj.weight=(int)min)min=HTj.weight;s2=j;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.paren
9、t)if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,free(cd);void OutputHuffman() /哈夫曼编码输出int i;int n;int Q100;HuffmanTree HT;HuffmanCode HC;system(cls);printf(请输入您想输入的字符个数：);scanf(%d,for(i=0;in;i+) printf(请输入第%d 个字符的权值：n,i+1);scanf(%d, HuffmanCoding(HT,HC,Q,n);for(i=1;i=n;i+)printf(nn 哈夫曼的编码分别为:);while (*HCi)printf(%c,*HCi);HCi+;void main() /主函数int i;while (1)printf(nn 1.关于二叉树的建立与操作nn);printf(nn 2.实现哈夫曼编码nnnnnn);printf(请输入您想输入的操作编号：);scanf(%d,switch (i)case 1:m();break;case 2:OutputHuffman();break;
