二叉树结点的左右子树交换 课程设计报告
更新时间:2023-12-18 02:22:01 阅读量: 教育文库 文档下载
目录
一 需求分析.................................................................................................................. 1 二 概要设计.................................................................................................................. 1 三 详细设计.................................................................................................................. 2 四 调试分析和测试结果.............................................................................................. 4 五 总结.......................................................................................................................... 6 六 参考文献.................................................................................................................. 7 七 致谢.......................................................................................................................... 7 八 附录.......................................................................................................................... 7
一 需求分析
问题描述:交换二叉树中所有结点的左、右子树,该二叉树以二叉链表作为存储结构。
基本思想:设二叉树的根指针为s,且以二叉链表表示,可利用一个类型为Q的指针队列来实现,且设队列单元包含两个域,一个为front,一个为rear,整个队列容量为maxsize,当树非空时,将当前的树根结点入队列,同时将当前队列顶元素出队列当作根结点,然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换;再将交换后的左指针或右指针入队列,这样反复进行,直到队列空为止。
图1-1是该课题的功能模块图:
二叉树结点的左、右子树的交换 重新建立二叉树 交换左右子数 先根遍历二叉树退出 图 1-1
二 概要设计
该课题主要分为三个功能模块:重新建立二叉树、交换左右子数、先根遍历二叉树。这里主要用到了队列及二叉树的知识,先对二叉树进行层次遍历,然后
1
再进行左右子树交换操作,最后再进行先根遍历二叉树,这就实现了二叉树节点的左右子树交换。三个功能模块相互独立又相互关联,独立仅在于各自操作互不影响,而关联在于后两个功能可以对当前建立的二叉树进行操作,产生不同的结果。
该功能流程图(图2-1)如下:
开 始 输入二叉树的节点(以“!“结束) enter 0 菜 单 1 重新建立二叉树 2 交换左右子数 3 先根遍历二叉树 结 束 图2-1
三 详细设计
本课题为二叉树结点的左、右子树的交换,主要分为三个模块:重新建立二叉树、交换左右子数、先根遍历二叉树。各模块的详细设计如下:
2
首先定义结构体类型及二叉树结点类型,如下所示:
typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉树结点类型
struct node {
datatype data; //结点数据
pointer lchild,rchild; //左右孩子结点 };
三个模块各写三个函数,分别如下所示:
bitree level_creat() //由层次序列建立二叉树,返回根指针 {
char ch; ch=cin.get(); int front,rear; pointer root,s;
root=NULL; //置空二叉树 front=rear=0; //置空队列 //while(cin>>ch,ch!='!') while(cin>>ch,ch!='!') { if(ch!='@') //非虚结点,建立新结点 { s=new node; s->data=ch; s->lchild=s->rchild=NULL; } else s=NULL; rear++; Q[rear]=s; //不管结点是否为虚都要入队 if(rear==1) { root=s; front=1; } //第一个点是根,要修改头指针,他不是孩子 else if(s && Q[front]) //孩子和双亲都不是虚结点 if(rear%2==0) Q[front]->lchild=s; // rear是偶数,新结点是左孩子 else { Q[front]->rchild=s; //rear 是奇数,新结点是右孩子 front++; } }
return root; }
void exchange(bitree t) //交换左右子数函数 {
pointer p;
3
if(t==NULL) return; //空树,直接返回
p=t->lchild; t->lchild=t->rchild; t->rchild=p; //交换 exchange(t->rchild); //遍历原左子树 exchange(t->lchild); //遍历原右子树 }
void preorder(bitree t) //先根遍历函数 {
if(t==NULL) return;
cout<
preorder(t->lchild); //先根遍历左子树 preorder(t->rchild); //先根遍历右子树 flag=1; }
四 调试分析和测试结果
本人主要编写main()函数及先根遍历函数,主函数还是比较简单,就是先根遍历函数有一个小问题:输入的的第一个树即根结点始终打印不出来,分析代码,也没发现什么错误,比较纠结。
下面是测试结果截图: 图4-1为程序运行首页。
图4-1
图4-2为输入二叉树结点的界面。
4
图4-2
图4-3为操作菜单。
图4-3
图4-4为左右二叉树交换成功。
图4-4
图4-5为先根遍历输出结果。
5
图4-5
五 总结
在刚选到该课题的时候,感觉挺茫然的,不知从何处入手。毕竟一个寒假过来,上学期学的数据结构知识也忘的差不多了,并且学的也不是很扎实,所以感觉无从下手。在队友的相互帮助下,我们开始加紧的看书,去图书馆借资料以及上网进行搜索相关的资料,并慢慢的开始做起来。
我们这组三人,分工也比较明确,各自主要负责自己的模块。二本人负责先序遍历模块以及主函数的的编写。在编码过程中,我们遇到了很多小问题,以及一些因粗心而造成的错误,我们都一一解决了。只是我这个环节还有一个问题没有得到解决,就是输出先根遍历的结果时根节点没输出来。这个问题困扰我两天,一直没有得到解决。这个需要以后再继续学习、探究。
总的来说,由于时间有限,本次课程设计“马马虎虎”地完成了。从理论到实践,在整整一个星期的日子里,我学到很多很多的东西,不仅巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的内容。通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才是真正的知识,才能提高自己的实际动手能力和独立思考的能力。
6
六 参考文献
1.严蔚敏 吴伟明 数据结构(C语言版)--清华大学出版社 2. csdn论坛 网址:http://www.csdn.com
七 致谢
完成该课题的设计,离不开队友的相互配合、同学的帮助及老师的指导,在此表示十分感谢!
八 附录
//源代码
#include
/* 二叉树类型的定义(二叉链表形式储存) */
typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉树结点类型 struct node {
datatype data; //结点数据
pointer lchild,rchild; //左右孩子结点 };
typedef pointer bitree; //定义二叉树类型 /* 先根遍历交换左右子树 */ /* 层次遍历序列生成 */
7
const int maxsize=100; int flag=0;
pointer Q[maxsize+1];
bitree level_creat() //由层次序列建立二叉树,返回根指针 {
char ch;
ch=cin.get(); int front,rear; pointer root,s;
root=NULL; //置空二叉树 front=rear=0; //置空队列 //while(cin>>ch,ch!='!') while(cin>>ch,ch!='!') {
if(ch!='@') //非虚结点,建立新结点 {
s=new node; s->data=ch;
s->lchild=s->rchild=NULL; }
else s=NULL; rear++;
Q[rear]=s; //不管结点是否为虚都要入队
if(rear==1) { root=s; front=1; } //第一个点是根,要修改头指针,他不是孩子
else if(s && Q[front]) //孩子和双亲都不是虚结点
if(rear%2==0) Q[front]->lchild=s; // rear是偶数,新结点是左孩子
else {
Q[front]->rchild=s; //rear 是奇数,新结点是右孩子 front++; } }
return root; }
/* 交换左右子数 */
void exchange(bitree t) {
pointer p;
if(t==NULL) return; //空树,直接返回
p=t->lchild; t->lchild=t->rchild; t->rchild=p; //交换 exchange(t->rchild); //遍历原左子树
8
exchange(t->lchild); //遍历原右子树 }
/* 二叉树的先根遍历 */
void preorder(bitree t) //先根遍历 {
if(t==NULL) return;
cout<
preorder(t->lchild); //先根遍历左子树 preorder(t->rchild); //先根遍历右子树 flag=1; }
/*void stop() {
// cout<<\按任意键继续:\ getch(); }*/
void main() {
bitree T=NULL; int ch;
cout<<\首先层次遍历序列生成二叉树,请输入结点数据(输入'@'为虚结点,输入'!'结束):\\n\ T=level_creat(); if(T==NULL) {
cout<<\二叉树生成失败!\\n\ cout<<\按任意键返回菜单:\ getch(); }
else {
cout<<\二叉树生成成功!\\n\ cout<<\按任意键返回菜单:\ getch(); } AA: do{
system(\调用清屏函数 cout<<\
cout<<\┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\
cout<<\┃ 二叉树左右子树交 ┃\
cout<<\┣━━━━━━━━━━━━━━━━━━━━━━━━━━
9
━━━━━━━━━━━━┫\ cout<<\┃\\t\\t1.重新建立二叉树 ┃\
cout<<\┃\\t\\t2.交换左右子数 ┃\
cout<<\┃\\t\\t3.先根遍历二叉树 ┃\
cout<<\┃\\t\\t0.退出 ┃\
cout<<\┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\
cout<<\请选择数字(0-3):\ cin>>ch; switch(ch) {
case 0: break;
case 1: T=level_creat(); system(\
cout<<\二叉树生成成功!\\n\ cout<<\按任意键返回菜单:\ getch(); break;
case 2: exchange(T);
cout<<\左右子树交换成功!\\n\ cout<<\按任意键返回菜单:\ getch(); break;
case 3: cout<<\先根遍历二叉树结果:\\n\ preorder(T); if(flag) {
cout<<\按任意键返回菜单:\ getch(); }
cout< default:cout<<\您输入错误!请重新输入:\\n\\n\ getch(); goto AA; } }while(ch!=0); } 10 ━━━━━━━━━━━━┫\ cout<<\┃\\t\\t1.重新建立二叉树 ┃\ cout<<\┃\\t\\t2.交换左右子数 ┃\ cout<<\┃\\t\\t3.先根遍历二叉树 ┃\ cout<<\┃\\t\\t0.退出 ┃\ cout<<\┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\ cout<<\请选择数字(0-3):\ cin>>ch; switch(ch) { case 0: break; case 1: T=level_creat(); system(\ cout<<\二叉树生成成功!\\n\ cout<<\按任意键返回菜单:\ getch(); break; case 2: exchange(T); cout<<\左右子树交换成功!\\n\ cout<<\按任意键返回菜单:\ getch(); break; case 3: cout<<\先根遍历二叉树结果:\\n\ preorder(T); if(flag) { cout<<\按任意键返回菜单:\ getch(); } cout< default:cout<<\您输入错误!请重新输入:\\n\\n\ getch(); goto AA; } }while(ch!=0); } 10
正在阅读:
二叉树结点的左右子树交换 课程设计报告12-18
七年级地理上册 世界的地形教案 湘教版03-12
2019年师德师风建设工作总结12-30
爱心化甘露 润物细无声 浅谈差生转化问题09-23
土木材料力学(A卷)试题09-22
商法(保险法)练习(1)09-20
街道统战工2022年作要点08-01
2019年整理中国市场营销趋势分析10-11
六级笔试新题型模拟试卷0105-26
旅馆建筑设计调研报告 - 图文11-14
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 子树
- 结点
- 左右
- 交换
- 课程
- 报告
- 设计
- 《算法分析》实验指导书(1)2015-2016
- 中国共产党的组织、纪律和作风考试题
- 重大事项社会稳定风险评估工作实施细则
- 最新冀教版四年级数学上全册教学反思
- 寒假亲子共读感悟
- 椒江区住所信息申报表(盖章表格)新版
- 北洺河选矿工艺流程图
- 大地(备案)N125号-财产综合保险条款
- 弧长和扇形面积导学案
- 自动化综合设计 - 用matlab进行单位负反馈系统的校正设计 - 图文
- 肤质不同 保养方法不一样
- 数据库应用技术复习提要及答案
- 实验小学学生艺术素养监测实施方案
- 七年级政治上册 第二单元 友谊的天空单元练习 新人教版(道德与法治)
- 浅谈当前消防宣传工作中存在的问题及解决对策
- 知识产权法习题及答案(研究生)
- 安全验收评价报告 - 图文
- 组成原理练习题(1)
- 主次矛盾和矛盾主次方面的区分
- 肿瘤预防与检测运营方案