2022年遍历算法及应用 .pdf

《2022年遍历算法及应用 .pdf》由会员分享，可在线阅读，更多相关《2022年遍历算法及应用 .pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实 验 报 告课程名称算法与数据结构姓名何劼专业计算机科学与技术部别指导教员日期年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - 2 实验项目列表序号实验项目名称成绩01 稀疏多项式02 小型计算器03 遍历算法及应用04 05 06 07 08 09 10 11 12 13 14 15 16 总评成绩：教员签字：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

2、- 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - 3 实验报告姓名： 何劼学号：专业： 计算机科学与技术部别：实验地点：实验时间： 2012、4、17 设备编号：同组人员：指导教员签字：成绩：教员评语：一、 实验名称遍历算法及应用二、实验目的1 掌握二叉树的递归构造方法2 掌握二叉树的递归遍历方法3 掌握二叉树的递归遍历的简单应用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - - - -

3、- - 4 三、实验内容和要求编写完成如下功能的程序。1 构造二叉树（中序加后序序列造树选做）2 删除树中原来所有1 度的结点3 求给定的任意结点的父亲4 从根到叶的一条最长路经5 计算树中叶结点数（选）6 判定一棵树是否是正则树（选）7 按层遍历树，并输出树宽（选）要求：1 先构造出二叉树，然后输出原树的三种遍历序列。2 在删除原来所有1 度的结点后，再输出新二叉树的三种遍历序列。3 直接输出给定结点的父结点的值。4 输出这条最长的路径。5 输出树中叶结点的数目。6 输出一棵树是否是正则树的判定结论。7 按层遍历树，并输出树宽四、实验环境1硬件环境： PC机名师资料总结 - - -精品资料欢

4、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 5 2软件环境： Windows操作系统， VC+ 集成开发环境五、算法设计思想题目一构造二叉树。为了使得程序能够更加具有通用性， 设计者在构造二叉树时编写了三种造树方式，分别是先序扩充序列造树，先序加中序序列造树以及中序加后序造树。其中前两个程序已经在课上得到了实现。中序加后序造树，主要问题就是左右子树上下标界的确定，运用图示法能够较为形象准确的解决此问题。三种序列的输出这里不加赘述。题目二删除树中1 度结点。

5、采用先序遍历递归。首先判断下一结点是否为1 度结点，若为1度结点并且有右儿子，返回1；若为 1 度结点并且有左儿子，返回2；不为 1 度结点返回 0。再根据返回值的情况进行勾连和结点的删除。题目三求结点的父亲。采用后续遍历递归。设计者配合使用了类似于“红绿灯”的found标记值。若为 0 则还未发现结点；若为1 则找到该结点返回上一层输出其父亲，并置 found 为 2。题目四输出从根到叶的一条最长路径。首先找到最长路径对应的叶子 （先序） ， 再求取叶子的祖先（后序）。运用 order 数组存储其祖先，最后从后到前输出。这样得到的路径是符名师资料总结 - - -精品资料欢迎下载 - - -

6、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - 6 合从根到叶的顺序的。题目五计算叶子的数目。采用先序遍历递归。判断是否为叶子。若为叶节点num加 1；反之递归判断其左儿子，右儿子。题目六判断正则树。如果存在这样一个结点， 它只有一个儿子，那么 found 标记值置 1。当递归遍历完整棵树之后，found 等于 1 则不为正则树；反之则为正则树。题目七按层遍历树。运用了队的结构。初始时刻last指针 boundary 指针重合， first指针在两者之前1 位。树根先入队，并访问

7、它，first指针后移，与boundary 指针重合，说明该层遍历完成，breadth 记录该层宽度。然后其左儿子，右儿子入队， last指针移至队尾。接着访问下一结点每当 first与 boundary 重合则说明该层遍历完成。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - 7 六、主要问题与解决方法构造二叉树时，主要是中序加后序造树的递归标界的确定。如上文所说，运用图示法比较形象准确的解决了问题。删除 1 度结点时，设计者

8、一开始觉得问题较为简单，但是真正上手之后，发现还是有一定难度的，不仅需要判断采用哪种遍历方式，还需要考虑找到一度结点输出最长路径时，一开始递归输出叶子祖先的顺序是从叶子到根。后来运用一个数组，将顺序倒了过来。按层遍历树时，按照教员的提示，运用队结构和boundary 指针的方式，实现了按层遍历。并且记录了树宽。这个思想值得学习。七、实验结果程序对题目要求的构造二叉树、删除树中1 度结点、输出从根到叶的一条最长路径、求结点的父亲、计算叶子的数目和判断正则树的问题进行了解决。在构造二叉树的问题中加入了先序扩充序列造树和中序加后序造树。在最后还添加了教员课上要求的按层遍历树以及求树宽的代码。经测试，

