二叉树实验报告总结

1 / 49 二叉树实验报告总结 过程控制软件技术基础课程实验报告 姓名： 学号： 1008180230 指导教师： 戚风亮 任登凤 1. 实验目的 通过自主设计实验，掌握过程控制软件的基础理论知识，本实验具体表现为二叉树的建立和遍历，为以后计算机控制的软件设计提供基础。提高逻辑思维方式，培 养应用可视化编程工具开发计算机软件的能力。 2. 实验内容 2 / 49 本文主要介绍二叉树的建立和遍历。所使用的编程软件为matlab2016版本，主要使用其中的 GUI功能，完成可视化界面操作。从更直接的角度感受二叉树的建立和遍历。 二叉树的建立和遍历包含两个方面：建立和遍历。其中建立包括输入二叉树的每一个结点的元素，以及二叉树每一个结点的随机存储地址。与此同时，更重要的是创建两个指针域：左指针域 L 和右指针域 R，在本次实验中，采用产生随机数的方式生成随机存储地址，采用两个数组代表两个指针域。二叉树的遍历采用递归函数的方式，本实验中采用三个函数Front,Middle,Behind 分别实现前序、中序以及后序的功能。 界面的设计： 软件的设计界面见图 1。 图 1 软件的总体界面 界面中主要包括以下几个部分： a. 深度 m 的输入框： 此输入框在输入某个数值后将决定二叉树的深度，值得注意的是：本次实验中的设计标准为 4 层，3 / 49 即最大为 4层。当输入数值大于 4 时，将提示出错，并要求重新输入。 图 2. 出错消息提醒框 同时，当 输入层数小于 4 时，软件将自动消去最后的那几层结点。 图 3. 软件自动按要求生成二叉树层数 b. 二叉树结点元素输入框： 二叉树结点元素输入框用于输入每个结点的元素值，同时 按照二叉树的规则，每一个根结点对应至少两个子结点，即如果根结点的值为空，则它的子结点输入框不得输入，即其enabled 属性为 false。当根结点输入值后，子结点输入框即可输入。 与此同时，由于 matlab 的 GUI 中，没有向 VB 中的 line 控件，所以必须用代码加以实现，在 matlab中，函数 annotation可 以 用 来 画 箭 头 ， 具 体 如 下 ： arr(1,1)=annotation(gcf,arrow, , ); 4 / 49 其中，后面的两组数据为坐标值， arr(1,1)表示第一排的第一个箭头，在 matlab 中的每个图象都对应一个句柄值，这样，所有箭头都对应各自的句柄值， 进 而形成一个所有箭头的数组，便于管理每一个图像。 图 4. 根结点输入后子结点方可输入 c. 控制按钮：生成二叉树 生成二叉树的主要功能是，将没有输入值的结点以及箭头隐藏，同 时为每一个结点分配随机的存储地址，进而形成左右指针域。 图 5. 最终形成的二叉树 如图 5所示，在每个结点的左边有一个数字，即代表该结点在内存中的随机地址。该数字由 matlab 内部函数 randperm产生。如： data=randperm(5) 即产生 1 5的 5 个随机数，并赋值给5 / 49 数组 data。 本次实验中，最关键的是左右指针域的建立，即 左右 数组的建 立。 为实现这 个功 能，创建 函数L,R,VV=point。 其中 L表示左指针域， R代表右指针域， VV代表值域。至此，二叉树已完全建立。 d. 重置按钮：将界面设置为初始状态 e. 退出按钮：退出系统 f. 前序按钮：生成二叉树的前序遍历。 3. 软件总体结构、程序流程图 软件总体结构： 软件界面总体上有三个部分： 输入界面 二叉树总体结构 控制界面二叉树最终形成 6 / 49 结果界面二叉树遍历显示 软件程序总体上有以下几个方面： a. 名为 gouzao的函数：该函数输入参数为输入框的坐标，返回该输入框的特点。即只有该输入框存在值时，它对应的子结点输入框方可输入。这里所谓的存在值的相反面是 “ 非空 ” ，而并非 “ 空字符串 ” 。 b. 名为 point 的函数：该函数没有输入参数，但可以返回左 指 针 域 、 右 指 针 域 以 及 值 域 。 其 调 用 格 式 为L,R,VV=point。 c. 名为 Front、 Middle、 Behind 的函数：这三个函数分别返回前序遍历、中序遍历、后序遍历的结果。 d. 名为 Erchashu 的函数：该函数为 matlab 的 GUI 中系统自动生成的 m文件格式的函数。它是整个系统的中枢，整合了以上的所有函数。 程序流程图： 7 / 49 实 验 报 告 课程名称 算法与数据结构 专 业 学号 姓名 实验日期 算法与数据结构实验报告 一、实验目的 1.了解二叉树的结构特点及有关概念，掌握二叉树建立的基本算法 2.了解二叉树遍历的概念，掌握遍历二叉的算法 3.进一步掌握树的结构及非线性特点，递归特点和动态性。 8 / 49 二、实验内容 二叉树的实现和运算 三、实验要求 1用 C+/C 完成算法设计和程序设计并上机调试通过。 2撰写实验报告，提供实验结果和数据。 3分析算法，并简要给出算法设计小结和心得。 四、算法步骤 用户以三元组形式输入二叉树的结点元素及其位置关系，建立二叉树，并打印输出该二叉树。 用户输入选择结点，程序调用 BiTNode* Find Node(char tag, BiTNode* node)函数，返回子树的根结点，然后调用BiTreeDepth(BiTree T)函数，求出子树的深度，并输出该值。 9 / 49 3.用户可以选择是否继续执行程序，若继续，则输入 1，否则输入 0，结束程序。 五、主程序代码： int main(void) BiTree T; TElemType e1; char node; / node 为用户选择输入的结点 / int b,choose; / b 为以选定结点为子树的深度， choose为实现多次选择输入的标志 / BiTNode* a; / a 为选定结点为子树的根结点 / choose=1; / 多 次选择的标志，当 choose 为 1时运行程序，为 0 时结束程序 / InitBiTree(T); 10 / 49 printf(构造空二叉树后 ,树空否？ %d(1:是 0:否 ), 树的深度 =%dn,BiTreeEmpty(T),BiTreeDepth(T); e1 = Root(T); if(e1 != Nil) #ifdef CHAR printf(二叉树 的根为 : %cn,e1); #endif #ifdef INT printf(二叉树的根为 : %dn,e1); #endif else 11 / 49 printf(树空，无根 n); /三元组构建二叉树 string x; print ACR!n); GetUserWord(x); while(x!=end) AddNode(T, x0, x1, x2); GetUserWord(x); /输出树 PrintTreeLevel( T ); /以三元组形式输入任意二叉树，求以任意一选定结点为子树的深度。 while(choose) / 实现多次选择输入 / 12 / 49 printf(Please select a node: ); fflush(stdin); scanf(%c,&node); a= FindNode(node,T); / a 为生成子树的根 / b=BiTreeDepth(a); printf(the Depth of BiTree is : %dn,b); printf(nif you want to cointue choose 1,else choose 0: ); fflush(stdin); scanf(%d,&choose); 13 / 49 DestroyBiTree( T ); return EXIT_SUCCESS; 六、心得体会 树是常用的数据结构。通过实验加深了我对树的遍历的认识，巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。 通过实验，有如下几点收获 和体会： 1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。 2、编程需要有耐心，尤其实在单步调试的时候，更是马虎不得，有时候关键就是那么一步，错过了就得从头来过了。编程也需要勇气，要勇于发现自己的错误， 也要勇于推翻自己之前的思路，要坚信 “ 没有最好，只有更14 / 49 好 ” 。编程，最好是一鼓作气，得天天 “ 摸摸 ” 它，时时想着它，要是过一阵再去碰它那就得先去读懂自己的程序了，一切的一切几乎都得从头开始。编程需要细心，有时一个不注意小错误就能引出大问题。编程也需要规范，不仅为了他人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善。 3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的设计也很重要。 4.以前在学 C语言时总觉得函数的递归调用是一样很复杂的算法，经常会理解不了而导致编程的错误。但在这次实验中，二叉树的先序、中序与后序的输出都用了递归算法。而且用起来并不复杂，这使我更进一步学习理解了函数的递归调用并得到灵活的运用。 经过 本次实验基本上解决的一些所遇到的问题，我对二叉树的结构等有了较为深入的理解。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步。 算法与数据结构实验报告 二叉树 15 / 49 课程名称：算法与数据结构 实验项目名称：满二叉树的建立与遍历 实验时间： 2016年 11月 29日 班级：电科 1301 姓名：侯炜 学号： 1402130126 实验目的：熟悉使用线性表结构，设计并理解多项式算法。 实验环境： Visual C+， win7 实验步骤： 一建立基本数据结构及程序架构 二设计 多项式各类操作的算法 三调试程序，修改错误 四总结得失 实验结果：成功使用中序输入建立二叉树并进行相应的遍历16 / 49 输出。 实验心得： 队列结构作用之一：用于储存 “ 临时数据 ” 以便后续输出 满二叉树是仅仅输入一次遍历顺序就得出结果的先决条件 具体实验步骤： 一建立基本数据结构及程序架构 数据结构 确定所需要的对二叉树进行抽象的数据类型：树节点。建立数据结构如下： /-数据结构 typedef struct treenode char data; struct treenode* ltree; 17 / 49 struct treenode* rtree; Tnode; /- 主程序架构 建立了一个全局变量数组 queue用作队列，函数指针 fp用以调用操作函数， scree100数组用以储存输入的字符串。主要函数声明如下： /- Tnode* finit(Tnode*tf,int flo);/中序建立 void transver(Tnode* tf,int flo,fp kf,int n);/层序遍历 tf 为树节点 flo 为层数 kf 为回调函数 n 为标识层数： 0为全部遍历 其他 n为输出第 n层 void ordtra(Tnode* tf,fp kf,int flo);/先序遍历 void follow(Tnode* tf,fp kf,int flo);/后序遍历 18 / 49 Tnode*pus_pop(Tnode*tf,int k);/队列操作函数： k=0 时为出队 1为入队 int ana(char sz);/分析二叉树层数 void visit(Tnode*k);/回调访问函数 int ifpopcorn();/判断队列是否为空 void inintque();/初始化队列 int flag(int n,int i);/层数显示标记 主函数阶段，循环显示主界面：建立多项式、多项式操作以及显示多项式。 【输入格式】： 建立二叉树： 二叉树数据：按中序遍历顺序输入 输出某一层： 输入层数，按回车即可。 二设计算法 19 / 49 建立二叉树 评价： 处理 scree 存储的中序输入的字符串， 实现思想：以中序遍历的方法，递归建立。 代码如下： Tnode* finit(Tnode* tf,int flo)/中序建立 if(!flo)return NULL; if(*scree=0)return NULL; tf=(Tnode*)malloc(sizeof(Tnode);/为当前节点申请空间 tf-ltree=finit(tf-ltree,flo-1);/递归 中序是先左再中后右 tf-data=*printc; /赋值 printc 为指向scree字符串 20 / 49 printc+; /指针后移 tf-rtree=finit(tf-rtree,flo-1);/递归 return tf;/返回树节点 遍历算法 评价：利用递归算法遍历。 算法思想：递归。 实现代码如下： void ordtra(Tnode* tf,fp kf,int flo)/先序遍历 / printf(%c,tf-data); 21 / 49 if(!tf|!flo)return; kf(tf);/回调函数 ordtra(tf-ltree,visit,flo-1); ordtra(tf-rtree,visit,flo-1); void follow(Tnode* tf,fp kf,int flo)/后序遍历 / printf(%c,tf-data); if(!tf|!flo)return; follow(tf-ltree,visit,flo-1); follow(tf-rtree,visit,flo-1); 22 / 49 kf(tf); return ; 层序遍历 评价：实现对每一层进行遍历输出。 算法思想：建立一个队列，循环思想如下：在循环前将当头节点入队，进入循环后，先出队一个，输出，同时判断左右子树是否存在 ，存在则分别入队，进入下一次循环。这样下去，可以把每一层都输出。 同时会有一个 i 变量，用于判断循环边界以及是否输入某层。 void transver(Tnode* tf,int flo,fp kf,int n) 23 / 49 int i=0; if(!tf)return NULL; inintque();/初始化队列 pus_pop(tf,1);/树头入队 while(i i+;/“ 指向 ” 下一个节点 tf=pus_pop(tf,0);/出队 if(flag(n,i)kf(tf);/flag 作用为：如果标记变量 n 为 0 那么就返回 1 如果为其他数字则需要判断 i 是否在第 n 层 否则返回 0 if(tf-ltree)pus_pop(tf-ltree,1);/左子树存在的话就入队 if(tf-rtree)pus_pop(tf-rtree,1);/右子树存在的话就入队 24 / 49 printf(n); int flag(int n,int i) if(n=0)return 1; if(pow(2,n-1)-1)=i)return 1;/ 在第 n 层 范 围 内 return 0; 其他函数 队列的入队和出队函数 Tnode*pus_pop(Tnode*tf,int k) 25 / 49 if(k)queuept+=tf;/1 入 else if(ptph)return queue+ph; 访问函数 void visit(Tnode*k) printf(%c ,k-data); 数据结构实验报告 专业班级：计算机科学与技术 26 / 49 姓名：。 学号：。 一、实验目的和要求 上机学习二叉树。 二、实验内容 实现二叉树的各项算法并掌握其用法如二叉树的构造，先中后序遍历，层次遍历等等 三、实验过程 设计算法 1.二叉树的构造：通过对二叉树的先序序列的扩展来构造 二叉树 2.求二叉树的高度：二叉树的高度等于子树高度加一，递归27 / 49 求出二叉树高度。 3二叉树的层次遍历：初始化队列，使根节点进队。下面开始循环，终止条件为队列为空。是队头结点出队，并使它的左孩子和右孩子一次进队 4.求二叉树叶子结点：遍历二叉树，如果左孩子和右孩均不存在，则该结点为叶子结点。 数据结构的选择和概要设计 数据结构的选择：学习二叉树结构，利用队列实现其中的层次遍历。 概要设计：利用类将二叉树和其属性封装起来，定义结构体变量作为结点。 四、测试及结果分析 五、实验收获 通过课堂学习以及课后的上机实 习，我学习到了树和二叉树的性质，以及相关算法。如二叉树的遍历，求二叉树的高度。并在这些算法实现的过程中对递归有了更加深的了解，并且28 / 49 认识到了递归的重要性 六、附录 #include #include using namespace std; struct node char data; node*lchild; node*rchild; int num; ; class Tree public: 29 / 49 Tree() cout bool empty() if(root=NULL) return true; return false; void pre_number() if(empty() return; T_pre_number(this-root); void pre_travel() if(empty() return; int i=1; node* t=this-root; T_pre_travel(t,i); cout void preorder() if(empty() 30 / 49 return; node* t=this-root; coutroot; T_inorder(t); coutroot; T_postorder(t); coutroot)二叉树实验报告总结 )n; node* t=this-root; coutroot; T_level_order(T); 树 和 二 叉 树 一、实验目的 1. 掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 2. 掌握用指针类 型描述、访问和处理二叉树的运算。 二、实验要求 1. 认真阅读和掌握本实验的程序。 2. 上机运行本程序。 31 / 49 3. 保存和打印出程序的运行结果，并结合程序进行分析。 4. 按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运 行结 果。 三、实验内容 1. 输入字符序列，建立二叉链表。 2. 按先序 、中序和后序遍历二叉树。 3. 按某种形式输出整棵二叉树。 4. 求二叉树的高度。 5. 求二叉树的叶节点个数。 6. 交换二叉树的左右子树。 32 / 49 7. 借助队列实现二叉树的层次遍历。 8. 在主函数中设计一个简单的菜单，分别调试上述算法。 为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质 5来建立二叉树，输入数据时要将节点的序号和数据同时给出：。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#” 来充当，也要输入。若当前数据不为 “#” ，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。 四、解题思路 1 访问根结点， 2 先序遍历左子树， 3 先序遍历右子树 1、先序遍历： 1 中序遍历左子树， 2 访问根结点， 3 中序遍历右子树 2、中序遍历： 33 / 49 1 后序遍历左子树， 2 后序遍历右子树， 3 访问根结点 3、后序遍历： 4、层次遍历算法：采用一个队列 q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。 五、程序清单 #include #include #define M 100 typedef char Etype; /定义二叉树结点值的类型为字符型 typedef struct BiTNode /树结点结构 34 / 49 Etype data; struct BiTNode *lch,*rch; BiTNode,*BiTree; BiTree queM; int front=0,rear=0; /函数原型声明 BiTNode *creat_bt1(); BiTNode *creat_bt2(); void preorder(BiTNode *p); void inorder(BiTNode *p); void postorder(BiTNode *p); 35 / 49 void enqueue(BiTree); BiTree delqueue( ); void levorder(BiTree); int treedepth(BiTree); void prtbtree(BiTree,int); void exchange(BiTree); int leafcount(BiTree); void paintleaf(BiTree); BiTNode *t; int count=0; /主函数 36 / 49 void main() char ch; int k; do printf(nnn); printf(n= 主 菜 单=); printf(nn 1.建立二叉树方法 1); printf(nn 2.建立二叉树方法 2); printf(nn 3.先序递归遍历二叉树 ); 37 / 49 printf(nn 4.中序递归遍历二叉树 ); printf(nn 5.后序递归遍历二叉树 ); printf(nn 6.层次遍历二叉树 ); printf(nn 7.计算二叉树的高度 ); printf(nn 8.计算二叉树中叶结点个数 ); printf(nn 9.交换二叉树的左右子树 ); printf(nn 10.打印二叉 树 ); printf(nn 0.结束程序运行 ); printf(n=); printf(n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10); 38 / 49 scanf(%d,&k); switch(k) case 1:t=creat_bt1( );break; /调用性质 5建立二叉树算法 case 2:printf(n请输入二叉树各结点值 :);fflush(stdin); t=creat_bt2();break; /调用递归建立二叉树算法 case 3:if(t) printf(先序遍历二叉树 :); preorder(t); printf(n); else printf(二叉树为空 !n); 39 / 49 break; case 4:if(t) printf(中序遍历二叉树 :); inorder(t); printf(n); else printf(二叉树为空 !n); break; case 5:if(t) printf(后序遍历二叉树 :); postorder(t); 40 / 49 printf(n); else printf(二叉树为空 !n); break; case 6:if(t) printf(层次遍历二叉树： ); levorder(t); printf(n); else printf(二叉树为空！ n); break; 41 / 49 case 7:if(t) printf(二叉树的高度为： %d,treedepth(t); printf(n); else printf(二叉树为空！ n); break; case 8:if(t) printf(二叉树的叶子结点数为： %dn,leafcount(t); printf(二叉树的叶结点为： );paintleaf(t); printf(n); 42 / 49 else printf(二叉树为空！ n); break; case 9:if(t) printf(交换二叉树的左右子树： n); exchange(t); prtbtree(t,0); printf(n); else printf(二叉树为空！ n); break; case 10:if(t) 43 / 49 printf(逆时针旋转 90度输出的二叉树： n); prtbtree(t,0); printf(n); else printf(二叉树为空！ n