{
if(T!=NULL) {
printf(\ PreOrder(T->lchild); PreOrder(T->rchild); } }
void InOrder(BiTree T)//中序 {
if(T!=NULL) {
InOrder(T->lchild); printf(\ InOrder(T->rchild); } }
void PostOrder(BiTree T)//后序 {
if(T!=NULL) {
PostOrder(T->lchild); PostOrder(T->rchild); printf(\ } }
void main()//主函数 {
BiTree Ta;
Ta=CreateBiTree(); printf(\先序遍历:\ printf(\ PreOrder(Ta); printf(\
printf(\中序遍历:\ printf(\ InOrder(Ta); printf(\
printf(\后序遍历:\ printf(\ PostOrder(Ta); }
实验七 二叉树的应用程序设计
实验预备知识：
2．掌握二叉树的创建和遍历算法。 3．掌握霍夫曼编码原理。
一、实验目的
1．进一步掌握二叉树的存储结构和相应算法。 2．掌握霍夫曼树树的创建和霍夫曼编码。
二、实验环境
⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；
三、实验要求
1．要求采用二叉链表作为存贮结构，完成霍夫曼树的创建。 2．输出对应数据的霍夫曼编码，并求出平均编码长度。
四、实验内容
1．在自己的U盘的“姓名+学号”文件夹中创建“实验7”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。
2．现在某电报公司假设有10字符进行编码，这10个字符的使用频率如下表所示，请创建霍夫曼树。
A 19 B 18 C 16 D 14 E 12 F 8 G 6 H 4 I 2 J 1 3.编写函数求出A~J的霍夫曼编码。
五、报告要求
1．认真书写实验报告，字迹清晰，格式规范。报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求、实验原理（系统主要工作流程图）。
2．报告中应书写主要源程序，且源程序中要有注释。 3．报告最后包含实验总结和体会。
4．如未调试通过或结果不正确，试分析原因，利用课余时间独立完成，完成后方可书写实验报告。
#include
typedef char* HuffmanCode; typedef struct {char data;
unsigned int weight ;
unsigned int parent, LChild,RChild ; }HTNode, * HuffmanTree; //选出权值最小的两个//
void select(HuffmanTree *ht,int n, int *s1, int *s2) {int i;
int min1=0,min2=0;
(*ht)[min1].weight=(*ht)[min2].weight=101; for(i=1;i<=n;i++)
{if((*ht)[i].weight < (*ht)[min1].weight&&(*ht)[i].parent == 0) min1=i;} for(i=1;i<=n;i++)
{if((*ht)[i].weight < (*ht)[min2].weight&&(*ht)[i].parent == 0&&min1!=i) min2=i;}
*s1=min2;*s2=min1; }
void CrtHuffmanTree(HuffmanTree *ht , int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i,w;
int s1,s2;char c; m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ printf(\输入字符及权重:\\n\ for(i=1;i<=n;i++)
{/*1-n号放叶子结点，初始化*/ fflush(stdin);
scanf(\ (*ht)[i].data = c; (*ht)[i].weight = w; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; }
for(i=n+1;i<=m;i++) {
(*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0;
} /*非叶子结点初始化*/
/*创建非叶子结点,建哈夫曼树*/ for(i=n+1;i<=m;i++)
{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*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; } }
//中序输出哈夫曼树叶子节点//
void outputHuffman(HuffmanTree HT, int m) { if(m!=0) {
outputHuffman(HT,HT[m].LChild);
if(!HT[m].LChild&&!HT[m].RChild)printf(\ outputHuffman(HT,HT[m].RChild); } }
/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) {
char *cd; int i;
unsigned int c; int start; int p;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd[n-1]='\\0'; /*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/ {
start=n-1; /*初始化编码起始指针*/
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/ if( (*ht)[p].LChild == c)
cd[--start]='0'; /*左分支标0*/ else
cd[--start]='1'; /*右分支标1*/
hc[i]=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/ strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1;i<=n;i++)
printf(\编码为%s\\n\}
// 主函数// void main() {
HuffmanTree HT; HuffmanCode HC; int n; int m;
printf(\输入叶子节点的个数:\ scanf(\
CrtHuffmanTree(&HT,n);
m = 2*n-1;printf(\中序输出哈夫曼树叶子节点：\\n\ outputHuffman(HT,m); printf(\
CrtHuffmanCode(&HT,&HC,n); }
实验八 图的建立及遍历操作
实验预备知识：
1．掌握图的存储结构和访问。 2．掌握图的遍历及相关操作原理。
一、实验目的
1．掌握图的存储结构和相关操作。
2．能够熟练用计算机来表示图和进行图处理。
二、实验环境
⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；
三、实验要求
1．要求对于给定的图分别用邻接矩阵和邻接表来存储。 2．对于存储好的图进行深度和广度优先遍历。 3．完成图的各种操作。