二叉树的应用_数据结构课程设计报告书.doc

《二叉树的应用_数据结构课程设计报告书.doc》由会员分享，可在线阅读，更多相关《二叉树的应用_数据结构课程设计报告书.doc（11页珍藏版）》请在三一办公上搜索。

1、.信息科学与技术学院数据结构课程设计报告题目名称：二叉树的应用专业_学生_学生_指导目 录1、课程设计的目的、课程设计题目、题目要求21.1课程设计的目的31.2课程设计的题目31.3题目要求32课程设计的实验报告内容:43课程设计的原程序代码:44运行结果165. 课程设计总结216参考书目221课程设计的目的1.1课程设计的目的:通过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是链表,但是也运用了类.通过两种方法解决现有问题.1.2课程设计的题目: 二叉树的应用1.3题目要求:1. 建立二叉

2、树的二叉链表存储算法2. 二叉树的先序遍历,中序遍历和后序遍历输出3. 非递归的先序遍历,中序遍历4. 二叉树的层次遍历5. 判断此二叉树是否是完全二叉树6. 二叉树的左右孩子的交换2课程设计的实验报告内容:7. 通过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队,而二叉树的左右孩子的交换则采用的是一个简单的递归。3课程设计的原程序代码:#includeusing namespace std;#define MAXSIZE 100int sign=0;void menu;/typedef struct BiTNodechar dat

3、a;BiTNode *left_child,*right_child;BiTNode,*BiTree;int CreateBiTree/创建二叉树 char ch; coutch; if T=NULL; else if! coutdata=ch; CreateBiTreeleft_child;/create leftchild CreateBiTreeright_child; /create rightchild return 1;/判断此树是否是完全二叉树int LevelOrder1BiTree stackMAXSIZE;BiTreep;int front,rear;front=-1,re

4、ar=0;stackrear=T;whilefront+;p=stackfront;ifleft_child=NULL&right_childsign=1;ifleft_childrear+;stackrear=p-left_child;ifright_childrear+;stackrear=p-right_child;return 1;void Output /输出二叉树if cout空树!n;return ; /空树coutdata ;/ 输出根结点ifleft_child Outputleft_child; /输出左子树ifright_childOutputright_child;/输

5、出右子树int Depth /求树深int i,j;if return 0;i = Depthleft_child;j = Depthright_child;return j?i:j + 1;int Node/求结点数if return 0;return 1+Nodeleft_child+Noderight_child;int Leaf /求叶子结点if return 0;ifleft_child&!T-right_child return 1;/仅有根结点return Leafleft_child+Leafright_child;/返回叶子结点的数目void PreOrder /先序遍历算法

6、 DLRif return ; /递归调用的结束条件coutdata ; / 访问根结点的数据域PreOrderleft_child;/先序递归遍历T的左子树PreOrderright_child;/先序递归遍历T的右子树void InOrder/中序遍历算法 LDRif return ;InOrderleft_child;coutdata ;InOrderright_child;void PostOrder/后序遍历算法 LRDif return ;PostOrderleft_child;PostOrderright_child;coutdata ;/非递归先序遍历int NRPreOrde

7、rBiTree stack100,p;int top;ifreturn 1;top=-1;p=T;while!whilecoutdata ;iftoptop+;stacktop=p;else cout栈溢出left_child;ifreturn 1;elsep=stacktop;top-;p=p-right_child; return 1;/非递归中序遍历int NRInOrderBiTree stack100,p;int top;ifreturn 1;top=-1;p=T;while!whileiftoptop+;stacktop=p;else cout栈溢出left_child;ifret

8、urn 1;elsep=stacktop;coutdataright_child;return 1;/层次遍历void LevelOrderBiTree queue100;int front,rear;ifreturn;front=-1;rear=0;queuerear=T;whilefront+;coutdata ;ifleft_child!=NULLrear+;queuerear=queuefront-left_child;ifright_child!=NULLrear+;queuerear=queuefront-right_child;/*左右子树交换*/*将结点的左右子树交换*/*Bi

9、TNode *swap BiTNode *t,*t1,*t2; if t=NULL; else t=mallocsizeof; t-data=T-data; t1=swapleft_child; t2=swapright_child; t-left_child=t2; t-right_child=t1; return; void print if printfdata; ifleft_child!=NULL|T-right_child!=NULL printf; printleft_child; ifright_child!=NULLprintf; printright_child; prin

10、tf; */int PreOrderTraverse ifreturn 0;BiTree t;if left_child|T-right_child t=T-left_child;T-left_child=T-right_child;T-right_child=t;PreOrderTraverseleft_child;PreOrderTraverseright_child;return 0;/菜单void menu cout*endl; coutendl; cout*endl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl

11、; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; cout*endl;/主函数void main int br,a;BiTree T;br=CreateBiTree;whilemenu;cout;cina;if=0|aswitch case 0:cout建立后的二叉树为：n;Output;coutendl;system;break;case 1:cout该树的树深为: Depthendl;system;break;case 2:cout该树的结点数：Nodeendl;system;break;case

12、 3:cout该树的叶子结点为：Leafendl;system;break;case 4:cout该树以先序遍历输出为：n;PreOrder;coutendl;system;break;case 5:cout该树以中序遍历输出为:n;InOrder;coutendl;system;break;case 6:cout该树以后序遍历输出为：n;PostOrder;coutendl;system;break;case 7:cout该树的非递归先序遍历输出为:n; NRPreOrder;coutendl;system;break;case 8:cout该树的非递归中序遍历输出为:n; NRInOrde

13、r;coutendl;system;break;case 9:cout该树的层次遍历：n;LevelOrder;coutendl;system;break;case 10:LevelOrder1;ifcout这不是一个完全二叉树。endl;else cout这是一个完全二叉树。endl;/break;system;break;case 11:PreOrderTraverse; cout左右孩子已经替换成功endl;break;case 12:exit;4运行结果:4. 1用二叉链表创建二叉树：4.2主菜单4.3求二叉树树深：4.4二叉树结点数:4.5二叉树的中序遍历:4.6二叉树的层次遍历：4.7左右孩子交换：4.8左右孩子交换后的中序遍历：4.9左右孩子交换后的层次遍历：5. 课程设计总结：此次课程设计使我对书本的知识有进一步了解。同时也是我知道自己的一些不足,这次课程设计我是在书本与同学的帮助下完成的。6参考书目：1.数据结构课本2.数据结构基本操作11 / 11