电子科技大学通信与信息工程学院标准实验报告（实验）课程名称软件技术基础实验电子科技大学教务处制表电子科技大学实验报告一、实验室名称：校公共机房二、实验项目名称：二叉树和哈夫曼树三、实验学时：4学时四、实验原理：使用VS2010等C语言集成开发环境（IDE），在微型计算机上对程序进行编辑、编译、连接与运行。

通过上机练习掌握二叉树的建立、插入删除，遍历等方法和过程，掌握递归函数在二叉树建立，遍历中的应用，掌握哈夫曼树的最小路径和建立过程。

五、实验目的：1.熟练二叉树和哈夫曼树的概念和基本操作方法。

2.掌握课程平台使用方法。

六、实验内容：上机完成所有函数，编程实验，调试运行程序并完成报告。

七、实验器材（设备、元器件）：硬件要求：普通pc机，1G内存，100G硬盘空间即可。

软件要求：Windows 7，包括C编译器的IDE。

八、实验步骤、实验编程与运行结果：下面建立该二叉树并展示输出结果：#include<stdio.h>#include<stdlib.h>typedef struct bnode{int data;struct bnode *lc,*rc;};struct bnode* create(){struct bnode *tree=NULL;char ch;ch=getchar();if(ch=='_')tree=NULL;else{tree=(struct bnode *)malloc(sizeof(struct bnode));tree->data=ch;tree->lc=create();tree->rc=create();}return tree;}//先序遍历（根左右）--递归int preorder(struct bnode *root){putchar(root->data);if(root->lc!=NULL)preorder(root->lc);if(root->rc!=NULL)preorder(root->rc);}//中序遍历--递归int inorder(struct bnode *root){if(root->lc!=NULL)inorder(root->lc);putchar(root->data);if(root->rc!=NULL)inorder(root->rc);}//后序遍历--递归int postorder(struct bnode *root){if(root->lc!=NULL)postorder(root->lc);if(root->rc!=NULL)postorder(root->rc);putchar(root->data);}int main(){struct bnode *root=NULL;printf("先序建立二叉树，输入变量: (下划线为NULL):");root=create(); //输入(ABC DE G F )printf("先序遍历输出：");preorder(root);printf("\n");printf("中序遍历输出：");inorder(root);printf("\n");printf("后序遍历输出：");postorder(root);printf("\n");}下面建立该二叉树并展示输出结果：#include<stdio.h>#include<stdlib.h>struct hftree{int data;struct hftree *left;struct hftree *right;};struct hftree *CreateHuffman(int a[], int n){int i, j;struct hftree *b[100], *q;//假设哈弗曼书最大为100个节点for (i = 0; i < n; i++) //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点{b[i]=(struct hftree*)malloc(sizeof(struct hftree));b[i]->data=a[i];b[i]->left=NULL;b[i]->right=NULL;}for (i = 1; i < n; i++)//进行n-1 次循环建立哈夫曼树{//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标int k1 = -1, k2;for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树，k2指向第二棵{if (b[j] != NULL && k1 == -1){k1 = j;continue;}if (b[j] != NULL){k2 = j;break;}}for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小{if (b[j] != NULL){if (b[j]->data < b[k1]->data){k2 = k1;k1 = j;}else if (b[j]->data < b[k2]->data)k2 = j;}}//由最小权值树和次最小权值树建立一棵新树，q指向树根结点q = (struct hftree*)malloc(sizeof(struct hftree));q->data = b[k1]->data + b[k2]->data;q->left = b[k1];q->right = b[k2];b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置b[k2] = NULL;//k2位置为空}free(b); //删除动态建立的数组breturn q; //返回整个哈夫曼树的树根指针}//求哈夫曼树的带权路径长度int WeightPathLength(struct hftree* T, int len)//len初始为0{if (T == NULL) //空树返回0return 0;else{if (T->left == NULL && T->right == NULL)//访问到叶子结点return T->data * len;else //访问到非叶子结点，进行递归调用，返回左右子树的带权路径长度之和，len 递增return WeightPathLength(T->left,len+1)+WeightPathLength(T->right,len+1);}}//哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）void HuffManCoding(struct hftree* T, int len)//len初始值为0{static int a[10];//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一if (T != NULL)//访问到叶子结点时输出其保存在数组a中的0和1序列编码{if (T->left == NULL && T->right == NULL){int i;printf("结点权值为%d的编码：", T->data);for (i = 0; i < len; i++)printf("%d", a[i]);printf("\n");}else{a[len] = 0;HuffManCoding(T->left, len + 1);a[len] = 1;HuffManCoding(T->right, len + 1);}}}int main(){int n, i;int a[100];struct hftree* t;printf("从键盘输入待构造的哈夫曼树中带权叶子结点数n：");scanf("%d", &n);printf("从键盘输入%d个整数作为权值：", n);for (i = 0; i < n; i++)scanf(" %d", &a[i]);t = CreateHuffman(a, n);printf("哈夫曼树的带权路径长度：");printf("%d\n", WeightPathLength(t, 0));printf("各个数据的哈夫曼编码：\n");HuffManCoding(t, 0);}。