数据结构实验报告三

1、甘肃政法学院本科生实验报告（）姓名:学院:专业:班级:实验课程名称:实验日期:指导教师及职称:实验成绩:开课时间： 2013-2014学年 第二学期甘肃政法学院实验管理中心印制实验题目第七章、树形结构小组合作否姓名班级学 号一、实验目的7.1实现二叉树的各种基本运算的算法7.2实现二叉树的各种遍历算法7.3求二叉树从根节点到叶子节点的路径 7.4由遍历序列构造二叉树 7.5实现中序线索化二叉树 7.6构造哈夫曼树7.7用二叉树来表示代数表达式二实验环境安装了Windows7操作系统，并且安装了Microsoft Visual C+ 6.0。三、实验内容与步骤7.1实现二叉树的各种基本运算的算法

2、【编写一个程序exp7-1.cpp，实现二叉树的各种基本运算的算法。（1） 输出二叉树b（2） 输出H节点的左右孩子节点值（3） 输出二叉树b的深度（4） 输出二叉树b的宽度（5） 输出二叉树b的节点个数（6） 输出二叉树b的叶子节点个数（7） 释放二叉树b输入程序如下：#include "stdafx.h"/文件名:exp7-1.cpp#include <stdio.h>#include"algo7-1.cpp"typedef char ElemType;/typedef struct node/ElemType data;/数据元素/st

3、ruct node *lchild;/指向左孩子/struct node *rchild;/指向右孩子/ BTNode;/extern void CreateBTNode(BTNode *&b,char *str);/extern BTNode *FindNode(BTNode *b,ElemType x);/extern BTNode *LchildNode(BTNode *p);/extern BTNode *RchildNode(BTNode *p);/extern int BTNodeDepth(BTNode *b);/extern void DispBTNode(BTNode

4、 *b);/extern int BTWidth(BTNode *b);/extern int Nodes(BTNode *b);/extern int LeafNodes(BTNode *b);/extern void DestroyBTNode(BTNode *&b);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)");printf("二叉树的基本运算如下:n");printf(" (1)输出二叉树:");Dis

5、pBTNode(b);printf("n");printf(" (2)H节点:");p=FindNode(b,'H');if (p!=NULL)lp=LchildNode(p);if (lp!=NULL) printf("左孩子为%c ",lp->data);elseprintf("无左孩子 ");rp=RchildNode(p);if (rp!=NULL)printf("右孩子为%c",rp->data);elseprintf("无右孩子 ");

