2023年数据结构实验报告4.docx

《2023年数据结构实验报告4.docx》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告4.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实险报告班级：100 1 1206 姓名：邹维超 学号；E-mail:日期：11.15实脸题目：输入一棵二叉树，使用二叉链表结构存储二叉树，并用递归方法输出先序、中序、后序三种 遍历结果。实脸目的：纯熟掌握二叉树结构，能用二叉性表建立存储二叉树，并且可以用先序、中序、后序遍历输出 二叉树实验内容：用广义表榆入一个二叉树，用二叉链表创建二叉树，并用先序、中序、后序遍历榆出。一、需求分析.本演示程序中，输入的二叉树是任意的不为空的二叉树，榆入形式为广义表形式的二叉树，椅出为该 二叉树的先序、中序、后序遍历输出。1 .本程序可以实现给定广义表形式的二叉树的创建，以及实现该二叉树的先序、中序、

2、后序遍历输出。2 .程序执行的命令涉及：(1 )输入广义表形式的二义树(2)创建二又树(3)先序递归遍历输出(4)中序递归遍历榆出(5)后序 递归遍历输出.测试数据：输入:(-(+(a, *(b, -(c, d), +(e, f )先序递归遍历榆出：-+a*b-cd+cf中序递归遍历揄出：a+b*cd-e+f后序递归遍历榆出：ab c d-*+e f + 一二概要设计为了实现上述操作，应以二叉链表为存储结构。1 .基本操作node * create (char a20)创建二叉性表void p r eor d e r ( n ode *b t)先序递归遍历榆出void i no r der(

3、n ode *bt)中序递归遍历榆出void po s to r der (n ode *bt)后序递归遍历揄出void N RPrcord e r ( n ode *bt)2 . 本程序涉及五个模块(1)主程序模块(2)二叉树建立模块(3)先序递归遍历输出模块(4)中序递归遍历输出模块(5)后序递归遍历输出模块三具体设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要 写出伪码算法；西出函数的调用关系。1 .元素类型，节点类型和指针类型t ype def struct nod e(c h a r d a ta;st r uct nod e *lc;s

4、t r uct n od e *rc；Inode:nod e * s maxsiz e：int top -1;node *p;node *b t ;.每个模块分析(D主程序模块int main 0(ode 夫bt;char b 20;printf (请榆入二叉树： n ;s ca n f ( %s*, b);bl= c r e a t e( b );-print f (该二叉树的先序递归遍历序列为：*);pr e order (bt);p rin t f ( n );printf (该二义树的中序递归遍历序列为：”)； inord e r (bt);p ri n tf (* n *);叩rin

5、tf (该二叉树的后序递归遍历序列为：”)：p o s t o r der (bt):pri n t f C n );getchar 0 ;ogetcha r ();ret u r n 0;(2)二叉树建立模块mode *p;mode *p;/大以广义表形式输入的二叉树第一个必为左括号*/no d e *c r eat e (ch a r a2O)=1 ；n o de *bt;top+;/*因是左括号，申请新节点*/p = ( n od e ) m a 1 I oc (si ze o f ( n ode)；P-1 c=NULL;左右孩子置空*/ rc=NULL;bt= p ;/大使根节点指向新

6、申请节点大/s t op =p：/*将指针入栈*/ou-hi I e (ai! = 0)/*字符教组读到0结束循环*/i f(ai = ()/*假如读到左括号*/ i f (a i +1!=/) /*假如左括号后边不是逗号，申请新节点，左右孩子置空，栈顶元素的 左孩子指向新节点，指针入栈* /(p= (node *)ma Hoc ( s izeof (node)：p lc=NULL;p-rc=NULL;stop- I c= p ;top+; stop =p;)e I se/*否则栈顶元素左孩子为空，为保持人栈出栈平衡，栈顶加一次火/(stop- I c = NULL;top+;/ *假如读到逗

7、号，先出栈*/top；if(a i + l!= ),)/*假如逗号后边不是右括号，申请新节点，左右孩子置空，栈顶元素的右孩子指向新节点，新节点入栈*/(p= (node *) ma I I oc(sizeof ( n od e );p-lc=NULL：p r c=NULL;stop-rc=p;top+ + ：stop=p;)else top+;/*否则保持平衡入栈一次*/)else if (ai=)/*读到右括号，出栈，p等于栈顶元素*/(top;p=stop;)else/*读到字符，p的data为该字符*/8 p -dat a = a i ;。i +;)r e t u rn b t ;(3)

8、先序递归遍历输出模块v oid p reor d er( n od e *bt)i f (bt! =NULL)， print f (飞c ”, b t- data);*preor d er (bt -lc);pre o rd e r (bt-rc)；(4)中序递归遍历榆出模块void in o rder ( n ode *bt)(if (bt !=NULL)(i n order (bt-l c );p r i n tf (*%c”, bt- d ata);inorder (bt-rc);，(5)后序递归遍历输出模块v o id postor d e r (no d e *bt)(i f (bt

9、! =N ULL)(*p o s tor d er (bt-l c );po s tordcr(bt- r c);pri n tf ( %c -data)： )四使用说明、测试分析及结果1.测试结果榆入：(+ (a, *( b , (c, d ) , + (e, f )先序递归遍历揄出： 一+a*bcd+ef中序递归遍历榆出：a+b*cd- e + f后序递归遍历输出：abc d -*+e f +-3.运营界面叫即口际Debug二叉网exe-13回树,先中后先中后 ，-jp1Y2,J 二勺】Ti二fs-T 人d叉叉叉叉叉叉 输,先中后先中后 ，-jp1Y2,J 二勺】Ti二fs-T 人d叉叉叉叉叉叉 输 历历历 历历历遍富归归 fs归递普d .1 d d .1 d五、实验总结本次程序由于提前在纸上设计了算法，编写了主体程序，所以编写比较顺利，在编写后序非递归遍历时由于 算法问题迟迟难以实现，通过改善，算法对的，顺利实现，通过本次编程，熟悉了二叉树，可以纯熟使用二叉 链表建立二叉树，可以实现二叉树的先序、中序、后序遍历输出。教师评语:实验成绩: