二叉树编写计算.docx
- 文档编号:14610076
- 上传时间:2023-06-25
- 格式:DOCX
- 页数:23
- 大小:34.23KB
二叉树编写计算.docx
《二叉树编写计算.docx》由会员分享,可在线阅读,更多相关《二叉树编写计算.docx(23页珍藏版)》请在冰点文库上搜索。
二叉树编写计算
《数据结构的课程设计》
报告
题目:
二叉树的应用设计与实现
班级:
1612401
学号:
161240113
姓名:
张修鸣
指导老师:
孙涵
完成日期:
2014.1.3
目录
一.需求分析.
二.程序主要功能.
三.程序运行平台.
四.程序类说明.
五.模块分析.
六.存在的不足与对策.
七.体验感悟
八.程序源代码.
需求分析
编程实现二叉树的建立,先序、中序、后序、层序遍历(递归和非递归方法),二叉树的高度、繁茂度,交换左右子树,统计叶子节点的数目,判断是否为完全二叉树,按树的形态在屏幕上打印输出。
程序主要功能
该程序的主要功能有:
(1)从文件中读入建树信息,树的节点数目不小于20个,树的高度不小于4。
(2)建树信息采用两行英文字符表示,每个英文字符代表一个结点,第1行为树的中序遍历结果,第2行为树的后序遍历结果。
(3)先序、中序、后序、层序遍历(递归和非递归方法),二叉树的高度、繁茂度,交换左右子树,统计叶子节点的数目,判断是否为完全二叉树,按树的形态在屏幕上打印输出。
程序运行平台
该程序是用VC++6.0制做的,使用MicrosoftVisualC++6.0运行该程序,具体操作是:
打开MicrosoftVisualC++6.0,菜单栏里点文件→打开工作区→找到“图书管理系统.dsw”这个文件→打开,或者在资源管理器中双击该文件,此时,VC++6.0会自动打开,并载入该系统相关资源,点击Run命令菜单或者或用快捷键Ctrl+F5运行该程序。
trl计分析能_________________________________________________________________________________________________________________________
程序类说明
二叉树
typedefstructBiTNode{
chardata;
intc;
structBiTNode*LChild;
structBiTNode*RChild;
}*BiTree,*nodetype;
nodetypep;
函数分析:
intPreOrderTraverse(nodetype&T){//递归先序遍历T
intInOrderTraverse(nodetype&T){//递归中序遍历T
intPostOrderTraverse(nodetype&T){//递归后序遍历T
intNUPre(nodetype&T)//非递归先序遍历T
intNUIn(nodetype&T)//非递归中序遍历T
intNUPost(nodetype&T)//非递归后序遍历T
voidchange(nodetype&T){//交换左右子树
intInitBiTree(nodetype&T){//构造空二叉树
nodetypeIntertl(charx,nodetype&T){//在结点的左子树插入x
nodetypeIntertr(charx,nodetype&T){//在结点的右子树插入x
intAssign(charv,nodetype&e){//结点e赋值为v
intdeep(nodetype&T,intn){//返回深度
intleaves(nodetype&T){//叶子节点数目
voidLevelOrder(BiTreeT){//层次遍历
voidcreate(nodetype&T){从文件中读取信息并建立二叉树
模块分析
我设计的系统,主要分为两大模块1二叉树模块2遍历模块
系统主要完成以下功能:
1二叉树模块:
1交换左右子树
2构造空二叉树
3在结点的左子树插入x
4在结点的右子树插入x
5结点e赋值为v
6返回深度
7叶子节点数目
8从文件中读取信息并建立二叉树
2遍历模块
1递归先序遍历T
2递归中序遍历T
3递归后序遍历T
4非递归先序遍历T
5非递归中序遍历T
6非递归后序遍历T
7层次遍历
文件信息
各种遍历
二叉树的信息
以树的形态显示
存在的不足与对策
由于自身能力有限,所以没有设计非常好的交互界面。
在设计过程中由于设计者的编程功底欠缺,因此学习过程较为艰辛,需要解决的问题也比较多。
在以后的学习中,应该循序渐进,不可急于求成,先打好基础,这样才能更好地发展。
体验感悟
在编写程序的过程中,深切的体会到自身能力还有待提高,通过大规模的查询网上资料与相关书籍我学习到了很多以前不知道的编程方法与各种奇妙的函数语句时,提高了自己对程序设计本身的兴趣,更加乐意去学习这方面的新的东西,并在不断地自我挑战中收获着,或知识技能,或信心勇气。
希望自己在今后的学习中可以更好的完善自我。
程序源代码
#ifndefNUM1_H
#defineNUM1_H
#include
#include
#include
usingnamespacestd;
intn=0;
intn1=0;
typedefstructBiTNode{
chardata;
intc;
structBiTNode*LChild;
structBiTNode*RChild;
}*BiTree,*nodetype;
nodetypep;
voidVisit(nodetype&T){
if(T!
=NULL)
cout<
}
intInitBiTree(nodetype&T){//构造空二叉树
if((T=(nodetype)malloc(sizeof(nodetype)))==NULL)return0;
T->c=0;
T->LChild=NULL;
T->RChild=NULL;
n=0;
return1;
}
nodetypeIntertl(charx,nodetype&T){//在结点的左子树插入x
nodetypep;
if(T==NULL){
cout<<"\n插入错误";
returnNULL;
}
if((p=(nodetype)malloc(sizeof(nodetype)))==NULL)returnNULL;
else{p->data=x;
p->LChild=NULL;
p->RChild=NULL;
}
if(T->LChild==NULL)T->LChild=p;
else{
p->LChild=T->LChild;
T->LChild=p;}
returnT;
}
nodetypeIntertr(charx,nodetype&T){//在结点的右子树插入x
nodetypep;
if(T==NULL){
cout<<"\n插入错误";
returnNULL;
}
if((p=(nodetype)malloc(sizeof(nodetype)))==NULL)returnNULL;
else{p->data=x;
p->LChild=NULL;
p->RChild=NULL;
}
if(T->RChild==NULL)T->RChild=p;
else{
p->RChild=T->RChild;
T->RChild=p;}
returnT;
}
intDestroyBiTree(nodetype&T){//销毁二叉树
if(T){free(T);
return1;
}
return0;
}
intClearBiTree(nodetype&T){//清空二叉树
nodetypet;
if((t=(nodetype)malloc(sizeof(nodetype)))==NULL)return0;
t->LChild=NULL;
t->RChild=NULL;
T=t;
n=0;
return1;
}
intBiTreeD(BiTreeT){//返回二叉树的结点数
returnn;
}
charRoot(nodetype&T){
intt;
t=T->data;
returnt;
}
charValue(nodetype&T,nodetype&e){//返回e值
returne->data;
}
intAssign(charv,nodetype&e){//结点e赋值为v
e->data=v;
n++;
return1;
}
voidctree(charstack1[],charstack2[],nodetype&T,intk){
inti;
chara,s1[100],s2[100];
if(k==0)return;
a=stack1[k-1];
Assign(a,T);
if(k==1)
return;
for(i=0;i if(a==stack2[i])break; if(i! =k-1) { for(intj=i;j { s1[j-i]=stack1[j]; s2[j-i]=stack2[j+1]; } if(i! =k-1) Intertr(a,T); ctree(s1,s2,T->RChild,k-1-i); } for(intj=0;j s1[j]=stack1[j]; s2[j]=stack2[j]; } if(i! =0) Intertl(a,T); ctree(s1,s2,T->LChild,i); } voidcreate(nodetype&T){ charstack1[100],stack2[100]; intm=0; fstreamfp; fp.open("a.txt",ios: : in); if(fp.fail()) { cout<<"文件打开失败! \n"; exit(0); } while(! fp.eof()){ if(m==0){ fp.getline(stack2,100); m=1; } if(m==1)fp.getline(stack1,100); } ctree(stack1,stack2,T,strlen(stack2)); fp.close(); } intdeep(nodetype&T,intn){//返回深度 inti,j; j=i=0; if((T->LChild==NULL)&&(T->RChild==NULL))returnn; if(T->LChild! =NULL) i=deep(T->LChild,n+1); if(T->RChild! =NULL) j=deep(T->RChild,n+1); n=(i>j)? i: j; returnn; } nodetypeparent(nodetype&T,nodetype&e){//返回e的双亲 nodetypep; if(T==NULL)returnNULL; if((T->LChild==e)||(T->RChild==e))returnT; if(T->LChild! =NULL){ p=parent(T->LChild,e); returnp;} if(T->LChild! =NULL){ p=parent(T->LChild,e); returnp;} returnNULL; } nodetypeSeach(nodetype&T,inte){//查找e,返回e的结点 nodetypep; if(T==NULL)returnNULL; if(T->data==e)returnT; if(T->LChild! =NULL){ p=Seach(T->LChild,e); returnp;} if(T->LChild! =NULL){ p=Seach(T->LChild,e); returnp;} returnNULL; } nodetypeLeftchild(nodetype&T,nodetype&e){//返回e的左孩子 if(e->LChild! =NULL)returne->LChild; elsereturnNULL; } nodetypeReftchild(nodetype&T,nodetype&e){//返回e的右孩子 if(e->RChild! =NULL)returne->RChild; elsereturnNULL; } intleaves(nodetype&T){//叶子节点数目 if(T==NULL)return0; if(T->LChild==NULL&&T->RChild==NULL) n1++; leaves(T->LChild); leaves(T->RChild); returnn1; } typedefstructQNode { BiTNodedata; structQNode*next; }QNode,*QueuePtr;//队列节点类型 typedefstruct { QueuePtrfront; QueuePtrrear; }LinkQueue;//队列的头尾指针 voidInitQueue(LinkQueue*Q)//创建队列 { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); Q->rear->next=NULL; } voidEnQueue(LinkQueue*Q,BiTNodee)//入队操作 { QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; } BiTNodeDeQueue(LinkQueue*Q)//出对操作 { BiTNodee;QueuePtrp; p=Q->front->next; e=p->data; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; free(p); return(e); } intQueueEmpty(LinkQueue*Q)//判断队列是否为空 { if(Q->front==Q->rear) return1; else return0; } voidLevelOrder(BiTreeT)//层次遍历 { LinkQueueQ;BiTNodep; InitQueue(&Q); EnQueue(&Q,*T); while(! QueueEmpty(&Q)) { p=DeQueue(&Q); printf("%c\t",p.data); if(p.LChild! =NULL) EnQueue(&Q,*(p.LChild)); if(p.RChild! =NULL) EnQueue(&Q,*(p.RChild)); } } #endif #include #include #include"math.h" #include"4.h" #include"stdio.h" intn3; usingnamespacestd; #defineM64 charC[M][M]; intPr(nodetype&T,intr,inti,intj,intl){ intn=pow(2,(double)(i-1)); if(n==1)C[r+l][j]=T->data; else C[r+l*n/2][j]=T->data; if(T->LChild==NULL&&T->RChild==NULL)return0; if(T->LChild! =NULL) Pr(T->LChild,r+l*n/2,i-1,j+1,-1); if(T->RChild! =NULL) Pr(T->RChild,r+l*n/2,i-1,j+1,1); return1; } voidshow(nodetype&T,inti) { intz,x; z=x=0; for(intj=0;j for(intk=0;k C[j][k]='0'; intn; n=pow(2,(double)(i-1)); C[n][0]=T->data; if(T->LChild! =NULL) Pr(T->LChild,n,i-1,1,-1); if(T->RChild! =NULL) Pr(T->RChild,n,i-1,1,1); C[100][100]; for(j=0;j z=0; for(intk=0;k if(C[k][j]=='0')cout<<""; else{cout< z++; } x=j*z+x; cout< } n3=x; } intPreOrderTraverse(nodetype&T){//递归先序遍历T if(T==NULL)return0; Visit(T); if(T->LChild! =NULL) PreOrderTraverse(T->LChild); if(T->RChild! =NULL) PreOrderTraverse(T->RChild); return1; } intInOrderTraverse(nodetype&T){//递归中序遍历T if(T==NULL)return0; if(T->LChild! =NULL) PreOrderTraverse(T->LChild); Visit(T); if(T->RChild! =NULL) PreOrderTraverse(T->RChild); return1; } intPostOrderTraverse(nodetype&T){//递归后序遍历T if(T==NULL)return0; PostOrderTraverse(T->LChild); PostOrderTraverse(T->RChild); Visit(T); return1; } intNUPre(nodetype&T)//非递归先序遍历T { nodetypestack[100],p; p=T; intm=0; while(! (p==NULL&&m==0)){ while(p! =NULL){Visit(p); if(m<99){ stack[m]=p; m++; } else{ cout<<"栈溢出"; return0; } p=p->LChild; } if(m<=0)return1; else{ m--; p=stack[m]; p=p->RChild;} } return1; } intNUIn(nodetype&T)//非递归中序遍历T { nodetypestack[100],p; p=T; intm=0; while(! (p==NULL&&m==0)){ while(p! =NULL){ if(m<99){ stack[m]=p; m++; } else{ cout<<"栈溢出"; return0; } p=p->LChild; } if(m<0)return1; else{ m--; p=stack[m];Visit(p); p=p->RChild; } } return1; } intNUPost(nodetype&T)//非递归后序遍历T { nodetypestack[100],p,pv=NULL; p=T; intm=0; while(p! =NULL||m>0){ while(p! =NULL){ if(m<99){ stack[m++]=p; } else{ cout<<"栈溢出"; return0; } p=p->LChild; } if(m<=0)return1; p=stack[m-1]; if(p->RChild==NULL||p->RChild==pv){ Visit(p); m--; pv=p; p=NULL;} else p=p->RChild; } return1; } voidchange(nodetype&T){//交换左右子树 nodetypel,r; l=T->LChild; r=T->RChild; T->LChild=r; T->RChild=l; } intSF(inta){//判断是否为完全二叉树 if((double)n return1; else return0; } intmain(){ nodetypeT; InitBiTree(T); create(T); inti; cout<<"\n递归中序遍历T"< cout<<"\n非递归中序遍历T"< NUIn(T); cout<<"\
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 编写 计算
![提示](https://static.bingdoc.com/images/bang_tan.gif)