问题一：二叉树遍历1.问题描述设输入该二叉树的前序序列为：ABC##DE#G##F##HI##J#K##（#代表空子树）请编程完成下列任务：⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；⑵按层次遍历的方法来输出该二叉树按层次遍历的序列；⑶求该二叉树的高度。

2.设计描述（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。

二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。

根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。

研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。

采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。

（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。

遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。

（3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。

3．源程序1 2 3 4 5 6 7 8 91011121314 #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define ElemType charstruct BTreeNode {ElemType data;struct BTreeNode* left;struct BTreeNode* right;};void CreateBTree(struct BTreeNode** T) {char ch;scanf_s("\n%c", &ch);if (ch == '#') *T = NULL;15161718192021222324252627282930313233343536else {(*T) = malloc(sizeof(struct BTreeNode));(*T)->data = ch;CreateBTree(&((*T)->left));CreateBTree(&((*T)->right));}}void Preorder(struct BTreeNode* T){if (T != NULL) {printf("%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);}37383940414243444546474849505152535455565758 }void Postorder(struct BTreeNode* T) {if (T != NULL) {Postorder(T->left);Postorder(T->right);printf("%c ", T->data);}}void Levelorder(struct BTreeNode* BT) {struct BTreeNode* p;struct BTreeNode* q[30];int front=0,rear=0;if(BT!=NULL) {rear=(rear+1)% 30;q[rear]=BT;}while(front!=rear) {front=(front+1)% 30;p=q[front];printf("%c ",p->data);59606162636465666768697071727374757677787980if(p->left!=NULL) {rear=(rear+1)% 30;q[rear]=p->left;}if(p->right!=NULL) {rear=(rear+1)% 30;q[rear]=p->right;}}}int getHeight(struct BTreeNode* T) {int lh,rh;if (T == NULL) return 0;lh = getHeight(T->left);rh = getHeight(T->right);return lh>rh ? lh + 1 : rh + 1; }void main(void){struct BTreeNode* T;CreateBTree(&T);8182838485868788899091929394printf("前序序列：\n");Preorder(T);printf("\n");printf("中序序列：\n");Inorder(T);printf("\n");printf("后序序列：\n");Postorder(T);printf("\n");printf("层次遍历序列：\n");Levelorder(T);printf("\n");printf("二叉树高度：%d\n", getHeight(T)); }4.运行结果问题二：哈夫曼编码、译码系统1.问题描述对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件（选做）。

❖从文件中读入给定的一篇英文短文（文件为ASCII编码，扩展名为txt）；❖统计并输出不同字符在文章中出现的频率（空格、换行、标点等不按字符处理）；❖根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；❖将文本文件利用哈夫曼树进行编码，存储成编码文件（编码文件后缀名.huf）❖进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。

（选做）2.设计描述（1）统计并输出不同字符在文章中出现的频率，通过建立两个数组chs和chs_freq来实现，chs存储文件中出现过的字符，chs_freq（初始化为全0）存储对应字符在文件中出现的频数，当扫描一个字符时，先与chs中已有字符进行比较，若数组中存在该字符，则将该字符对应频数加1，否则则将该字符加入数组，并频数加1。

（2）根据字符频率构造哈夫曼树，即将chs_freq数组作为权值数组，建立哈夫曼树，为了方便后续操作，为结构体BtreeNode添加一个新的成员变量symbol，建立二叉树时用以存储对应权值的字符。

（3）通过最优二叉树（哈夫曼树）输出每个字符的哈夫曼编码，是利用递归实现的，访问非叶子节点时，分别向左右子树递归调用，并将分支上的01编码保存到数组a对应元素中，向下一层len++。

访问到非叶子节点时输出其保存在数组中的编码序列，并将其保存至哈夫曼编码文件orde.code。

（4）将文本文件利用哈夫曼树进行编码：每从文本文件中读取一个字符，则在哈夫曼编码文件order.code查找该字符，查找到后将该字符对应哈夫曼编码写入编码后文件order.huf。

并将order.code文件指针重新指向开头，准备对下一个字符进行操作。

3．源程序1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334 #include <stdio.h>#include <stdlib.h>typedef int ElemType;struct BTreeNode {ElemType data;struct 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 ((ch>64 && ch<91)||(ch>96 && ch<123)) {for (tmp = 0; tmp <= num; tmp++){if (ch == chs[tmp]) { ch_freq[tmp]++; break; }if (tmp == num) { chs[num] = ch; ch_freq[num]++; num++; break; }}}ch = fgetc(fp);}chs[num]='\0';for (i = 0; i < num; i++) printf("%c %d\n", chs[i], ch_freq[i]);}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 < n; i++) {3536373839404142434445464748495051525354555657585960616263646566676869707172737475767778b[i] = malloc(sizeof(struct BTreeNode));b[i]->data = a[i]; b[i]->left = b[i]->right = NULL;b[i]->symbol = ss[i];}for (i = 1; i < n; i++) {int k1 = -1, k2;for (j = 0; j < n; j++) {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 = malloc(sizeof(struct BTreeNode));q->data = b[k1]->data + b[k2]->data;q->left = b[k1]; q->right = b[k2];b[k1] = q; b[k2] = NULL;}free(b);return q;};void HuffCoding(struct BTreeNode* FBT, int len) {static int a[50];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) {printf("%c霍夫曼编码为：", FBT->symbol);fputc(FBT->symbol,fp);fputc('\t',fp);for (i = 0; i < len; i++) {printf("%d", a[i]);tmp=a[i]+48;fputc(tmp,fp);}printf("\n");fputc('\n',fp);}else {a[len] = 0; HuffCoding(FBT->left, len + 1);798081828384858687888990919293949596979899 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122a[len] = 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("文件打开失败！\n");exit(1);} fseek(src,0L,SEEK_SET);ch1 = fgetc(src);ch2 = fgetc(fp1);while (ch1 != EOF){if ((ch1>64 && ch1<91)||(ch1>96 && ch1<123)) {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 = fgetc(fp1);}ch1 = fgetc(src);}fclose(fp1);fclose(fp2);}void main(void){char chs[100];int ch_freq[100] = {0};struct BTreeNode* T;123 124 125 126 127 128 129FILE *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.运行结果。