版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、真诚为您提供优质参考资料,若有不当之处,请指正。实验报告课程名称数据结构实验名称二叉树的遍历日期2013/05/30学生学号B11050226姓名枯天蝎班级B110502实验目的:掌握二叉树的结构特征,掌握用指针类型描述、遍历二叉树的运算。实验条件:电脑一台 Vc+6.0实验内容与算法思想:内容:P213 实习题 1建立一棵用二叉链表方式存储的二叉树,并对其进行遍历(先序、中序、和后序),打印输出遍历结果。基本要求如下:从键盘接受输入线序序列,以二叉链表作为存储结构,建立二叉树(以先序来建立)并对其进行遍历(先序、中序、后序),然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。算法思想
2、:定义二叉树结构体类型时,也定义了一个顺序栈结构体类型,用以辅助完成二叉树的非递归遍历。由键盘输入二叉树先序序列,用扩展线序序列函数接受并创建二叉链表。遍历前先判断二叉树是否为空,若为空,执行空操作;否则依次执行各遍历函数相应操作。先序遍历算法思想,先访问根节点,然后按先序遍历左子树,再按先序遍历右子树。中序遍历算法思想,先按中序遍历左子树,再访问根节点,然后按中序访问右子树。后序遍历算法思想,先按后序遍历左子树,接着按中序遍历右子树,然后访问根节点。运行结果:递归算法: 非递归算法:实验总结(结论或问题分析):通过实验,加深了对C语言尤其是函数调用部分的认识和掌握。没有找到在实验运行结果上明
3、确区分递归算法实现的遍历和非递归算法实现的遍历的方法。实验成绩任课教师签名张红霞附:源程序:递归算法程序#include #include #include #define maxsize 100#define FALSE 0#define TRUE 1typedef struct node /二叉树结构体类型定义char data;struct node *lchild;struct node *rchild;bitnode,*bitree;/*扩展先序序列创建二叉链表*/void cteatebitree(bitree *bt)char ch;ch=getchar();if(ch=.)*b
4、t=NULL;else *bt=(bitree)malloc(sizeof(bitnode);(*bt)-data=ch;cteatebitree(&(*bt)-lchild);cteatebitree(&(*bt)-rchild);/*先序递归遍历*/void preorder(bitree root)if(root!=NULL)printf(%c ,root-data);preorder(root-lchild);preorder(root-rchild);/*中序递归遍历*/void inorder(bitree root)if(root!=NULL)preorder(root-lchi
5、ld);printf(%c ,root-data);preorder(root-rchild);/*后序递归遍历*/void postorder(bitree root)if(root!=NULL)preorder(root-lchild);preorder(root-rchild);printf(%c ,root-data);void main()bitree bt;cteatebitree(&bt);printf(先序递归遍历序列:n);preorder(bt);printf(n);printf(中序递归遍历序列:n);inorder(bt);printf(n);printf(后序递归遍历
6、序列:n);postorder(bt);printf(n);非递归算法程序#include #include #include #define FALSE 0#define TRUE 1#define maxsize 100typedef struct node /二叉树结构体定义char data;struct node *lchild;struct node *rchild;bitnode,*bitree;typedef struct /顺序栈结构体定义bitree elemmaxsize;int top;seqstack;int push(seqstack *s,bitree x) /入
7、栈if(s-top=maxsize-1)return(FALSE);s-top+;s-elems-top=x;return(TRUE);bitree pop(seqstack *s,bitree x) /出栈if(s-top=-1) return NULL;elsex=s-elems-top;s-top-;return x;int gettop(seqstack *s,bitree *x) /读取栈顶元素if(s-top=-1) return FALSE;else*x=s-elems-top;return TRUE;void createbitree(bitree *bt) /扩展先序序列创建
8、二叉链表char ch;ch=getchar();if(ch=.)*bt=NULL;else *bt=(bitree)malloc(sizeof(bitnode);(*bt)-data=ch;createbitree(&(*bt)-lchild);createbitree(&(*bt)-rchild);void preorder1(bitree root,seqstack s) /先序遍历bitnode *p;p=root;while(p!=NULL|!(s.top=-1)while(p!=NULL)printf(%c,p-data);push(&s,p);p=p-lchild;if(!(s.
9、top=-1)p=pop(&s,p);p=p-rchild;void inorder1(bitree root,seqstack s) /中序遍历bitnode *p;s.top=-1;p=root;while(p!=NULL|!(s.top=-1)if(p!=NULL)push(&s,p);p=p-lchild;elsep=pop(&s,p);printf(%c,p-data);p=p-rchild;void postorder1(bitree root) /后序遍历bitnode *p,*q;seqstack s;q=NULL;p=root;s.top=-1;/printf(%c,p-data);while(p!=NULL|!(s.top=-1)while(p!=NULL)push(&s,p); p=p-lchild;if(!(s.top=-1)gettop(&s,&p); if(p-rchild=NULL)|(p-rchild=q)printf(%c,p-data);q=p;p=pop(&s,p);p=NULL;else p=p-rchild;void main() printf(先序序列创建二叉树n);seqstack s;s.top=-1;bitree root;create
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 工装拆除合同
- 江苏省住宅装修合同
- 马桶维修合同范本
- 数学:2.1.2整式复习课件(人教新课标七年级上)
- 小学人教英语上下册Unit-4-Time-Lesson-3-课件3公开课教案教学设计课件测试卷练习卷
- 人教版四年级语文上册《语文园地五》(完整课件)-课件
- 部编版语文二年级第二学期:第4课-邓小平爷爷植树-第2课时课件
- 做账实操-农民专业合作社的财务管理制度
- 安徽省屯溪一中2022年物理高一下期末联考模拟试题含解析
- 安徽省干汊河中学2021-2022学年物理高一下期末统考模拟试题含解析
- 鹿产品采购合同范本
- 神经调控在精神疾病治疗中的潜力
- GB/T 150.1-2024压力容器第1部分:通用要求
- 2024年内蒙古呼和浩特市中考物理试题(解析版)
- 语文-安徽省安徽六校教育研究会2025届高三年级入学素质测试(开学联考)试题和答案
- 仪器仪表制造市场调研及行业前景预测报告(参考范文)
- 2024江苏“学习达人”挑战赛题库(附答案)
- 肥胖患者的长期体重管理及药物临床应用指南(2024版)
- JGT503-2016承插型盘扣式钢管支架构件
- 2024年质量知识竞赛考试题库500题(含答案)
- CJT 516-2017 生活垃圾除臭剂技术要求
评论
0/150
提交评论