数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc

数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc

ID:56734006

大小:123.50 KB

页数:10页

时间:2020-07-06

数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc_第1页
数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc_第2页
数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc_第3页
数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc_第4页
数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc_第5页
资源描述:

《数据结构实验 实现中序线索化二叉树 构造哈夫曼树.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、.实验报告课程名称数据结构实验项目名称实现中序线索化二叉树,构造哈夫曼树班级与班级代码实验室名称(或课室)SS1-204专业软件工程任课教师学号:姓名:实验日期:2011年11月18日商学院教务处制..实验报告成绩评价:评价项目优良一般差实验任务是否明确实验步骤是否清晰详尽实验任务是否完成实验结果是否正确程序设计是否规标准版面整体效果是否美观指导教师(签名)2011年月日说明:指导教师评分后,实验报告交院(系)办公室保存。..实验题7.5实现中序线索化二叉树/*文件名:exp7-5.cpp*/#include#includ

2、e#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;intltag,rtag;/*增加的线索标记*/structnode*lchild;structnode*rchild;}TBTNode;voidCreateTBTNode(TBTNode*&b,char*str){TBTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;/*建立的二叉树初始时为空*/ch=str[j];whi

3、le(ch!='')/*str未扫描完时循环*/{switch(ch){case'(':top++;St[top]=p;k=1;break;/*为左结点*/case')':top--;break;case',':k=2;break;/*为右结点*/default:p=(TBTNode*)malloc(sizeof(TBTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)/**p为二叉树的根结点*/b=p;else/*已建立二叉树根结点*/{switch(k)..{case1:St

4、[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}voidDispTBTNode(TBTNode*b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL

5、

6、b->rchild!=NULL){printf("(");DispTBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispTBTNode(b->rchild);printf(")");}}}T

7、BTNode*pre;/*全局变量*/voidThread(TBTNode*&p){if(p!=NULL){Thread(p->lchild);/*左子树线索化*/if(p->lchild==NULL)/*前驱线索*/{p->lchild=pre;/*建立当前结点的前驱线索*/..p->ltag=1;}elsep->ltag=0;if(pre->rchild==NULL)/*后继线索*/{pre->rchild=p;/*建立前驱结点的后继线索*/pre->rtag=1;}elsepre->rtag=0;pre=p;Thread(p->rch

8、ild);/*右子树线索化*/}}TBTNode*CreaThread(TBTNode*b)/*中序线索化二叉树*/{TBTNode*root;root=(TBTNode*)malloc(sizeof(TBTNode));/*创建根结点*/root->ltag=0;root->rtag=1;root->rchild=b;if(b==NULL)/*空二叉树*/root->lchild=root;else{root->lchild=b;pre=root;/*pre是*p的前驱结点,供加线索用*/Thread(b);/*中序遍历线索化二叉树*/p

9、re->rchild=root;/*最后处理,加入指向根结点的线索*/pre->rtag=1;root->rchild=pre;/*根结点右线索化*/}returnroot;}voidThInOrder(TBTNode*tb){..TBTNode*p=tb->lchild;/*指向根结点*/while(p!=tb){while(p->ltag==0)p=p->lchild;printf("%c",p->data);while(p->rtag==1&&p->rchild!=tb){p=p->rchild;printf("%c",p->data

10、);}p=p->rchild;}}voidmain(){TBTNode*b,*tb;CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。