6、printf("n");printf(" (3)二叉树b的深度:%dn",BTNodeDepth(b);printf(" (4)二叉树b的宽度:%dn",BTWidth(b);printf(" (5)二叉树b的节点个数:%dn",Nodes(b);printf(" (6)二叉树b的叶子节点个数:%dn",LeafNodes(b);printf(" (7)释放二叉树bn");DestroyBTNode(b);输入程序并运行，如图7.2实现二叉树的各种遍历算法编写一个程序exp7

7、-2.cpp，实现二叉树的各种遍历算法。 输入程序如下：#include "stdafx.h"/文件名:exp7-2.cpp#include <stdio.h>#include "algo7-1.cpp"#include <malloc.h>#define MaxSize 100typedef char ElemType;void PreOrder(BTNode *b) /先序遍历的递归算法if (b!=NULL) printf("%c ",b->data);/访问根节点PreOrder(b->lc

8、hild);/递归访问左子树PreOrder(b->rchild);/递归访问右子树void PreOrder1(BTNode *b)BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) top+;/根节点入栈 Sttop=b; while (top>-1)/栈不为空时循环 p=Sttop;/退栈并访问该节点 top-; printf("%c ",p->data); if (p->rchild!=NULL)/右孩子入栈 top+; Sttop=p->rchild; if (p->lchild!=NU

9、LL)/左孩子入栈 top+; Sttop=p->lchild;printf("n");void InOrder(BTNode *b) /中序遍历的递归算法if (b!=NULL) InOrder(b->lchild);/递归访问左子树printf("%c ",b->data);/访问根节点InOrder(b->rchild);/递归访问右子树void InOrder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top>-1 | p!=N

10、ULL)while (p!=NULL)top+;Sttop=p;p=p->lchild;if (top>-1)p=Sttop;top-;printf("%c ",p->data);p=p->rchild;printf("n");void PostOrder(BTNode *b) /后序遍历的递归算法if (b!=NULL) PostOrder(b->lchild);/递归访问左子树PostOrder(b->rchild);/递归访问右子树printf("%c ",b->data);/访问根节点

11、void PostOrder1(BTNode *b)BTNode *StMaxSize;BTNode *p;int flag,top=-1;/栈指针置初值if (b!=NULL)dowhile (b!=NULL)/将t的所有左节点入栈top+;Sttop=b;b=b->lchild;p=NULL;/p指向当前节点的前一个已访问的节点flag=1;while (top!=-1 && flag)b=Sttop;/取出当前的栈顶元素if (b->rchild=p)/右子树不存在或已被访问,访问之printf("%c ",b->data);/访问*

12、b节点top-;p=b;/p指向则被访问的节点elseb=b->rchild;/t指向右子树flag=0; while (top!=-1);printf("n"); void TravLevel(BTNode *b)BTNode *QuMaxSize;/定义循环队列int front,rear;/定义队首和队尾指针front=rear=0;/置队列为空队列 if (b!=NULL) printf("%c ",b->data); rear+;/节点指针进入队列Qurear=b; while (rear!=front)/队列不为空 front=(

13、front+1)%MaxSize;b=Qufront;/队头出队列if (b->lchild!=NULL)/输出左孩子,并入队列printf("%c ",b->lchild->data);rear=(rear+1)%MaxSize;Qurear=b->lchild;if (b->rchild!=NULL)/输出右孩子,并入队列printf("%c ",b->rchild->data);rear=(rear+1)%MaxSize;Qurear=b->rchild; printf("n");

14、void main()BTNode *b;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"); printf("二叉树b:");DispBTNode(b);printf("n");printf("层次遍历序列:");TravLevel(b);printf("先序遍历序列:n");printf(" 递归算法:");PreOrder(b);printf("n");printf(" 非递归算法:"

15、;);PreOrder1(b);printf("中序遍历序列:n");printf(" 递归算法:");InOrder(b);printf("n");printf(" 非递归算法:");InOrder1(b);printf("后序遍历序列:n");printf(" 递归算法:");PostOrder(b);printf("n");printf(" 非递归算法:");PostOrder1(b);DestroyBTNode(b); 输入程序

16、并运行，如图图87.3求二叉树从根节点到叶子节点的路径对7.1的二叉树，设计一个程序exp7-3.cpp完成如下功能：（1） 输出所有叶子节点（2） 输出所有叶子节点到根节点的路径（3） 输出（2）中的第一条最长路径输入程序如下：#include "stdafx.h"/文件名:exp7-3.cpp#include <stdio.h>#include <malloc.h>#include "algo7-1.cpp"#define MaxSize 100typedef char ElemType;Node *&b);void

