版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实验三 二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容问题描述建立一棵二叉树,试编程实现二叉树的如下基本操作:1. 按先序序列构造一棵二叉链表表示的二叉树T;2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列;3. 求二叉树的深度/结点数目/叶结点数目;(选做)4. 将二叉树每个结点的左右子树交换位置。(选做) 基本要求从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),测试数据如输入:ABCDEGF(其中表示空格字符) 则输出结果为 先序:ABCDEGF 中序:CB
2、EGDFA 后序:CGEFDBA层序:ABCDEFG选作内容采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌握二叉树的各种遍历算法的实现。一 实验分析本次试验是关于二叉树的常见操作,主要是二叉树的建立和遍历。二叉树的遍历有多种方法,本次试验我采用递归法,递归法比较简单。 二 概要设计功能实现1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树2.int PreTravel(BiTree &T) 前序遍历3. int MidTravel(BiTree &
3、;T) 中序遍历4.int PostTravel(BiTree &T) 后序遍历5.int Depth(BiTree &T) /计算树的深度6.int howmuch(BiTree T,int h) 采用树节点指针数组,用于存放遍历到的元素地址,如果有左孩子,存入地址,j加一 ,否则没操作,通过访问数组输出层次遍历的结果。k计算叶子数,j为总节点。 H=0printf("%d", j)h=1真printf("%d",k)h=2for(i=0;i<j;i+)printf("%c",Qi->data)print
4、f("参数错误")真真真假假假假7. int exchang(BiTree &T) 交换左右子树,利用递归,当有左右孩子时才交换三 详细设计#include<stdio.h>#include<stdlib.h>typedef struct BiTNodechar data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;int CreatBiTree(BiTree &T)/先序法创建二叉树char ch;if(ch=getchar()=' ')T=NULL;elseT=(
5、BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(1);T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);return 0;int PreTravel(BiTree &T)/前序遍历if(T) printf("%c",T->data);PreTravel(T->lchild);PreTravel(T->rchild);return 0;int MidTravel(BiTree &T)/中序遍历if(T) MidTravel(
6、T->lchild);printf("%c",T->data);MidTravel(T->rchild);return 0;int PostTravel(BiTree &T)/后序遍历if(T) PostTravel(T->lchild);PostTravel(T->rchild);printf("%c",T->data);return 0;int howmuch(BiTree T,int h)BiTNode *Q100;/树节点指针数组,用于存放遍历到的元素地址if(T=NULL)printf("空
7、的二叉树n");Q0=T; /存入树根int i,k=0;int j=1; /j为总节点for(i=0;i<j;i+)if(Qi->lchild!=NULL) /如果有左孩子,存入地址,j加一 ,否则没操作Qj=Qi->lchild ;j+;if(Qi->rchild!=NULL) /如果有右孩子,存入地址,j加一 ,否则没操作Qj=Qi->rchild ;j+;if(Qi->lchild=NULL&&Qi->rchild=NULL)k+; /计算叶子数if(h=0)printf("%d", j);else
8、 if(h=1)printf("%d",k);else if(h=2) for(i=0;i<j;i+)printf("%c",Qi->data);else printf("参数错误");return 0;int Depth(BiTree &T) /计算树的深度 int lh , rh ; if( NULL = T ) return 0 ; else lh = Depth( T->lchild ) ; rh = Depth( T->rchild ) ; return ( lh > rh ? lh :
9、 rh ) + 1 ; int exchang(BiTree &T)/交换左右子树 if(T != NULL) if(T->lchild!=NULL&&T->rchild!=NULL)/当有左右孩子时才交换char t;t=T->lchild->data;T->lchild->data=T->rchild->data;T->rchild->data=t; /交换数据exchang(T->lchild);/ 递归调用 exchang(T->rchild); return 0; int choose(B
10、iTree T) /功能选int a;scanf("%d",&a);if(a=1)printf("先序遍历:");PreTravel(T);else if(a=2)printf("中序遍历:");MidTravel(T);else if(a=3)printf("后序遍历:");PostTravel(T);else if(a=4)printf("层序遍历:");howmuch(T,2);else if(a=5)printf("总节点数:");howmuch(T,0);e
11、lse if(a=6)printf("总叶子数:");howmuch(T,1);else if(a=7)printf("树的深度:");printf("%d",Depth(T);else if(a=8)printf("交换前n");howmuch(T,2);exchang(T);printf("交换后n");howmuch(T,2);else if(a=9)exit(1);else printf("没有这个操作n"); printf(" 操作完成,请输入下一个操作n");choose(T);return 0;int main() /主函数printf("-二叉树的基本操作-n");printf("请先建立二叉树,按先序的方式输入如果数据为空输入空格n");BiTree T; /定义二叉树,初始化CreatBiTree(T); choose(T);return 0;四 用户手册根据程序的提示按先序输入二叉树,如果数据为空输入空格,然后回车,输入你要进行的操作的序号。1.先序遍历、2中序遍历、3 后序遍历 、4层次遍历、5总节点数、6总叶子数、7树的深度、8交换左右子树、9结束操作五 实验总结通过
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 配餐协议书范文2024年
- 沪教版九年级上册《1.2 化学研究些什么》2023年同步练习卷
- 扁担那头的父亲(2023年山东青岛中考语文试卷记叙文阅读题及答案)
- 个人珠宝抵押合同模板
- 合伙入股机械合同模板
- 同城加工转让合同模板
- 幼小衔接数学练习题
- 家谱印刷合同协议书
- 医院人事劳务合同模板
- 临时租用厂房合同模板
- Unit 6 Meet my family 单元整体教学说课(教学设计)-2024-2025学年人教PEP版英语四年级上册
- 2024年上海烟草集团限责任公司招聘24人高频考题难、易错点模拟试题(共500题)附带答案详解
- 2024年五年级英语上册 Unit 3 Do you want some rice教案 湘少版
- 2024-2025学年七年级道德与法治上册 第一单元 单元测试卷(人教陕西版)
- 智能农机可行性分析报告
- 商务数据分析与应用 课程标准
- 八年级语文上册 第一单元 单元测试卷(人教广东版 2024年秋)
- 2024年中国残联所属事业单位面向社会招聘工作人员30人历年(高频重点提升专题训练)共500题附带答案详解
- 汽车汽车制造行业数据分析与管理
- 中医更年期综合征课件
- 2024年江西省中考生物试卷附答案
评论
0/150
提交评论