9、该程序是可以解决以上问题的。而对于整个程序，稍微不太满意的地方是对于1 度结点的删除和求最长路径的函数部分。两者过于冗长，并且进行了函数的二次调用。对于前者，经过教员后期课上指导发现可以有更好的较为简单的解决方法（主要思想是运用引用型参数） ， 而后者暂时还没有找到较好的方法能够名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - 8 只对树一次遍历就得到从根到叶的顺序输出。以下是程序运行的截图和部分程序运行示意图：名师资料总结 -

10、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - 10 八、体会、质疑、建议本次实验主要是对二叉树进行了一系列的操作，归根结底是二叉树的查找、插入、删除。通过实验我对三种操作有了更加深入的认识，也更加熟练的掌握了其具体应用。通

11、过对于树这种非链式结构的结构类型各种操作，我也体会到了学以所用的道理。任何一种结构类型都是为了更加方便准确的对事物进行描述，并且使之能够为计算机所识别使用。这是一个从具体到抽象的过程，也是一个建模的过程。而对于一个结构的定义，我认为不应该过分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - 11 的限制自己一定要使用什么结构。模型是死的，人是活的。一切都应该根据具体情况分析使用。当然，要达到游刃有余的地步，作为我，还有很长的路

12、要走。具体到这个程序，我发现自己对于引用型的参数认识还不够，特别是具体应用的时候，问题还比较多，应当再继续加强。九、源代码.cpp 文件连接#include #include #define M 100 typedef int eletype; typedef struct treenode eletype data; struct treenode *lson,*rson; Bnode,*Bptr; int num,found,or,first,last,boundary,breadth; eletype longest,x; Bptr addr; 名师资料总结 - - -精品资料欢迎下载

13、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 12 eletype orderM; / 找叶子数的函数中： num用于记录叶子数目；按层遍历函数中用于记录层的宽度。/*found用于记录查找的状态：找父亲函数中： 0 为查找结点不存在， 1 为找到该点， 2 为父亲结点已输出；判断正则树的函数中： 1 为找到一个不满足的结点，0 为未找到；找祖先函数中： 0 为查找结点不存在， 1 为找到该点。 */ /or与数组 order配合用于调整输出顺序，使其从根到叶顺序

14、输出。/first是作为队的首指针。/last作为队的尾指针。/boundary作为每层的边界指针。/breadth记录已遍历的层中最宽的宽度。/longest用于记录递归到当前，最长路径的值。/addr用于记录找到的结点的地址。void preorder(Bptr p)/先序序列输出 if(p=NULL)return; printf(%d ,p-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 13 preor

15、der(p-lson); preorder(p-rson); void inorder(Bptr p)/中序序列输出 if(p=NULL)return; inorder(p-lson); printf(%d ,p-data); inorder(p-rson); void postorder(Bptr p)/后序序列输出 if(p=NULL)return; postorder(p-lson); postorder(p-rson); printf(%d ,p-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

16、 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - 14 Bptr precreat()/先序扩充序列造树 Bptr p; scanf(%d,&x); if(x=0)return NULL; p=new Bnode; p-data=x; p-lson=precreat(); p-rson=precreat(); return p; Bptr p_i_creat(eletype a,eletype b,int i,int j,int s,int t)/先序+中序序列造树 int k; Bptr p; if(ij)return NULL; p=new Bn

17、ode; p-data=ai; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 15 k=s; while(klson=p_i_creat(a,b,i+1,i+k-s,s,k-1); p-rson=p_i_creat(a,b,i+k-s+1,j,k+1,t); return p; Bptr i_p_creat(eletype a,eletype b,int i,int j,int s,int t)/中序+后序序列造树 int

18、 k; Bptr p; if(ij)return NULL; p=new Bnode; p-data=aj; k=s; while(klson=i_p_creat(a,b,i,i+k-s-1,s,k-1); p-rson=i_p_creat(a,b,i+k-s,j-1,k+1,t); return p; void findfather(Bptr p,eletype aim)/找结点父亲的函数 if(p=NULL|found=2)return; if(p-data=aim) found=1; return; if(found=0) findfather(p-lson,aim); if(found

19、=0) findfather(p-rson,aim); if(found=1) printf(%d的父亲是： %dn,aim,p-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - 17 found=2; void leavenumber(Bptr p)/树的叶结点个数 if(p=NULL)return; if(p-lson=NULL&p-rson=NULL) num+; leavenumber(p-lson);

20、leavenumber(p-rson); void longest_leave(Bptr p,int height)/找一片最长路径的叶子 if(p=NULL)return; if(p-lson=NULL&p-rson=NULL&longestlson,height+1); longest_leave(p-rson,height+1); void ancestor(Bptr p,Bptr addr,eletype order)/存储 a 结点的祖先（逆序） if(p=NULL)return; if(p=addr) orderor+=p-data; found=1; return; if(fou

21、nd=0) ancestor(p-lson,addr,order); if(found=0) ancestor(p-rson,addr,order); if(found=1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - 19 orderor+=p-data; int degree1(Bptr p)/判断 p 是否为 1 度结点， if(p=NULL)return 0; if(p-lson=NULL&p-rson!=NUL

22、L) return 1;/返回 1 表示该 1 度结点有右儿子if(p-lson!=NULL&p-rson=NULL) return 2;/返回 2 表示该 1 度结点有左儿子return 0;/返回 0 表示该点不是 1 度结点 void delete_1(Bptr p)/删除一度结点函数 Bptr re; if(p=NULL)return; if(degree1(p-lson)=1) re=p-lson; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 -

23、 - - - - - - - - 20 p-lson=p-lson-rson; delete re; delete_1(p); else if(degree1(p-lson)=2) re=p-lson; p-lson=p-lson-lson; delete re; delete_1(p); if(degree1(p-rson)=1) re=p-rson; p-rson=p-rson-rson; delete re; delete_1(p); else if(degree1(p-rson)=2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

24、 - - - 名师精心整理 - - - - - - - 第 20 页，共 29 页 - - - - - - - - - 21 re=p-rson; p-rson=p-rson-lson; delete re; delete_1(p); delete_1(p-lson); delete_1(p-rson); void judge(Bptr p)/判断正则树 if(p=NULL|found=1)return; if(p-lson=NULL&p-rson!=NULL) found=1;return; if(p-lson!=NULL&p-rson=NULL) found=1;return; judge

25、(p-lson); judge(p-rson); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 29 页 - - - - - - - - - 22 void levelorder(Bptr p,Bptr team)/按层遍历树的函数 if(p=NULL|first=last)return; first+; printf(%d ,p-data); num+; if(p-lson) teamlast+=p-lson; if(p-rson) teamlast+=p-rson

26、; if(first=boundary) if(breadthnum) breadth=num; num=0; boundary=last; levelorder(teamfirst,team); void initialize()/全局变量初始化函数 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 29 页 - - - - - - - - - 23 num=0,found=0,or=0; longest=-1; addr=NULL; first=-1; last=0;

27、 boundary=0; breadth=0; void main() Bptr f_root=new Bnode; eletype aim; int i=0,j,s=0,node,choice1,choice2,c; Bptr root,teamM; eletype aM,bM; /*造树*/ printf(请输入树结点数目： n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 29 页 - - - - - - - - - 24 scanf(%d,&node);

28、printf(*n); printf(1先序扩充序列造树 n2先序 +中序序列造树 n3 中序+后序序列造树 n); printf(*n); printf(请输入所需操作： ); scanf(%d,&choice1); if(choice1=1) printf(请输入先序扩充序列： n); root=precreat();/先序扩充序列造树 else if(choice1=2) printf(请输入先序序列： n); for(j=0;jnode;j+) scanf(%d,&aj); printf(请输入中序序列： n); for(j=0;jnode;j+) scanf(%d,&bj); roo

29、t=p_i_creat(a,b,0,node-1,0,node-1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 29 页 - - - - - - - - - 25 / 先序+中序序列造树else if(choice1=3) printf(请输入中序序列： n); for(j=0;jnode;j+) scanf(%d,&bj); printf(请输入后序序列： n); for(j=0;jlson=root; f_root-rson=NULL; delete_1(f

30、_root);/删除 1 度结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 29 页 - - - - - - - - - 27 printf(先序序列： ); preorder(f_root-lson);/先序输出printf(n); printf(中序序列： ); inorder(f_root-lson);/中序输出printf(n); printf(后序序列： ); postorder(f_root-lson);/后续输出printf(n); else if(c

31、hoice2=2) printf(请输入需要找父亲的结点：n); scanf(%d,&aim); if(root-data=aim)printf(树根没有父亲！ n); else findfather(root,aim);/找父亲名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 29 页 - - - - - - - - - 28 if(found=0)printf(该结点不存在！ n); else if(choice2=3) longest_leave(root,1);/

32、找一片最长路径的叶子ancestor(root,addr,order);/存储叶结点的祖先（逆序）for(or=or-1;or!=-1;or-)/顺序输出printf(%d ,orderor); printf(为最长路径。 n); else if(choice2=4) leavenumber(root);/记录叶子数printf(叶子数为 %d 。n,num); else if(choice2=5) judge(root);/判断正则树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

33、28 页，共 29 页 - - - - - - - - - 29 if(found=1)printf(不是正则树！ n); else printf(是正则树！ n); else if(choice2=6) printf(按层遍历序列为： n); levelorder(root,team); printf(树宽为： %dn,breadth); printf(n); else printf(输入错误！ n); printf(是否继续？ 1继续， 2结束 n); scanf(%d,&c); while(c=1); printf(谢谢使用，再见！ n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 29 页 - - - - - - - - -