17、AllPath(BTNode *b)struct snode BTNode *node;/存放当前节点指针 int parent;/存放双亲节点在队列中的位置 QuMaxSize;/定义顺序队列int front,rear,p;/定义队头和队尾指针 front=rear=-1;/置队列为空队列rear+; Qurear.node=b;/根节点指针进入队列Qurear.parent=-1;/根节点没有双亲节点 while (front<rear)/队列不为空 front+;b=Qufront.node;/队头出队列if (b->lchild=NULL && b->

18、;rchild=NULL)/*b为叶子节点printf(" %c到根节点逆路径:",b->data);p=front;while (Qup.parent!=-1)printf("%c ",Qup.node->data);p=Qup.parent;printf("%cn",Qup.node->data);if (b->lchild!=NULL)/左孩子入队列rear+;Qurear.node=b->lchild;Qurear.parent=front;if (b->rchild!=NULL)/右孩子入

19、队列rear+;Qurear.node=b->rchild;Qurear.parent=front; void AllPath1(BTNode *b,ElemType path,int pathlen)int i;if (b!=NULL)if (b->lchild=NULL && b->rchild=NULL)/*b为叶子节点printf(" %c到根节点逆路径: %c ",b->data,b->data);for (i=pathlen-1;i>=0;i-)printf("%c ",pathi);pri

20、ntf("n");elsepathpathlen=b->data;/将当前节点放入路径中pathlen+;/路径长度增1AllPath1(b->lchild,path,pathlen);/递归扫描左子树AllPath1(b->rchild,path,pathlen);/递归扫描右子树pathlen-;/恢复环境void LongPath(BTNode *b,ElemType path,int pathlen,ElemType longpath,int &longpathlen)int i;if (b=NULL)if (pathlen>long

21、pathlen)/若当前路径更长,将路径保存在longpath中for (i=pathlen-1;i>=0;i-)longpathi=pathi;longpathlen=pathlen;elsepathpathlen=b->data;/将当前节点放入路径中pathlen+;/路径长度增1LongPath(b->lchild,path,pathlen,longpath,longpathlen);/递归扫描左子树LongPath(b->rchild,path,pathlen,longpath,longpathlen);/递归扫描右子树pathlen-;/恢复环境void D

22、ispLeaf(BTNode *b) if (b!=NULL) if (b->lchild=NULL && b->rchild=NULL) printf("%c ",b->data); else DispLeaf(b->lchild);DispLeaf(b->rchild);void main()BTNode *b;ElemType pathMaxSize,longpathMaxSize;int i,longpathlen=0;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I

23、)"); printf("二叉树b:");DispBTNode(b);printf("n");printf("b的叶子节点:");DispLeaf(b);printf("n");printf("AllPath:n");AllPath(b);printf("AllPath1:n");AllPath1(b,path,0);LongPath(b,path,0,longpath,longpathlen);printf("第一条最长逆路径长度:%dn",l

24、ongpathlen);printf("第一条最长逆路径:");for (i=longpathlen-1;i>=0;i-)printf("%c ",longpathi);printf("n");DestroyBTNode(b);输入程序并运行，如图图127.4由遍历序列构造二叉树【设计一个程序exp7-4.cpp实现由先序遍历以及由中序遍历序列构造一颗二叉树的功能要求以括号表示和凹入表示法输入该二叉树。并用“ABDEHJKLMNCFGI”和“DBJHLKMNEAFCGI”以及由中序遍历序列“DBJHLKMNEAFCGI”和后序遍

25、历序列“DJLNMKHEBFIGCA”进行验证。输入程序如下：#include "stdafx.h"/文件名:exp7-4.cpp#include <stdio.h>#include <malloc.h>#include"algo7-1.cpp"#define MaxSize 100#define MaxWidth 40typedef char ElemType;/typedef struct node /ElemType data;/数据元素/struct node *lchild;/指向左孩子/struct node *rch

26、ild;/指向右孩子/ BTNode;/extern void DispBTNode(BTNode *b);/extern void DestroyBTNode(BTNode *&b);BTNode *CreateBT1(char *pre,char *in,int n)BTNode *s;char *p;int k;if (n<=0) return NULL;s=(BTNode *)malloc(sizeof(BTNode);/创建二叉树节点*ss->data=*pre;for (p=in;p<in+n;p+)/在中序序列中找等于*ppos的位置kif (*p=*p

27、re)break;k=p-in;s->lchild=CreateBT1(pre+1,in,k);s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);return s;BTNode *CreateBT2(char *post,char *in,int n,int m)BTNode *s;char *p,*q,*maxp;int maxpost,maxin,k;if (n<=0) return NULL;maxpost=-1;for (p=in;p<in+n;p+)/求in中全部字符中在post中最右边的那个字符for (q=post;q<p

28、ost+m;q+)/在in中用maxp指向这个字符,用maxin标识它在in中的下标if (*p=*q)k=q-post;if (k>maxpost) maxpost=k;maxp=p;maxin=p-in;s=(BTNode *)malloc(sizeof(BTNode);/创建二叉树节点*ss->data=postmaxpost;s->lchild=CreateBT2(post,in,maxin,m);s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m);return s;void DispBTNode1(BTNode *b) /

29、以凹入表表示法输出一棵二叉树BTNode *StMaxSize,*p;int levelMaxSize2,top=-1,n,i,width=4;char type;if (b!=NULL)top+;Sttop=b;/根节点入栈leveltop0=width;leveltop1=2;/2表示是根while (top>-1)p=Sttop;/退栈并凹入显示该节点值n=leveltop0;switch(leveltop1)case 0:type='L'break;/左节点之后输出(L)case 1:type='R'break;/右节点之后输出(R)case 2:

30、type='B'break;/根节点之后前输出(B)for (i=1;i<=n;i+)/其中n为显示场宽,字符以右对齐显示printf(" ");printf("%c(%c)",p->data,type);for (i=n+1;i<=MaxWidth;i+=2)printf("-");printf("n");top-;if (p->rchild!=NULL)/将右子树根节点入栈top+;Sttop=p->rchild;leveltop0=n+width;/显示场宽增wi

31、dthleveltop1=1;/1表示是右子树if (p->lchild!=NULL)/将左子树根节点入栈top+;Sttop=p->lchild;leveltop0=n+width; /显示场宽增widthleveltop1=0; /0表示是左子树void main()BTNode *b;ElemType pre="ABDEHJKLMNCFGI"ElemType in="DBJHLKMNEAFCGI"ElemType post="DJLNMKHEBFIGCA"b=CreateBT1(pre,in,14);printf(&

32、quot;先序序列:%sn",pre);printf("中序序列:%sn",in);printf("构造一棵二叉树b:n");printf(" 括号表示法:");DispBTNode(b);printf("n");printf(" 凹入表示法:n");DispBTNode1(b);printf("nn");printf("中序序列:%sn",in);printf("后序序列:%sn",post);b=CreateBT2(pos

33、t,in,14,14);printf("构造一棵二叉树b:n");printf(" 括号表示法:");DispBTNode(b);printf("n");printf(" 凹入表示法:n");DispBTNode1(b);printf("n");DestroyBTNode(b);运行程序，如图7.5 实现中序线索化二叉树设计一个程序exp7-5.cpp实现中序线索化二叉树采用递归和非递归两种方式输出线索中序序列。输入程序如下：/ 4.cpp : Defines the entry point f

34、or the console application#include "stdafx.h"/文件名:exp7-5.cpp#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;int ltag,rtag;/增加的线索标记struct node *lchild;/左孩子指针struct node *rchild;/右孩子指针 TBTNode;void CreateTBTNode(TBTNo

35、de * &b,char *str)TBTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch=strj;while (ch!='0')/str未扫描完时循环switch(ch) case '(':top+;Sttop=p;k=1; break;/为左节点case ')':top-;break;case ',':k=2; break;/为右节点default:p=(TBTNode *)malloc(sizeof(TBTNode);p-

36、>data=ch;p->lchild=p->rchild=NULL;if (b=NULL)/*p为二叉树的根节点b=p;else/已建立二叉树根节点switch(k) case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;void DispTBTNode(TBTNode *b)if (b!=NULL)printf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)printf("(

37、");DispTBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispTBTNode(b->rchild);printf(")");TBTNode *pre;/全局变量void Thread(TBTNode *&p)if (p!=NULL)Thread(p->lchild);/左子树线索化if (p->lchild=NULL)/前驱线索p->lchild=pre;/建立当前节点的前驱线索p->ltag=1;else p->ltag=0

38、;if (pre->rchild=NULL)/后继线索pre->rchild=p;/建立前驱节点的后继线索pre->rtag=1;else pre->rtag=0;pre=p;Thread(p->rchild);/右子树线索化TBTNode *CreateThread(TBTNode *b)/中序线索化二叉树TBTNode *root;root=(TBTNode *)malloc(sizeof(TBTNode);/创建根节点root->ltag=0;root->rtag=1;root->rchild=b;if (b=NULL)/空二叉树root-

39、>lchild=root;elseroot->lchild=b;pre=root;/pre是*p的前驱节点,供加线索用Thread(b);/中序遍历线索化二叉树pre->rchild=root;/最后处理,加入指向根节点的线索pre->rtag=1;root->rchild=pre;/根节点右线索化return root;void InOrder(TBTNode *tb)/被ThInOrder算法调用if (tb->lchild!=NULL && tb->ltag=0)/有左孩子InOrder(tb->lchild);printf

40、("%c ",tb->data);if (tb->rchild!=NULL && tb->rtag=0)/有右孩子InOrder(tb->rchild);void ThInOrder(TBTNode *tb)/中序递归算法InOrder(tb->lchild);void ThInOrder1(TBTNode *tb)/中序非递归算法TBTNode *p=tb->lchild;/指向根节点while (p!=tb)while (p->ltag=0) p=p->lchild;printf("%c &quo

41、t;,p->data);while (p->rtag=1 && p->rchild!=tb)p=p->rchild;printf("%c ",p->data);p=p->rchild;void DestroyTBTNode1(TBTNode *tb)/被DestroyTBTNode算法调用if (tb!=NULL)if (tb->lchild!=NULL && tb->ltag=0) /有左孩子 DestroyTBTNode1(tb->lchild);if (tb->rchild!=

42、NULL && tb->rtag=0) /有右孩子 DestroyTBTNode1(tb->rchild);free(tb);void DestroyTBTNode(TBTNode *tb)/释放中序线索二叉树的所有节点DestroyTBTNode1(tb->lchild);free(tb);void main()TBTNode *b,*tb;CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"); printf("二叉树:");DispTBTNode(b);printf(&

43、quot;n");tb=CreateThread(b);printf("线索中序序列:n");printf(" 递归算法:");ThInOrder(tb);printf("n");printf(" 非递归算法:");ThInOrder1(tb);printf("n");DestroyTBTNode(tb);运行程序，如图7.6构造哈夫曼树设计一个程序exp7-6.cpp构造一颗哈弗曼树，输出对应哈弗曼树编码和平均查找长度。输入程序如下#include "stdafx.h&qu

44、ot;/文件名:exp7-6.cpp#include <stdio.h>#include <string.h>#define N 50/叶子节点数#define M 2*N-1/树中节点总数typedef structchar data5;/节点值int weight;/权重int parent;/双亲节点int lchild;/左孩子节点int rchild;/右孩子节点 HTNode;typedef structchar cdN;/存放哈夫曼码int start; HCode;void CreateHT(HTNode ht,int n)int i,k,lnode,r

45、node;int min1,min2;for (i=0;i<2*n-1;i+)/所有节点的相关域置初值-1hti.parent=hti.lchild=hti.rchild=-1;for (i=n;i<2*n-1;i+)/构造哈夫曼树min1=min2=32767;/lnode和rnode为最小权重的两个节点位置lnode=rnode=-1;for (k=0;k<=i-1;k+)if (htk.parent=-1)/只在尚未构造二叉树的节点中查找if (htk.weight<min1)min2=min1;rnode=lnode;min1=htk.weight;lnode=

46、k;else if (htk.weight<min2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for (i=0;i<n;i+)/根据哈夫曼树求哈夫曼编码hc.start=n;c=i;f=hti.parent;while (f!=-1)/循

47、序直到树根节点if (htf.lchild=c)/处理左孩子节点hc.cdhc.start-='0'else/处理右孩子节点hc.cdhc.start-='1'c=f;f=htf.parent;hc.start+;/start指向哈夫曼编码最开始字符hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)int i,k;int sum=0,m=0,j;printf("输出哈夫曼编码:n"); /输出哈夫曼编码for (i=0;i<n;i+)j=0;printf(" %s:t"

48、,hti.data);for (k=hcdi.start;k<=n;k+)printf("%c",hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;printf("n");printf("平均长度=%gn",1.0*sum/m);void main()int n=15,i;char *str="The","of","a","to","and","in","tha

49、t","he","is","at","on","for","His","are","be"int fnum=1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123;HTNode htM;HCode hcdN;for (i=0;i<n;i+)strcpy(hti.data,stri);hti.weight=fnumi;CreateHT(ht,n);Creat