树的综合操作数据结构课程设计

《树的综合操作数据结构课程设计》由会员分享，可在线阅读，更多相关《树的综合操作数据结构课程设计（24页珍藏版）》请在金锄头文库上搜索。

1、 欢迎下载 数据结构 课程设计(论文) 树的综合操作 院 （ 系 ） 名 称 专业班级 学号 学生姓名 指导教师 起 止 时 间： 2014.12.292015.1.9 欢迎下载 课程设计（论文）任务及评语 院（系） ：电子与信息工程学院 教研室：软件工程 学 号 学生姓名 专业班级 课程设计（论文） 题目 树的综合操作 课程设计（论文）任务 任务要求： 树的综合操作实现以下几个功能： （1）创建二叉树的存储结构并保存； （2）非递归实现中序遍历二叉树（3）非递归实现先序遍历二叉树。（4）递归实现层次遍历二叉树；（5）求出二叉树的叶子结点数和层次数。 技术要求： 1、数据的逻辑结构采用树形结构

2、，物理结构采用链式存储结构（二叉链表） 。 2、软件能正常运行，界面清晰，操作要简单。 3、系统要有主界面设计，调用各个功能项。 4、采用 Viscal C+编写代码，可读性强。 5、数据类型用 typedef 定义。 指导教师评语及成绩 平时成绩： 答辩成绩： 论文成绩： 总成绩： 指导教师签字： 年 月 日 注：平时成绩占 20%，答辩成绩占 40%，论文成绩占 40%。 欢迎下载 摘 要 这次的课题主要是创建二叉树的存储结构并保存，通过这一过程了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力并提高综合运用所学的理论知识和方法独立分析和解决问题的能力 主要解决以下问题 创建

3、二叉树的存储结构并保存； 非递归实现中序遍历二叉树； 非递归实现先序遍历二叉树； 递归实现层次遍历二叉树； 求出二叉树的叶子节点数和层次树； 关键词：存储结构；二叉树；C+ 欢迎下载 目 录 第 1 章 绪论 . 1 1.1 系统的开发背景 . 1 1.2 开发工具及语言 . 1 第 2 章 概要设计 . 2 2.1 模块划分 . 2 2.2 数据结构的选择 . 2 第 3 章 系统详细设计与编码 . 3 3.1 完整的源程序 . 3 3.2 程序的输入和输出 . 错误!未定义书签。 3.3 调试程序中遇到的问题及解决方案 . 15 第 4 章 思考题解析 . 16 4.1 思考题的选择 .

4、16 4.2 类 C 算法 . 16 4.3 程序分析 . 17 第 5 章 总结 . 18 参考文献 . 20 附 录 . 错误!未定义书签。 欢迎下载 第 1 章 绪论 1.1 系统的开发背景 二叉树结构是 C 语言中的难点，但是近年来二叉树的应用越发的广泛，实用性越来越强。为了应对日新月异的时代变化，我参与了这个课题来提高自己对二叉树的掌握 1.2 开发工具及语言 本系统使用 Viscal C+语言开发，主界面清晰显示所有功能项，使用简单。各个功能项均定义一个函数来实现，在主函数中调用各个子函数实现不同的功能。 欢迎下载 第 2 章 概要设计 2.1 模块划分 1）题目应实现的具体功能；

5、 创建二叉树的存储结构并保存； 非递归实现中序遍历二叉树； 非递归实现先序遍历二叉树； 递归实现层次遍历二叉树； 求出二叉树的叶子节点数和层次树； 2.2 数据结构的选择 系统数据的逻辑结构采用树形结构，物理结构采用链式存储结构（二叉链表） 。 存储结构定义如下： typedef struct lnode char data; struct lnode *lchild,*rchild; lnode,*tree; 欢迎下载 第 3 章 系统详细设计与编码 3.1 完整的源程序 #include #include #include #define OK 1 #define ERROR 0 #def

6、ine OVERFLOW -2 #define MaxSize 100 typedef char TElemType; typedef int Status; /二叉树的链式存储结构 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; /栈的链式存储结构 typedef struct LNode BiTree data; struct LNode *next; LNode,*LinkList; /进栈 Status Push(LinkList& S,BiTree T) 欢

