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

《2022年2022年关于二叉树的基本操作与输出哈夫曼编码的C语言程序 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年关于二叉树的基本操作与输出哈夫曼编码的C语言程序 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、注：本程序主要是关于二叉树的一些基本操作，包括前序遍历， 中序遍历， 后序遍历以及求出总结点以及叶子结点的数目（本程序在输入时是默认以先序序列输入各个结点的数值。 如果是其它方式， 则三个遍历程序会有略微变化）以及哈夫曼编码的输出。以下程序除汉字外均为在英文环境中编写，可直接复制到VC 编程软件中运行。#include #include #include #include /getch()所需int num; typedef struct node /定义二叉树的结构体 char data; struct node *lchild,*rchild; BinTNode,*BinTree; Bin

2、Tree 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

3、第 1 页，共 7 页 - - - - - - - - - else printf(%c,ch); T=(BinTNode *)malloc(sizeof(BinTNode); T-data=ch; CreateBinTree(T-lchild ); CreateBinTree(T-rchild ); void Preorder(BinTree &T) /先序遍历 if (T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); void P() /先序遍历的调用 system(cls); printf( 先序遍历的结果如下：n

4、nnn); Preorder(T); void Inorder(BinTree &T) /中序遍历 if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); void I() /中序遍历的调用 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - system(cls); printf( 中序遍历的结果如下：nnnn); Inorder(T); void Postor

5、der(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; int Slen(BinTree &T)

6、/求总结点个数 if (T) num+; Slen(T-lchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - Slen(T-rchild); return num; void l() /将总结点以及叶子结点的数目进行输出 system(cls); num=0; printf( 叶子结点的个数为：%dnnnn,Ylen(T); num=0; printf( 总结点的个数为：%dnnnn,Slen(T); void m(

7、) /关于二叉树的操作总函数 int h; system(cls); printf( 创造一个二叉链表存储的二叉树n); printf( 请以先序序列输入所有结点的字符（虚结点用空格字符表示）：n); CreateBinTree(T); system(cls); while (1) printf( nnnn); printf(1. 先序遍历 n); printf(2. 中序遍历 n); printf(3. 后序遍历 n); printf(4. 统计所见二叉树中叶子结点个数和结点总数nnnnnn); printf( 请输入操作的序号：); scanf(%d,&h); switch (h) cas

8、e 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) /哈夫曼编码 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - int i,j,start,f,m1; int c; char *cd; if(n=1) retur

9、n; m1=2*n-1; HT=(HuffmanTree)malloc(m1+1)*sizeof(HTNode); for(p=HT+1,i=1;iweight=*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; s

10、1=j; min=100000; for(j=1;j=i-1;j+) if(j!=s1) if (HTj.parent=0) if(int)HTj.weight=(int)min) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - min=HTj.weight; s2=j; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.wei

11、ght+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.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); void

12、OutputHuffman() /哈夫曼编码输出 int i; int n; int Q100; HuffmanTree HT; HuffmanCode HC; system(cls); printf( 请输入您想输入的字符个数：); scanf(%d,&n); for(i=0;in;i+) printf( 请输入第 %d 个字符的权值：n,i+1); scanf(%d,&Qi); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - -

13、 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,&i); switch (i) case 1:m();break; case 2:OutputHuffman();break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -