二叉树的应用_数据结构课程设计(10页).doc

《二叉树的应用_数据结构课程设计(10页).doc》由会员分享，可在线阅读，更多相关《二叉树的应用_数据结构课程设计(10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-二叉树的应用_数据结构课程设计-第 10 页信息科学与技术学院数据结构课程设计报告题目名称：二叉树的应用专业班级：计算机科学与技术学生姓名：陈 杰学生学号：200808261指导教师：高 攀完成日期：2010-04目 录1、课程设计的目的、课程设计题目、题目要求2课程设计的目的3课程设计的题目3题目要求32课程设计的实验报告内容:43课程设计的原程序代码:44运行结果165. 课程设计总结216参考书目221课程设计的目的1.1课程设计的目的:通过以前的学习以及查看相关资料,按着题目要求编写程序,进一步加强对编程的训练,使得自己掌握一些将书本知识转化为实际应用当中.在整个程序中,主要应用的是

2、链表,但是也运用了类.通过两种方法解决现有问题.课程设计的题目: 二叉树的应用题目要求:1. 建立二叉树的二叉链表存储算法2. 二叉树的先序遍历，中序遍历和后序遍历输出3. 非递归的先序遍历，中序遍历4. 二叉树的层次遍历5. 判断此二叉树是否是完全二叉树6. 二叉树的左右孩子的交换2课程设计的实验报告内容:7. 通过递归对二叉树进行遍历。二叉树的非递归遍历主要采用利用队进行遍历。此后的判断此二叉树是否是完全二叉树也才采用队，而二叉树的左右孩子的交换则采用的是一个简单的递归。3课程设计的原程序代码:#includeusing namespace std;#define MAXSIZE 100i

3、nt sign=0;void menu();typedef struct BiTNodechar data;BiTNode *left_child,*right_child;BiTNode,*BiTree;int CreateBiTree(BiTree &T)/创建二叉树 char ch; coutch; if(ch=#) T=NULL; else if(!(T=new BiTNode) coutdata=ch; CreateBiTree(T-left_child);/create leftchild CreateBiTree(T-right_child); /create rightchil

4、d return 1;/判断此树是否是完全二叉树int LevelOrder1(BiTree &T)BiTree stackMAXSIZE;BiTreep;int front,rear;front=-1,rear=0;stackrear=T;while(rear!=front)front+;p=stackfront;if(p-left_child=NULL)&(p-right_child)sign=1;if(p-left_child)rear+;stackrear=p-left_child;if(p-right_child)rear+;stackrear=p-right_child;retur

5、n 1;void Output(BiTree &T) /输出二叉树if(!T) cout空树!n;return ; /空树coutdataleft_child) Output(T-left_child); /输出左子树if(T-right_child)Output(T-right_child);/输出右子树int Depth(BiTree &T) /求树深int i,j;if(!T) return 0;i = Depth(T-left_child);j = Depth(T-right_child);return (ij?i:j) + 1;int Node(BiTree &T)/求结点数if(!

6、T) return 0;return 1+Node(T-left_child)+Node(T-right_child);int Leaf(BiTree &T) /求叶子结点if(!T) return 0;if(!T-left_child&!T-right_child) return 1;/仅有根结点return Leaf(T-left_child)+Leaf(T-right_child);/返回叶子结点的数目void PreOrder(BiTree &T) /先序遍历算法 DLRif(!T) return ; /递归调用的结束条件coutdataleft_child);/先序递归遍历T的左子树

