数据结构二叉树遍历实验报告.doc

《数据结构二叉树遍历实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构二叉树遍历实验报告.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-!问题一： 二叉树遍历1. 问题描述设输入该二叉树的前序序列为： ABC#DE#G#F#HI#J#K#（#代表空子树）请编程完成下列任务：1 请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；2 按层次遍历的方法来输出该二叉树按层次遍历的序列；3 求该二叉树的高度。2. 设计描述（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和

2、LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。（3）计算二叉树高度也是

3、利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。3源程序12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #include #include #define ElemType charstruct BTreeNode ElemType

4、data;struct BTreeNode* left;struct BTreeNode* right;void CreateBTree(struct BTreeNode* T)char ch;scanf_s(n%c, &ch);if (ch = #) *T = NULL;else (*T) = malloc(sizeof(struct BTreeNode);(*T)-data = ch;CreateBTree(&(*T)-left);CreateBTree(&(*T)-right); void Preorder(struct BTreeNode* T)if (T != NULL) print

5、f(%c , T-data);Preorder(T-left);Preorder(T-right);void Inorder(struct BTreeNode* T)if (T != NULL) Inorder(T-left);printf(%c , T-data);Inorder(T-right);void Postorder(struct BTreeNode* T)if (T != NULL) Postorder(T-left);Postorder(T-right);printf(%c , T-data);void Levelorder(struct BTreeNode* BT)struc

6、t BTreeNode* p;struct BTreeNode* q30;int front=0,rear=0;if(BT!=NULL) rear=(rear+1)% 30;qrear=BT;while(front!=rear) front=(front+1)% 30;p=qfront;printf(%c ,p-data);if(p-left!=NULL) rear=(rear+1)% 30;qrear=p-left;if(p-right!=NULL) rear=(rear+1)% 30;qrear=p-right;int getHeight(struct BTreeNode* T)int l

7、h,rh;if (T = NULL) return 0;lh = getHeight(T-left);rh = getHeight(T-right);return lhrh ? lh + 1 : rh + 1;void main(void)struct BTreeNode* T;CreateBTree(&T);printf(前序序列：n);Preorder(T);printf(n);printf(中序序列：n);Inorder(T);printf(n);printf(后序序列：n);Postorder(T);printf(n);printf(层次遍历序列：n);Levelorder(T);pr

8、intf(n);printf(二叉树高度：%dn, getHeight(T);4.运行结果问题二： 哈夫曼编码、译码系统1. 问题描述对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件（选做）。v 从文件中读入给定的一篇英文短文（文件为ASCII编码，扩展名为txt）；v 统计并输出不同字符在文章中出现的频率（空格、换行、标点等不按字符处理）；v 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；v 将文本文件利用哈夫曼树进行编码，存储成编码文件（编码文件后缀名.huf）v 进行译码，将huf文件译码为ASCII编码的txt文件，

9、与原txt文件进行比较。（选做）2. 设计描述（1） 统计并输出不同字符在文章中出现的频率，通过建立两个数组chs和chs_freq来实现，chs存储文件中出现过的字符，chs_freq（初始化为全0）存储对应字符在文件中出现的频数，当扫描一个字符时，先与chs中已有字符进行比较，若数组中存在该字符，则将该字符对应频数加1，否则则将该字符加入数组，并频数加1。（2） 根据字符频率构造哈夫曼树，即将chs_freq数组作为权值数组，建立哈夫曼树，为了方便后续操作，为结构体BtreeNode添加一个新的成员变量symbol，建立二叉树时用以存储对应权值的字符。（3） 通过最优二叉树（哈夫曼树）输出

10、每个字符的哈夫曼编码，是利用递归实现的，访问非叶子节点时，分别向左右子树递归调用，并将分支上的01编码保存到数组a对应元素中，向下一层len+。访问到非叶子节点时输出其保存在数组中的编码序列，并将其保存至哈夫曼编码文件orde.code。（4） 将文本文件利用哈夫曼树进行编码：每从文本文件中读取一个字符，则在哈夫曼编码文件order.code查找该字符，查找到后将该字符对应哈夫曼编码写入编码后文件order.huf。并将order.code文件指针重新指向开头，准备对下一个字符进行操作。3源程序12345678910111213141516171819202122232425262728293

11、0313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129#include #include typedef int ElemType;struct BTreeNode ElemType data;s

12、truct BTreeNode* left;struct BTreeNode* right;char symbol;void CountChar(FILE *fp,char* chs,int* ch_freq) int num = 0;int i,tmp;char ch = fgetc(fp);while (ch != EOF)if (ch64 & ch96 & ch123) for (tmp = 0; tmp = num; tmp+)if (ch = chstmp) ch_freqtmp+; break; if (tmp = num) chsnum = ch; ch_freqnum+; nu

13、m+; break; ch = fgetc(fp);chsnum=0;for (i = 0; i num; i+) printf(%c %dn, chsi, ch_freqi);struct BTreeNode* CreateHuffman(ElemType a, int n,char ss) int i, j;struct BTreeNode *b, *q;q = malloc(sizeof(struct BTreeNode);b = malloc(n*sizeof(struct BTreeNode*);for (i = 0; i data = ai; bi-left = bi-right

14、= NULL;bi-symbol = ssi;for (i = 1; i n; i+) int k1 = -1, k2;for (j = 0; j n; j+) if (bj != NULL &k1 = -1) k1 = j; continue; if (bj != NULL) k2 = j; break; for (j = k2; j data data) k2 = k1; k1 = j; else if (bj-data data) k2 = j;q = malloc(sizeof(struct BTreeNode);q-data = bk1-data + bk2-data;q-left

15、= bk1; q-right = bk2;bk1 = q; bk2 = NULL;free(b);return q;void HuffCoding(struct BTreeNode* FBT, int len) static int a50;char tmp;FILE *fp;int i;if(len = 0) fp=fopen(order.code,w);if(fp=fopen(order.code,a) = NULL) printf(文件打开失败！n);exit(1);if (FBT != NULL) if (FBT-left = NULL & FBT-right = NULL) prin

16、tf(%c霍夫曼编码为：, FBT-symbol);fputc(FBT-symbol,fp);fputc(t,fp);for (i = 0; i left, len + 1);alen = 1; HuffCoding(FBT-right, len + 1);fclose(fp);void TransCode(FILE *src) FILE *fp1,*fp2;char ch1,ch2;if(fp1=fopen(order.code,r) = NULL) printf(文件打开失败！n);exit(1);if(fp2=fopen(order.huf,w) = NULL) printf(文件打开失

17、败！n);exit(1);fseek(src,0L,SEEK_SET);ch1 = fgetc(src);ch2 = fgetc(fp1);while (ch1 != EOF)if (ch164 & ch196 & ch1123) while(ch2 != EOF) if(ch2 = ch1)fgetc(fp1);ch2=fgetc(fp1);while(ch2!=n)fputc(ch2,fp2);ch2=fgetc(fp1); fputc(t,fp2);break;ch2 = fgetc(fp1);if(ch2 = EOF) printf(未找到对应编码!n);rewind(fp1);ch2

18、 = fgetc(fp1);ch1 = fgetc(src);fclose(fp1);fclose(fp2);void main(void)char chs100;int ch_freq100 = 0;struct BTreeNode* T;FILE *fp;if(fp=fopen(order.txt,r) = NULL) printf(文件打开失败！n);exit(1);CountChar(fp,chs,ch_freq);T = CreateHuffman(ch_freq,strlen(chs),chs);HuffCoding(T,0);TransCode(fp);fclose(fp);4.运行结果