二叉排序树的遍历.docx
- 文档编号:16903026
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:18
- 大小:94.01KB
二叉排序树的遍历.docx
《二叉排序树的遍历.docx》由会员分享,可在线阅读,更多相关《二叉排序树的遍历.docx(18页珍藏版)》请在冰点文库上搜索。
二叉排序树的遍历
课程设计名称:
数据结构课程设计
设计题目:
排序二叉树的遍历
完成期限:
自2011年12月26日至2011年12月29日共1周
设计依据、要求及主要内容(可另加附页):
一、设计目的
熟悉各种数据结构和运算,会使用数据结构的基本操作解决一些实际问题。
二、设计要求
(1)重视课程设计环节,用严谨、科学和踏实的工作态度对待课程设计的每一项任务;
(2)按照课程设计的题目要求,独立地完成各项任务,严禁抄袭;凡发现抄袭,抄袭者与被抄袭者皆以零分计入本课程设计成绩。
凡发现实验报告或源程序雷同,涉及的全部人员皆以零分计入本课程设计成绩;
(3)学生在接受设计任务后,首先要按设计任务书的要求编写设计进程表;
(4)认真编写课程设计报告。
三、设计内容
排序二叉树的遍历(用递归或非递归的方法都可以)
1)问题描述
输入树的各个结点,建立排序二叉树,对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。
2)基本要求
(1)用菜单实现
(2)能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列和叶子结点的数目。
四、参考文献
1.王红梅.数据结构.清华大学出版社
2.王红梅.数据结构学习辅导与实验指导.清华大学出版社
3.严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社
指导教师(签字):
教研室主任(签字):
批准日期:
2011年12月17日
主要内容:
一、需求分析:
输入树的各个结点,建立排序二叉树,对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。
我自己的思想:
首先设想把源程序分成头文件,调用和主函数三部分。
在头文件中申明类和定义结构体,把先序,中序,后序,层次和叶子节点数的函数定义在类中。
然后在调用文件中,把几个函数的实现定义写在里面。
最后在主函数中把输出结果以菜单的样式输出来的方式写完主函数程序。
实现的过程是先想好自己要输入的是什么,然后通过输入节点制,判断其是否是满足前序遍历,满足则可以实现下后面的功能。
二、问题求解:
现实中的问题:
给同学排队问题。
层次是从头开始每一层一层的排,然后分别记号码。
前序是先从最上面的那一个开始往左手边开始排,排之前先计算好人数,然后开始排,排玩左边排右边。
中序是先从最左边开始,然后左斜上角,然后右下角,再左斜上角,直到最上层为止,然后安这个顺序继续排右边的。
后序是先从最左边开始的,左边的一次排过来,然后直接排右边的,也是安依次的顺序,最后才是最上层的。
三、总体设计:
层次:
前序:
中序:
后序:
四、详细设计:
BiSortTree();//构造函数,初始化一棵二叉树,其前序序列由键盘输入
BiNode
voidPreOrder(BiNode
voidInOrder(BiNode
voidPostOrder(BiNode
voidLeverOrder(BiNode
voidleafnum(BiNode
voidempty();//判断二叉树是否为空
intprintnum();//输出(全部、叶子或单分支)结点数
BiNode
BiNode
五、调试与测试:
调试方法:
在C++程序想调试的地方按F9,然后按F5开始调试。
测试结果与预想的正确。
测试过程中遇到的问题:
输入的排序二叉树的输入顺序不对,导致输出结果与预计的不想符。
采取的措施:
仔细回想几个遍历的过程,通过调试和查看程序是否错误,最后终于解决了错误的地方。
六、关键源程序清单和执行结果:
注释问题都在程序中。
源程序:
//声明类BiSortTree及定义结构BiNode,文件名为bisorttree.h
#ifndefBITREE_H
#defineBITREE_H
intnum;
template
structBiNode//二叉树排序的结点结构
{
Tdata;
BiNode
};
template
classBiSortTree
{
public:
BiSortTree();//构造函数,初始化一棵二叉排序树,其前序序列由键盘输入
BiNode
voidPreOrder(BiNode
voidInOrder(BiNode
voidPostOrder(BiNode
voidLeverOrder(BiNode
voidleafnum(BiNode
voidempty();//判断二叉排序树是否为空
intprintnum();//输出叶子结点数
private:
BiNode
BiNode
};
#endif
//定义类中的成员函数,文件名为bisorttree.cpp
#include
#include
#include"bisorttree.h"
usingnamespacestd;
/*
*前置条件:
二叉排序树不存在
*输入:
无
*功能:
构造一棵二叉树
*输出:
无
*后置条件:
产生一棵二叉树
*/
template
BiSortTree
:
BiSortTree()
{
//this->num=0;
this->root=Creat();
}
/*
*前置条件:
二叉排序树已存在
*输入:
无
*功能:
获取指向二叉排序树根结点的指针
*输出:
指向二叉排序树根结点的指针
*后置条件:
二叉排序树不变
*/
template
BiNode
:
Getroot()
{
returnroot;
}
/*
*前置条件:
二叉排序树已存在
*输入:
无
*功能:
前序遍历二叉排序树
*输出:
二叉排序树中结点的一个线性排列
*后置条件:
二叉排序树不变
*/
template
voidBiSortTree
:
PreOrder(BiNode
{
if(root==NULL)return;
else{
cout<
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
/*
*前置条件:
二叉排序树已存在
*输入:
无
*功能:
中序遍历二叉排序树
*输出:
二叉排序树中结点的一个线性排列
*后置条件:
二叉排序树不变
*/
template
voidBiSortTree
:
InOrder(BiNode
{
if(root==NULL)return;//递归调用的结束条件
else{
InOrder(root->lchild);//中序递归遍历root的左子树
cout<
InOrder(root->rchild);//中序递归遍历root的右子树
}
}
/*
*前置条件:
二叉排序树已存在
*输入:
无
*功能:
后序遍历二叉排序树
*输出:
二叉排序树中结点的一个线性排列
*后置条件:
二叉排序树不变
*/
template
voidBiSortTree
:
PostOrder(BiNode
{
if(root==NULL)return;//递归调用的结束条件
else{
PostOrder(root->lchild);//后序递归遍历root的左子树
PostOrder(root->rchild);//后序递归遍历root的右子树
cout<
}
}
/*
*前置条件:
二叉排序树已存在
*输入:
无
*功能:
层序遍历二叉排序树
*输出:
二叉排序树中结点的一个线性排列
*后置条件:
二叉排序树不变
*/
template
voidBiSortTree
:
LeverOrder(BiNode
{
constintMaxSize=100;
intfront=0;
intrear=0;//采用顺序队列,并假定不会发生上溢
BiNode
BiNode
if(root==NULL)return;
else{
Q[rear++]=root;
while(front!
=rear)
{
q=Q[front++];
cout<
if(q->lchild!
=NULL)Q[rear++]=q->lchild;
if(q->rchild!
=NULL)Q[rear++]=q->rchild;
}
}
}
/*
*前置条件:
空二叉树
*输入:
数据ch;
*功能:
初始化一棵二叉排序树,构造函数调用
*输出:
无
*后置条件:
产生一棵二叉排序树
*/
template
BiNode
:
Creat()
{
BiNode
Tch;
cout<<"请输入创建一棵二叉排序树的结点数据"< cin>>ch; if(ch=="#")root=NULL; else{ root=newBiNode root->data=ch; root->lchild=Creat();//递归建立左子树 root->rchild=Creat();//递归建立右子树 } returnroot; } /* *前置条件: 二叉排序树已经存在 *输入: 无 *功能: 求二叉排序树的叶子结点个数 *输出: 二叉排序树的叶子结点个数 *后置条件: 二叉排序树不变 */ template voidBiSortTree : leafnum(BiNode { if(root==NULL)return; else{ if(! (root->lchild)&&! (root->rchild))//判断是否为叶子结点 num++; leafnum(root->lchild);//左子树中的叶子结点个数 leafnum(root->rchild);//右子树中的叶子结点个数 } } /* 将全局变量num初始化为 */ template voidBiSortTree : empty() { num=0; } /* 输出全局变量num的值 */ template intBiSortTree : printnum() { returnnum; } //二叉树的主函数,文件名为bisorttreemain.cpp #include #include #include"bisorttree.cpp" usingnamespacestd; voidmain() { BiSortTree BiNode intx=-1; while(x! =0) { cout<<"1.前序遍历"< cout<<"2.中序遍历"< cout<<"3.后序遍历"< cout<<"4.层序遍历"< cout<<"5.叶子节点个数"< cout<<"0.退出"< cin>>x; switch(x) {case1: cout<<"前序遍历为: "< bt.PreOrder(root); cout< break; case2: cout<<"中序遍历为: "< bt.InOrder(root); cout< break; case3: cout<<"后序遍历为: "< bt.PostOrder(root); cout< break; case4: cout<<"层序遍历为: "< bt.LeverOrder(root); cout< break; case5: bt.empty(); bt.leafnum(root); cout<<"叶子结点个数为: "< break; case0: exit(0); } } } 结果:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉排序树 遍历