7、PreOrder(T-right_child);/先序递归遍历T的右子树void InOrder(BiTree &T)/中序遍历算法 LDRif(!T) return ;InOrder(T-left_child);coutdataright_child);void PostOrder(BiTree &T)/后序遍历算法 LRDif(!T) return ;PostOrder(T-left_child);PostOrder(T-right_child);coutdata ;/非递归先序遍历int NRPreOrder(BiTree &T)BiTree stack100,p;int top;if(

8、T=NULL)return 1;top=-1;p=T;while(!(p=NULL&top=-1)while(p!=NULL)coutdata ;if(top100-1)top+;stacktop=p;else cout栈溢出left_child;if(top=-1)return 1;elsep=stacktop;top-;p=p-right_child; return 1;/非递归中序遍历int NRInOrder(BiTree &T)BiTree stack100,p;int top;if(T=NULL)return 1;top=-1;p=T;while(!(p=NULL&top=-1)w

9、hile(p!=NULL)if(top100-1)top+;stacktop=p;else cout栈溢出left_child;if(top=-1)return 1;elsep=stacktop;coutdataright_child;return 1;/层次遍历void LevelOrder(BiTree &T)BiTree queue100;int front,rear;if(T=NULL)return;front=-1;rear=0;queuerear=T;while(front!=rear)front+;coutdataleft_child!=NULL)rear+;queuerear=

10、queuefront-left_child;if(queuefront-right_child!=NULL)rear+;queuerear=queuefront-right_child;/*左右子树交换*/*将结点的左右子树交换*/*BiTNode *swap(BiTNode &T)BiTNode *t,*t1,*t2; if(T=NULL) t=NULL; else t=(BiTNode *)malloc(sizeof(BiTNode); t-data=T-data; t1=swap(T-left_child); t2=swap(T-right_child); t-left_child=t2

11、; t-right_child=t1; return(t); void print(BiTNode &T) if(T!=NULL) printf(%c,T-data); if(T-left_child!=NULL|T-right_child!=NULL) printf(); print(b-left_child); if(b-right_child!=NULL)printf(, ); print(b-right_child); printf(); int PreOrderTraverse(BiTree T)if(!T)return 0;BiTree t;if (T-left_child|T-r

12、ight_child) t=T-left_child;T-left_child=T-right_child;T-right_child=t;PreOrderTraverse(T-left_child);PreOrderTraverse(T-right_child);return 0;/菜单void menu() cout*endl; coutendl; cout*endl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; coutendl; c

13、outendl; coutendl; cout*endl;/主函数void main()int br,a;BiTree T;br=CreateBiTree(T);while(1)menu();cout;cina;if(a=0|a=12)switch (a)case 0:cout建立后的二叉树为：n;Output(T);coutendl;system(pause);break;case 1:cout该树的树深为: Depth(T)endl;system(pause);break;case 2:cout该树的结点数：Node(T)endl;system(pause);break;case 3:co

14、ut该树的叶子结点为：Leaf(T)endl;system(pause);break;case 4:cout该树以先序遍历输出为：n;PreOrder(T);coutendl;system(pause);break;case 5:cout该树以中序遍历输出为:n;InOrder(T);coutendl;system(pause);break;case 6:cout该树以后序遍历输出为：n;PostOrder(T);coutendl;system(pause);break;case 7:cout该树的非递归先序遍历输出为:n; NRPreOrder(T);coutendl;system(paus

15、e);break;case 8:cout该树的非递归中序遍历输出为:n; NRInOrder(T);coutendl;system(pause);break;case 9:cout该树的层次遍历：n;LevelOrder(T);coutendl;system(pause);break;case 10:LevelOrder1(T);if(sign=1)cout这不是一个完全二叉树。endl;else cout这是一个完全二叉树。endl;/break;system(pause);break;case 11:PreOrderTraverse(T); cout左右孩子已经替换成功endl;break;case 12:exit(-1);4运行结果:4. 1用二叉链表创建二叉树：求二叉树树深：二叉树结点数:二叉树的中序遍历:二叉树的层次遍历：左右孩子交换：4.8左右孩子交换后的中序遍历：5. 课程设计总结：此次课程设计使我对书本的知识有进一步了解。同时也是我知道自己的一些不足，这次课程设计我是在书本与同学的帮助下完成的。它并不难，但是我没有自己独自完成是我的错误。6参考书目：1.数据结构课本2. 数据结构基本操作