《2023年数据结构与算法实验报告二叉树.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构与算法实验报告二叉树.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、沈阳工程学院学 生 实 验 报 告（课程名称：数 据 结 构 与 算 法）实 验 题 目:_ _ _ _ _ _ _ _ _ _ 二叉树_ _ _ _ _ _ _ _ _ _ _ _ _ _班 级 软 本 1 1 1 学 号 姓名吴月芬地 点 F 座 606 指 导 教 师 姜 柳 祝 世 东实验日期：2023年 10月2 5 日一、实验目的1.掌握二叉树的结构特性，以及各种存储结构的特点及合用范围。2.掌握用指针类型描述、访问和解决二叉树的运算。二、实验环境Turbo C 或是 Visu a 1 C+三、实验内容与规定1.输入字符序列，建立二叉链表。2.按先序、中序和后序遍历二叉树(递归算法
2、)。3.按某种形式输出整棵二叉树。4.求二叉树的高度。5.求二叉树的叶结点个数。6.互换二叉树的左右子树。7.借助队列实现二叉树的层次遍历。8.在主函数中设计一个简朴的菜单，调试上述算法，规 定1-3必做，4-7为选做。为了实现对二叉树的有关操作，一方面要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是运用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号(按满二叉树编号)和数据同时给出：(序号,数据元素)。图4.1所示二叉树的输入数据顺序应当是：(l,a),(2,b),(3,c),(4,d),(6,e),(7,f),(9,g),(1 3,h).另一种算法是主教材中介绍的
3、方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。这时，图4.1所示二叉树的输入数据顺序应当是:abd#g#c e#h#f#。若当前数据不为“#，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。四、实验过程及结果分析(-)二叉树1.二叉树的综合程序源代码如下所示：#include#i n c 1 u d e#de fine NULLOstruc t bi t ree(c h ar da t a;s tr u ct bi t r ee*1 c hild,*rchi 1 d;struct b
4、i t ree*creat e b i t ree_l(struct b itre e*t)(int c h;osca n f(d”,&ch);i f(c h=0)0(NULL;。e Ise0(t-da t a=c h；t-lchild=(s t r u ct b i t r e e*)m a lloc(sizeo f(s truct bi tree);。t-lch i 1 d=c r eate b itree_l(t-lc h i 1 d);。t-rchild=(stru c t bit r ee*)mal 1 o c(si z eof(st r u c t bit r ee);t-rchi
5、ld=crea t e b it r ee_ 1 (t-rc h il d);)r e t u rn t;)str u ct b i t ree*cr e a tebit r ee_2(s t rue t b i tre e*t)(i nt ch;oscanf(n%dH,&ch)；if(c h=0)(t=NULL;)elses(s t-l c hild=(s t r uct bitre e*)m a llo c(si z eof(struc t bit r ee);o t-lc h i 1 d=createb i tree_ 2(t-lchild);t-data=ch;t-rchild=(st
6、ru c t b i tree*)ma 1 1 oc(si z eof(struc t bit r e e);t rc h ild=cr e atebit r e e _2(t-r c hil d);r eturn t;vo i d pre o rder_ 1 (st r uc t bit r e e*T)(if(T!=NULL)。8 pri n tf(d ttn,T d ata);p r eor d e r_l(Tlch i Id);pr e order_l(T-r child)；)v o id p r eord e r_yezi(s t rue t b i t r e e*T)(i f(T
7、!=NU L L)(。if(T-1 chi 1 d=N U LL&T-r c hild=NULL)只输出叶子节点g printf(H%dtt T-dat a);pr e ord e r_ 1(T-1 c hil d);p r e o rder_l(T-rchild);v oid i n o rd e r_ l(s t ru c t bitree*H)if(H)(inorder_ 1 (H-lchi 1 d);pr i ntf(%dtt,H-data)；in o rder_ l(H-rc h i 1 d);)vo i d preorder_ 2(s truct bi t r e e*p)(str
8、uct bit r e e*s 1 0 0；in t t op=-1;whil e(p!=NU L L|t o p!=-l)。w h ile(p!=NULL)8 t O P+；8 S t O p=p；8 p r intf(%d tt M,p-dat a);p=p-lchild;00 if(top!二一1)6 p=sto p;“o p；8 p=p-rchild;v oid p r eor d e r _ y ez i _2(stru c t b i tree*p)(s tr u ct bitree*s 1 0 0；。i nt top=-l;?wh i 1 e(p!二NULL|t o p!=-1)
9、twhi 1 e(p!=NULL)(00 top+；stop=p;if(p-1 c hild=NULL&p-rc h i ld=NULL)/只输出叶子节点p r i n t f(%d t t,p d a t a);p=p 1 child；0)i f(t o p!=-l)P=S Eto p;t o p-；8P=p-rchild；)v o id i n order_ 2(s t r u ct b i t r ee*p)(str u ct bitr e e*s L100；in t t o p-1;while(p!=NULL|t op!=-l)8vhile(p!=NULL)bb 84Op+；8 S t
10、o p=p;p=p-lch i 1 d;0)-if(to p!=-l)。8 p=stop；8 t Op；8 P r in t f（%dt t,p-data）;p=p-rch i Id;6）void menu_l（）（op r i n t f（nt*菜 单*oprintf（t 1.树的建立n）;printf（t2.树的遍历n）；p r i ntf（tO.退 出n ）;void men u _ 2（i n t n）（if（n=l）（a p r intf（nt*菜 单*n）；。p rintf（ntl.树的递归的先序建立 n）;。printf（n t2.树的递归的中序建立 n）;P rint f（n
11、t 3.树的非递归的先序建立 n）;prin t f（nt4.树的非递归的中序建立n）;）i f（n=2）p r intf（n t*菜 单*oo p r i n tf（nt 1.树的递归的先序遍历n）;p r intf（nt2.树的递归的中序遍历n ）;。叩 rintf（n t3.树的非递归的先序遍历n）;8P r intf（nt4.树的非递归的中序遍历n）；pri n tf（nt5.树的递归的先序遍历叶子节点n）;。p rin t f（nt 6.树的非递归的先序遍历叶子节点 n ）;）void main()(struct bi t ree*H；“ntn,m；oH=(st r u c t b
12、i t ree*)ma 1 lo c(si z eo f(st r uc t b i tr e e)；dogmen u _1();oosca n f(d”,&n);sif(n 2|n i f(m=5)。p reorder_yezi(H);。3 i f(m=6)皿叩r e or d e r y e zi 2(H);6)whi 1 e(n!=O);2.运营过程二叉树递归的先序建立过程如图1.1所示。菜*120X立历-M-w注的的*8X共 关*.关 菜 单 M X.W M M X1.树的递归的先序建立2.树的递归的中序建立3.树的非递归的先序建立4.树的非递归的中序建立11200300图1.1先序建
13、立二叉树二叉树的递归的先序遍历如图1.2所示。-D:5SUgSt3Debuqt59a)iS5.exe菜*120立历的的*菜 单 *1 .树的递归的先序遍历2.树的递归的中序遍历3.树的非递归的先序遍历4.树的非递归的巾序遍历5.树的递归的先序遍历叶子节点6.树的非递归的先序遍历叶子节点112 3图1.2递归先序遍历二叉树的递归的中序遍历如图1.3所示。图1.3递归的中序遍历二叉树的非递归的先序遍历如图1.4所示。图 1.4 非递归的先序遍历二叉树的非递归的中序遍历如图1.5 所示。图 1.5 非递归的中序遍历二叉树的递归的先序遍历叶子节点如图1.6 所示。图 1.6递归的先序遍历叶子节点二 叉 树 的 非 递 归 的 先 序 遍 历 叶 子 节 点 如 图 1.7 所 示。图 L 7 非递归的先序遍历叶子节点结 束 程 序 操 作 如 图 1.8 所 示。，D:程序邀据结构Debugt55的综合程序exe0Press*立历X1.2.0.any key to continue图 1.8 结束程序五、成绩评估优良中及格不及格出 勤内 容格 式创 新效 果总 评指导教师：年 月 日