《2023年数据结构实验报告4.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告4.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构实验报告班级：1 0 0 1 1 2 0 6 姓 名：邹维韬 学号：E-ma i l:日期：1 1.1 5实验题目：输入一棵二叉树，使用二叉链表结构存储二叉树，并用递归方法输出先序、中序、后序三种遍历结果。实验目的：纯熟掌握二叉树结构，能用二叉链表建立存储二叉树，并且可以用先序、中序、后序遍历揄出二叉树实验内容：用广义表揄入一个二叉树，用二叉链表创建二叉树，并用先序、中序、后序遍历输出。一、需求分析1 .本演示程序中，输入的二叉树是任意的不为空的二叉树，揄入形式为广义表形式的二叉树，输出为该二叉树的先序、中序、后序遍历揄出。2 .本程序可以实现给定广义表形式的二叉树的创建，以及实现该
2、二叉树的先序、中序、后序遍历输出。3.程序执行的命令涉及：(1 )输入广义表形式的二叉树(2)创 建 二 叉 树(3)先 序 递 归 遍 历 输 出(4)中序递归遍历输出(5)后序递归遍历输出4.测 试 数 据:输 入：(-(+(a,*(b,-(c,d),+(e,f )先序递归遍历输出：-+a *b -c d+e f中序递归遍历输出：a+b*c d-e+f后序递归遍历揄出：a b c d-*+e f +一二 概 要 设 计为了实现上述操作，应以二叉链表为存储结构。1.基本操作n o d e c r e a t e (c h a r a 2 0 )创建二叉链表v o i d p r e o r
3、d e r (n o d e *b t)先序递归遍历输出v o i d i n o r d e r (n o d e *b t)中序递归遍历输出void po s to r der(n ode*bt)后序递归遍历揄出v o id N RPreord e r(n ode*bt)2.本程序涉及五个模块(1)主程序模块(2)二叉树建立模块(3)先序递归遍历输出模块(4)中序递归遍历输出模块(5)后序递归遍历输出模块三具体设 计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法：画出函数的调用关系。1.元素类型，节点类型和指针类型t yp e def
4、 struct nod e(dc h a r d a ta;st r uct nod e*lc;st r uct n od e*rc;node;nod e*s maxsiz e ;int to p 1;node*p;node*b t ;2.每个模块分析(1)主程序模块i n t ma i n ()(n o d e *b t;c h a r b 2 0 ;p r i n tf (请输入二叉树：n )；s c a n f (%s,b);b t=c r e a t e(b );p r i n t f (该二叉树的先序递归遍历序列为：”)；p r e o r d e r (b t);p r i n t
5、 f (n )；-p r i n tf (该二叉树的中序递归遍历序列为：)；i n o r d e r (b t);叩 r i n i f(n)；叩r i n tf (该二叉树的后序递归遍历序列为：”)；e p o s t o r d e r (b t);p r i n t f (n );g e tc h a r ();o g e tc h a r ();r e t u r n 0;(2)二叉树建立模块n o d e r e a t e (c h a r a 2 O )(mo d e *p;i n t i=1;/*以广义表形式输入的二叉树第一个必为左括号*/n o d e *b t;&to p
6、+;p =(n o d e *)m a 1 I o c (si ze o f (n o d e);/*因是左括号，申请新节点*/p-l c=N U L L;/*左右孩子置空*/叩 r c=N U L L:b t=p ;/*使根节点指向新申请节点*/s t o p =p;/*将 指 针 入 栈*/o w h i I e (a i !=0 )/*字符数组读到 0 结束循环*/(i f (a i =()/*假如读到左括号*/i f (a i+1 !=/)/*假如左括号后边不是逗号，申请新节点，左右孩子置空，栈顶元素的左孩子指向新节点，指针入栈*/p二(n o d e *)ma H o c (s i
7、ze o f (n o d e);p -l c=N U L L;p-r c=N U L L;s to p -I c=p ;to p+;s to p =p:)e I se /*否则栈顶元素左孩子为空，为保持人栈出栈平衡，栈顶加一次*/(s to p -I c=N U L L;to p+;)e l s e i f (a i =二，)/*假如读到逗号，先出栈*/to p-；i f(a i +l !=)/*假如逗号后边不是右括号，申请新节点，左右孩子置空，栈顶元素的右孩子指向新节点，新 节 点 入 栈*/(p=(n o d e *)m a I I o c(si ze o f (n o d e );p-
8、l c-N U L L;p-r c=N U L L;s to p -r c=p;to p+;s to p =p;e l s e to p+;/*否则保持平衡入栈一次*/e l s e i f (a i =，)*)/*读到右括号，出栈，p等于栈顶元素*/(to p;p=s to p ;)e l se /*读到字符，p的d a ta为该字符*/g p -d a t a =a i;。i+;Ir e t u r n b t;(3)先序递归遍历输出模块v oid p reor d er(n od e*bt)i f(b t!:NULL)。print f(%c”,b t-d a t a);*preor d
9、er(bt-l c);pre o rd e r(bt-rc);。)(4)中序递归遍历输出模块void in o rder(n ode*bt)(n f(b t!=NULL)(n order(bt-1 c);p r i ntf(%c”,bt-d a t a);inorder(b t-rc);)(5)后序递归遍历输出模块v o id postor d e r(no d e*bt)(i f(bt!=N ULL)(0Pos tor d er(b t-l c);po s torder(bt-r c);pri n tf(%c,bt-d ata);)四 使 用 说 明、测试分析及结果1.测试结果输 入:(-(+(a,*(b,-(c,d),+(e,f)先序递归遍历输出：一+a*bc d+e f中序递归遍历输出：a+b*cd-e 4-f后序递归遍历输出：abc d-*+e f+-3.运营界面，F:编程V I 叉 廊 D e b u g 二叉树.e xe-t I B l g l五、实脸总结本次程序由于提前在纸上设计了算法，编写了主体程序，所以编写比较顺利，在编写后序非递归遍历时由于算法问题迟迟难以实现，通过改善，算法对的，顺利实现，通过本次编程，熟悉了二叉树，可以纯熟使用二叉链表建立二叉树，可以实现二叉树的先序、中序、后序遍历输出。教师评语:实验成绩: