2023年实验五二叉树基本操作的编程实现实验报告

府光龙车工如坐院HUBEI UNIVERSITYOF AUTOMOTIVETECHNOLOGY数据构造实验报告广一这里一定填写清晰自己选试验项目试验五试验类别基础篇学生姓名朱忠栋学生学号完毕日期2023-12-16指导教师付勇智试验成绩评阅日期评阅教师试验五二叉树基本操作的编程实现【试验目的】内容二叉树基本操作勺编程实现H规定二叉树基本操作的编程实现（2课时，验证型），掌握二叉树日勺建立、遍历、插入、删除等基本操作的编程实现，也可以深入编程实现查找等操作，存储构造重要采用次序或链接构造也鼓励学生运用基本操作进行某些应用的程序设计【试验性质】验证性试验（课时数2H）【试验内容】如下日勺选题都可以作为本次试验的推荐题目建立二叉树，并此前序遍历的方式将结点内容输出

1.将一种表达二叉树时数组构造转换成链表构造

2.将体现式二叉树方式存入数组，以递归方式建立体现式之二叉树状构造，再分别输出前序、中序及后序遍历成果，并计算出体现式之成果【注意事项】.开发语言使用1C.可以自己增长其他功能2【试验分析、阐明过程】页面不够，可续页根据自己选择时层次不一样日勺试验内容，完善程序代码，调试通过后，分析阐明该问题处理日勺详细算法过程不需要写出详细的代码，只体现清晰详细时处理算法即可可以采用流程图、形式语言或者其他数学体现方式来阐明这次试验考察的重要是递归建立二叉树，递归输出先序，中序和后序遍历日勺成果；非递归建立二叉树，再以非递归方式分别输出先序，中序和后序遍历的成果而对于基础篇考察的重要是递归建立二叉树，递归输出先序，中序和后序遍历日勺成果，是以填空日勺方式进行考察勺H对于第一空递归实现日勺先序遍历，其实现措施是printfH%dn,p-data;ifp-lchild!=NULL preorderp-lchild;ifp-rchild!=NULL preorderp-rchild;对于第二空递归实现日勺中序遍历，其实现措施是ifp-lchild!=NULL inorderp-lchild;printfn%d;p-data;ifp-rchild!=NULL inorderp-rchild;对于第三空递归实现日勺后序遍历，其实现措施是ifp-lchild!=NULL postorderp-lchild;ifp-rchild!=NULL postorderp-rchild;printfn%dn,p-data;【思索问题】页面不够，可续页

1.二叉树是树吗？它日勺定义为何是递归欧

2.I答最多有两棵子树的有序树，称为二叉树二叉树是一种特殊的树具有个结点日勺完全二叉树日勺深

3.n度为二叉树日勺计算措施若一棵二叉树为空，则其深度为log2n+l!!!0,WBR否则其深度等于左子树和右子树的最大深度加1三种根序遍历重要思绪是什么？

4.答大体思绪差不多，但节点访问位置不一样样，先序的话，是先访问，然后节点压栈，移到左子树，至

5.节点空退栈，移到右子树而中序日勺话，是先节点压栈，移到左子树，至节点空退栈，访问节点，然后移到右子树此外，所谓前序、中序、后序遍历，全称是前根序遍历，中根序遍历，后根序遍历，不管哪种遍历，访问左子树一定在访问右子树之前，不一样的就是根的访问时机因此三种递归/或非递归，程序思绪都是同样的.假如不用遍历算法一般启用什么数据构造实现后序遍历？6答用栈实现后序遍历

7.举出二叉树日勺应用范例？答一种集合的嘉集、排列问题、组合问题答一种集合的幕集、排列问题、组合问题【试验小结】（总结本次试验的重难点及心得、体会、收获）页面不够，可续页在本次试验中我碰到了许多困难，终于我顺利地完毕了它本次试验我收获良多，不仅仅是书本上日勺知识上的欠缺得到了补充，使我更好的掌握了本章日勺内容；在学习工作日勺品质方面也有了较大的进步总之这次试验，我认为是比较成功的在知识方面，通过这次试验我对树的有关知识进行了深入的思索，使我对其有了全面而深入日勺认识，对其特点和应用也有了对应的理解尤其是在应用方面使我不在像此前同样拘泥于学，而忽视用日勺重要性一种合格的学习者，必然是一种善于学以致用勺学习者，这样的学习者不仅仅会学习，还会用自己所学发明价值，是自己所学的U知识实现其应有日勺价值，而不是消化在肚子里在对此后发展方面，通过本次试验我明白了任何事都不是一蹴而就时，只有通过不停日勺钻研，反复日勺试验改善才也许得到自己想要的成果经历失败不可怕，可怕的是没有这个过程，只要有了这个过程，就算一时没有成功，不过我相信最终一定会成功的不是不会成功，只是还没有成功而已一一你正在走向成功的道路上等通过了这一段探究的历程，你必然会获得你渴望已久的成功【附录-试验代码】页面不够，可续页这个代码必须是调试通过，没有问题时最终代码#includestdio.h#includestdlib.h#includeconio.h#includeiostream.h#define MAXSIZE100typedef charelemtype;typedef struct bitree elemtypedata;structbitree*Ichild,*rchild;}BTREE;BTREE*create{//先序递归创立二叉树char ch;BTREE*bt;ch=getchar;ifch==#bt=NULL;elsebt=BTREE*mallocsizeofBTREE;bt-data=ch;〃递归创立左子树〃递归创立右子树bt-lchild=create;bt-rchild=create;returnbt;void preorderBTREE*root{〃递归实现的先序遍历IBTREE*p;p=root;ifp!=NULL printfn%dn,p-data;ifp-lchild!=NULL preorderp-lchild;ifp-rchild!=NULL preorderp-rchild;{//递归实现时中序遍历void inorderBTREE*rootBTREE*p;p=root;ifp!=NULLifp-lchild!=NULL prininorderp-lchild;tfn%d1,p-data;ifp-rchild!=NULL inorderp-rchild;{//递归实现的后序遍历void postorderBTREE*rootBTREE*p;p=root;ifp!=NULLifp-lchild!=NULL}ifp-rchild!=NULL postorderp-lchild;printfn%d,,,p-data;postorderp-rchild;void lorderBTREE*root f,r;{〃非递归实现的层次遍历为最大容量//maxsize类似于头尾指针BTREE*q[MAXSIZE],*p;int//f,rq[l]=root;f=r=1;whilef=rP=q[H；〃出队f++;printfn%cH,p-data;ifp-lchild!=NULLr++;q[r]=p-lchild;〃入队ifp-rchi!d!=NULLr++;q[r]=p-rchild;〃入队void showmenu{〃显示菜单printfn欢迎使用二叉树操作演示软件\n”；printf\tl.创立二叉树\n”；printf\t

2.先序遍历二叉树\n；printf\t3,中序遍历二叉树\n；.后序遍历二叉树printf\t4\n”;,层次遍历二叉树printf”\t5\n”;.退出程序printf”\t6\n”;}void main匚BTREE*roo NULL;int no;whilel{showmenu;printfn请输入你的I选择；scanfn%dn,no;〃清除键盘缓冲区fflushstdin;switchnocase Lprintf请按先序依次输入二叉树的J结点八n；printf空结点用#号表达.\n；root=create;二叉树创立成功，按任意键继续…printf\n getch;systemnclsn;break;case2:printf二叉树先序遍历成果为:\n；preorderroot;printfn\nn;systemnpausen;systemnclsn;break;case3:printf二叉树中序遍历成果为:\n；inorderroot;printfH\nn;systemnpausen;systemnclsn;break;case4:printf二叉树后序遍历成果为:\n；postorderroot;printfM\nn;systemnpausen;systemnclsn;break;二叉树层次遍历成果为case5:printf\n;lorderroot;printfH\nn;systemnpausen;systemnclsn;break;case6:return;default:“你的输入有误，请从新输入！printf\nsystemnpausen;systemnclsn;。