算法与数据结构实验报告实验五
更新时间:2024-03-03 05:01:01 阅读量: 综合文库 文档下载
算法与数据结构实验报告
实验五
实验名称: 二叉树的应用 姓名: 卢丽娟 学号: 211006289 专业: 软件工程 班级: 二班 指导教师: 陈亦萍 日期: 2012年5月19日
一、 实验目的
该实验是验证二叉树的二叉链表表示,实现CreateBiTree算法创建二叉树。
二、 实验内容与实验步骤
利用CreateBiTree算法创建二叉树,实现二叉树的先序、中序、后序递归遍历算法中的一种,编写主程序调用CreateBiTree创建二叉树,并调用先(中、后)序遍历算法,测试不同的输入数据创建二叉树,预期输出并验证输出的结果。
步骤:
1. 创建二叉树
BiTree CreateBiTree(BiTree &T)//二叉树的创建
{//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,构造二叉链表表示的二叉树T
char ch;scanf(\前加1空格,留给回车 if(ch=='#') T=NULL; //空格字符表示空树 else
{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-1); T->data=ch;//生成根节点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树}return T;}//CreateBiTree 2. 父亲结点的输出 int visit(char e)
{ printf(\3.中序遍历
void InorderTraverse(BiTree T) { BiTree node=T; if (node!=NULL)
{ InorderTraverse(node->lchild); //若非空,则先遍历左孩子 visit(node->data);InorderTraverse(node->rchild);}} //遍历结点 4.中序遍历非递归 void Inorder(BiTree T)
{ BiTree node=T;char stack[100];
int top = 0;stack[top] =node->data;
while(node!=NULL) //判断结点是否为空 {
while(stack[top]!='#') //不为空先遍历左孩子,再遍历右孩子 { top++; {
if(node->lchild) stack[top] = node->lchild->data; else stack[top] = '#';}top--;
top--; visit(stack[top]); top++;
if(node->rchild) stack[top] = node->rchild->data;
if(stack[top]!='#')
else stack[top] = '#';}}} 5.后序遍历
void PostOrderTraverse(BiTree T)
{ if (T!=NULL) //判断是否为空的情况 { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); 6. 求树的高度 { if(T)
{ BiTreeDepth(T->lchild,d+1); BiTreeDepth(T->rchild,d+1);} else{ if(d>depth) depth = d;}} 7. 查找并输出指定结点的所有儿子节点 void Child(BiTree T) { if(T) {
if(T->data!=cur_e)
{ Child(T->lchild); Child(T->rchild);} else
{ printf(\左孩子为\
visit(T->data);}}
void BiTreeDepth(BiTree T,int d) //求二叉树的深度
if(T->lchild) printf(\else printf(\空\\n\printf(\右孩子为\
if(T->rchild) printf(\else printf(\空\\n\
8. main函数可以用上面的几个函数直接调用,就有输出结果了。
三、 实验环境
操作系统是Windows XP,开发平台:Microsoft Visual C++ 6.0
四、 实验过程与分析
发现在调试运行的时候,出现的错误都是很低级的,比如说调试成功运行后,却运行错误,运行到一半就无法继续下去,查看程序也没错,后来发现是在主函数中少了getchar(),而且scanf括号中也少了“&”,还有就是大小写问题了。
五、 实验结论
测试的数据和输出结果如下: 1.# 树为空 2. a##
后序遍历二叉树: a 深度为1 输入父亲结点: a
左孩子为空 右孩子为空
中序遍历二叉树(非递归) a
3. a#b#c##
后序遍历二叉树: cba
深度为3
输入父亲结点: a
左孩子为空 右孩子为b
中序遍历二叉树(非递归) abc
六、附录
#include
const int OK = 1,ERROR = 0; #define ok 1 #define error 0 #define overflow -1 int depth=0;
char cur_e;
typedef struct BiTNode
{ char data; BiTNode* lchild; BiTNode* rchild;}BiTNode,*BiTree; BiTree CreateBiTree(BiTree &T)//二叉树的创建
{//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,构造二叉链表表示的二叉树T
char ch;scanf(\前加1空格,留给回车
if(ch=='#') T=NULL; else
{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-1); T->data=ch;//生成根节点 CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树 }
return T;}//CreateBiTree int visit(char e)
{ printf(\ return 1;} //中序遍历
void InorderTraverse(BiTree T){
BiTree node=T;
if (node!=NULL){InorderTraverse(node->lchild);//若非空,则先遍历左孩子
visit(node->data);InorderTraverse(node->rchild);}}//遍历结点 //中序遍历非递归
void Inorder(BiTree T)
{ BiTree node=T; char stack[100]; int top = 0; while(node!=NULL)//判断结点是否为空
stack[top] =node->data;
{
while(stack[top]!='#')//不为空先遍历左孩子,再遍历右孩子 { top++; if(node->lchild) stack[top] = node->lchild->data; else stack[top] = '#';} top--; if(stack[top]!='#') { top--; visit(stack[top]); top++;
if(node->rchild)
stack[top] = node->rchild->data;
else stack[top] = '#';}}}
//后序遍历
void PostOrderTraverse(BiTree T)
{ if (T!=NULL)//判断是否为空的情况
{ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild);visit(T->data);}} void BiTreeDepth(BiTree T,int d)//求二叉树的深度
{ if(T)
{ BiTreeDepth(T->lchild,d+1); BiTreeDepth(T->rchild,d+1);}
else
{ if(d>depth)
depth = d;}}
void Child(BiTree T) { if(T)
{ if(T->data!=cur_e){ Child(T->lchild);Child(T->rchild);} else{printf(\左孩子为\
if(T->lchild) printf(\else printf(\空\\n\右孩子为\if(T->rchild) printf(\else printf(\空\\n\
int main()
{ BiTree T; CreateBiTree(T); BiTreeDepth(T,0);
if(!depth) printf(\树为空\\n\
else{printf(\后序遍历二叉树:\\n\ printf(\深度为%d\\n\ printf(\输入父亲结点:\\n\
printf(\中序遍历二叉树(非递归)\\n\InorderTraverse(T);printf(\
return 0;}
正在阅读:
算法与数据结构实验报告实验五03-03
iOS版疯狂填字答案攻略大全51-60关05-03
中关村软件园施工组织设计09-11
麻醉药品、精神药品使用管理制度,麻醉精神药品管理制度03-09
中考化学总复习分类专题训练周围的空气和水05-05
2021年学生观看《英雄之城》纪录片观后感心得八篇08-04
发挥党员模范作用02-17
有含义的女生英文名08-20
- 秦皇岛律师:盗窃案成功辩护词
- A Compare of Chinese and English Compounds
- 3203外科护理学历年真题
- 大数据对科学哲学的新挑战
- 38标热力施工组织设计
- 电火花放电加工工艺
- 神机妙算 软件 高级操作
- 黔东南州2012年教师素质提升工程培训学习心得
- 2012年自主招生安徽录取名单
- 北师大课标版七年级数学下册教案平方差公式(一)
- 教科版小学五年级语文上册期末试题
- 高级财务会计大作业 (2)
- 如何在自然课中搞好探究性实验教学
- 建筑材料习题答案 - 图文
- 2019年2018入党思想汇报1500字-word范文(7页)
- 《古诗三首》(1)
- 面对繁多的一种坚持:展望大学中的道德教育
- 恶劣天气下如何保障行车安全
- “一比一访三走进”教学设计
- 吉林省工业旅游发展研究
- 实验
- 数据结构
- 算法
- 报告
- 超声波探伤II级人员考试试题及解答
- 庆祝建党90周年文艺演出串词
- 江苏省六合高级中学2012届高三物理周作业(7)
- 社会主义核心价值观 - 图文
- 船舶机械液压系统漏油原因与解决方法研究
- 房地产大纲和参考文献
- 走进李清照的美丽情怀 - 语文 - 高中 - 王玉芝
- 常州市田家炳实验中学高三暑期调研测试物理学科试卷
- 雅思雅思教父刘洪波:旅游类雅思作文高分范文及点评
- 广东省自考混凝土及砌体结构 复习要点
- 特殊人群服务管理工作措施
- 实习指导教师指导过程记录课件 doc
- 2013二年级上册数学第四单元表内乘法一教学设计
- 东华服装材料学复习题
- 浅谈小学语文中儿歌的教学作用-教育文档
- 2015第一学期四年级语文上册期中试卷带答案 - 图文
- 环保节能免烧砖厂建设项目可行性研究报告
- 数据结构课程设计—校园导航报告
- 水泥稳定碎石施工技术交底()
- 第2章 变动成本法练习题(答案版)