7、迎下载 LinkList stack; stack=(LinkList)malloc(sizeof(LNode); /分配空间 stack-data=T; stack-next=S-next; /进栈 S-next=stack; return OK; /Push /出栈 Status Pop(LinkList &S,BiTree &T) LinkList stack; stack=S-next; /出栈 S-next=stack-next; / 栈顶指向下个元素 T=stack-data; return OK; /Pop /是否为空栈 Status StackEmpty(LinkList S)

8、 if(S-next=NULL) return OK; else return ERROR; /以先序次序建立二叉树 Status CreatBiTree(BiTree &T) 欢迎下载 TElemType ch; cinch; if(ch=#) T=NULL; else if(!(T=(BiTree)malloc(sizeof(BiTNode) exit(OVERFLOW); /分配存储空间 T-data=ch; /生成根节点 CreatBiTree(T-lchild); /生成左子树 CreatBiTree(T-rchild); /生成右子树 return OK; /创建成功 /Creat

9、BiTree /非递归中序访问二叉树 BiTree GoFarLeft(BiTree T,LinkList &S) /指到二叉树最左边结点 if(!T) return NULL; while(T-lchild) Push(S,T); /结点进栈 T=T-lchild; return T; /返回树头结点 void Inorder_I(BiTree T) BiTree t; LinkList S; S=(LinkList)malloc(sizeof(LNode); 欢迎下载 S-next=NULL; t=GoFarLeft(T,S); /找到最左下的结点 while (t) coutdatarc

10、hild) t=GoFarLeft(t-rchild,S); else if(!StackEmpty(S) /栈空表明遍历结束 Pop(S,t); else t=NULL; /while cout0) while(p!=NULL) coutdatalchild; if(top0) 欢迎下载 top-; p=Stacktop; p=p-rchild; coutnext=NULL; Push(stack,b); /二叉树头结点进栈 while(!StackEmpty(stack) /是否为空 Pop(stack,p); /出栈 while (p) coutdatarchild)Push(stack

11、,p-rchild); /访问右指点 p=p-lchild; coutlchild; while (top0&stacktop-rchild=p) p=stacktop-; /栈顶结点出栈 coutdata0) p=stacktop-rchild; /开始遍历右子树 while(top0); coutlchild)&(!T-rchild) 欢迎下载 count+; CountLeaf(T-lchild,count); /左子树叶子个数 CountLeaf(T-rchild,count); /右子树叶子个数 /CountLeaf /计算双结点个数 void CountParent(BiTree

12、T,int &count) if(T) if(T-lchild&T-rchild) count+; CountParent(T-lchild,count); /左子树双结点个数 CountParent(T-rchild,count); /右子树双结点个数 /计算二叉树结点个数 void Count(BiTree T,int &count) if(T) Count(T-lchild,count); Count(T-rchild,count); count+; /结点个数 /单结点个数 void CountChild(BiTree T,int &count) 欢迎下载 if(T) if(T-lch

13、ild&(!T-rchild)|(T-rchild&(!T-lchild) count+; CountChild(T-lchild,count); /左子树单结点个数 CountChild(T-rchild,count); /右子树单结点个数 /计算树的高度 int Depth(BiTree T) int depthval,depthLeft,depthRight; if(!T) depthval=0; else depthLeft=Depth(T-lchild); /左子树高度 depthRight=Depth(T-rchild); /右子树高度 depthval=1+(depthLeftd

14、epthRight ?depthLeft:depthRight); /取高度最高 return depthval; /返回 /计算任意结点所在的层次 int NodeLevel(BiTree T,TElemType &p,int &count) if(T=NULL) return 0; if(T-data=p) return 1; if(NodeLevel(T-lchild,p,count)|(NodeLevel(T-rchild,p,count) 欢迎下载 count+; return 1; return 0; /主函数 void main() char flag; cout操作选项endl

15、; cout1,非递归打印二叉树(前序，中序，后序)endl; cout2,计算二叉树的结点总数，双孩子个数，单孩子结点数，叶子结点数目endl; cout3,计算二叉树的高度endl; cout4,判断结点的层次endl; do int item; coutitem; switch (item) case 1 : BiTree T; cout请输入要建立的二叉树,以#表示空树endl; CreatBiTree(T); cout先序非递归输出二叉树(两种算法)endl; cout算法 1:endl; PreOrder1(T); 欢迎下载 cout算法 2:endl; PreOrder2(T);

16、 cout中序非递归输出二叉树endl; Inorder_I(T); cout后序非递归输出二叉树endl; PostOrder(T); coutendl; cout是否继续操作?(y/n)flag; break; case 2: BiTree T; int nodeCount=0,leafCount=0,childCount=0,parentCount=0; cout请输入要建立的二叉树,以#表示空树endl; CreatBiTree(T); Count(T,nodeCount); CountParent(T,parentCount); CountChild(T,childCount); C

17、ountLeaf(T,leafCount); cout结点总数目为:nodeCountendl; cout双孩子结点数目:parentCountendl; cout单孩子结点数目:childCountendl; cout叶子结点数目:leafCountendl; cout是否继续操作?(y/n)flag; break; 欢迎下载 case 3: BiTree T; cout请输入要建立的二叉树,以#表示空树endl; CreatBiTree(T); cout该二叉树的高度为:Depth(T)endl; cout是否继续操作?(y/n)flag; break; case 4: BiTree T;

18、 int n=0; char ch; cout请输入要建立的二叉树,以#表示空树endl; CreatBiTree(T); coutch; if(T=NULL) cout空树endl; else NodeLevel(T,ch,n); cout结点的层次为:; coutn+1endl; cout是否继续操作?(y/n)flag; break; 欢迎下载 default : cout无此选项请确定后再输入!lchild);/*计算左子数的高度*/ rh=btheight(BT-rchild);/*计算右子数的高度*/ if(lhnum=lh-rh;/*计算结点的平衡因子*/ return t+1

19、4.3 程序分析 结点的平衡因子等于其左子树结点层次减去其右子树结点层次，因此要想求得每个结点的平衡因子，就得在遍历每个结点的时候，算出其左，右子树的层次，程序中用到了递归调用子函数 btheight(bitnode *bt)，以求出每个节点的左右子树的高度，然后作差，结果保留在 bt-num 中，最后结果用 return.返回 欢迎下载 第 5 章 总结 这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需

20、要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序。 刚开始学的时候确实有很多地方我很不理解， 每次上上机课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。TC 里检查错误都是用英文来显示出来的，经过了这次课程设计，现在已经可以了解很多错误在英文里的提

21、示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。 其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。 欢迎下载 本人签字： 欢迎下载 参考文献 1 徐孝凯编著. 数据结构M第一版.北京:机械工业出版社.1996 年 7 月 2 陈文博编著.数据结构M第二版.北京:机械工业出版社.1996 年 8 月 3 许卓群编著.数据结构M第一版.北京:高等教育出版社.1988 年 7 月 4 李廉治编著.数据结构教程M第一版.北京:大连理工大学出版社.1989 年 1 月 5 晋良颍编著.数据结构简明教程M第三版.南京:人民邮电出版社.2003 年 2 月