软基第四次上机实验报告

7/7软基第四次上机实验报告EX4.1实验流程1）二叉树结点类型定义为：typedefstructbnode{intdata;structbnode*lc,*rc;}bnode_type;2）编写二叉树的创建函数，可以是排序二叉树的创建思路（见教材），或者以先序遍历为框架。3）编写中序遍历函数；4）编写后序遍历函数；5）编写先序遍历函数；6）编写main()函数，先调用create函数，建立一颗二叉排序树；然后分别调用中序、后序、先序遍历函数，将二叉树的先序、中序和后序遍历序列输出到屏幕上。二、程序代码 #include<stdio.h>#include<malloc.h>typedefstructbnode{ intdata; structbnode*lc,*rc;}bnode;voidinorder(bnode*t){ if(t==NULL) { printf("thetreeisnull\n"); return; } else { if(t->lc!=NULL) inorder(t->lc); printf("%d\n",t->data); if(t->rc!=NULL)inorder(t->rc); }}voidpostorder(bnode*t){ if(t==NULL) { printf("thetreeisnull!\n"); return; } else { if(t->lc!=NULL) postorder(t->lc); if(t->rc!=NULL) postorder(t->rc); printf("%d\n",t->data); }}voidpreorder(bnode*t){ if(t==NULL) { printf("thetreeisnull!\n"); return; } else { printf("%d\n",t->data); if(t->lc!=NULL) preorder(t->lc); if(t->rc!=NULL) preorder(t->rc); }}voidcreate(bnode**t){ intx,n,i; bnode*p,*q;*t=NULL; printf("输入数据元素的个数:\n"); scanf("%d",&n); printf("分别输入这些元素:\n"); for(i=0;i<n;i++) { scanf("%d",&x); p=(bnode*)malloc(sizeof(bnode)); p->lc=NULL; p->rc=NULL; p->data=x; if(*t==NULL) *t=p; else { q=*t; while(q!=NULL) { if(q->data>x) { if(q->lc!=NULL) q=q->lc; else { q->lc=p; q=NULL; } } else { if(q->rc!=NULL)q=q->rc; else { q->rc=p; q=NULL; } } } } }}voidmain(){ bnode**a; a=(bnode**)malloc(sizeof(bnode*)); create(a); printf("此树的中序遍历:\n"); inorder(*a); printf("此树的后序遍历:\n"); postorder(*a); printf("此树的先序遍历:\n"); preorder(*a);}测试数据输入：输入数据元素的个数：8输入的数据：569843610输出：中序遍历：345668910后序遍历：346810965先序遍历;:543698610上机遇到的问题：调用函数出错；解决办法:问同学实际运行结果：如图所示 小结掌握不够，还的努力EX4.2程序流程输入一组数（权值），编写算法建立哈夫曼树，输出每个权值对应的二进制编码。二、程序代码 #include<stdio.h>#include<iostream.h>#include<iomanip.h>constintn=8;constintm=2*n-1;structtree{ floatweight; intparent; intlch,rch;};structcodetype{ intbits[n+1]; intstart; charch;};treehftree[m+1];codetypecode[n+1];voidcreathuffmantree()//建立哈夫曼树{ inti,j,p1,p2; floats1,s2; for(i=1;i<=m;i++) { hftree[i].parent=0; hftree[i].lch=0; hftree[i].rch=0; hftree[i].weight=0; } cout<<"请输入"<<n<<"个权值"<<endl; for(i=1;i<=n;i++) cin>>hftree[i].weight; for(i=n+1;i<=m;i++) { p1=p2=0; s1=s2=32767; for(j=1;j<=i-1;j++) if(hftree[j].parent==0) if(hftree[j].weight<s1) { s2=s1; s1=hftree[j].weight; p2=p1; p1=j; } elseif(hftree[j].weight<s2) {s2=hftree[j].weight;p2=j;} hftree[p1].parent=i; hftree[p2].parent=i; hftree[i].lch=p1; hftree[i].rch=p2; hftree[i].weight=hftree[p1].weight+hftree[p2].weight; }}voidhuffcode()//哈夫曼编码{ codetypecd; intc,p,i; for(i=1;i<=n;i++) { cd.start=n+1; cd.ch=96+i;//第一个树叶对应字母a，其余依此类推 c=i; p=hftree[i].parent; while(p!=0) { cd.start--; if(hftree[p].lch==c) cd.bits[cd.start]=0; else cd.bits[cd.start]=1; c=p; p=hftree[p].parent; } code[i]=cd; } for(i=1;i<=n;i++) { cout<<"字符"<<code[i].ch<<"的权值为："<<hftree[i].weight<<setw(5)<<"编码为："; for(intj=code[i].start;j<=n;j++) cout<<code[i].bits[j]<<""; cout<<endl; }}voidtrancode()//哈夫曼译码{ inti=m; charb; cout<<"请输入一串二进制编码（0、1以外的数结束）"<<endl; cin>>b; while((b=='0')||(b=='1')) { if(b=='0') i=hftree[i].lch; else i=hftree[i].rch; if(hftree[i].lch==0) { cout<<code[i].