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

word数据结构课程设计(论文)树的综合操作 院系名称 专业班级 学号 学生 指导教师课程设计论文任务与评语院系：电子与信息工程学院 教研室：软件工程学号学生专业班级课程设计论文题目树的综合操作课程设计论文任务任务要求：树的综合操作实现以下几个功能：1创建二叉树的存储结构并保存；2非递归实现中序遍历二叉树3非递归实现先序遍历二叉树。4递归实现层次遍历二叉树；5求出二叉树的叶子结点数和层次数。技术要求：1、数据的逻辑结构采用树形结构，物理结构采用链式存储结构二叉链表。2、软件能正常运行，界面清晰，操作要简单。3、系统要有主界面设计，调用各个功能项。4、采用Viscal C+编写代码，可读性强。5、数据类型用typedef 定义。指导教师评语与成绩平时成绩：辩论成绩：论文成绩：总成绩：指导教师签字：年月日注：平时成绩占20%，辩论成绩占40%，论文成绩占40%。19 / 23摘 要这次的课题主要是创建二叉树的存储结构并保存，通过这一过程了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力并提高综合运用所学的理论知识和方法独立分析和解决问题的能力主要解决以下问题创建二叉树的存储结构并保存；非递归实现中序遍历二叉树；非递归实现先序遍历二叉树；递归实现层次遍历二叉树；求出二叉树的叶子节点数和层次树；关键词：存储结构；二叉树；C+目 录第1章绪论1系统的开发背景1开发工具与语言1第2章概要设计1模块划分12.2 数据结构的选择1第3章系统详细设计与编码2完整的源程序2程序的输入和输出3调试程序中遇到的问题与解决方案4第4章思考题解析54.1 思考题的选择5类C算法5程序分析5第5章总结6参考文献7附录8第1章 绪论系统的开发背景二叉树结构是C语言中的难点，但是近年来二叉树的应用越发的广泛，实用性越来越强。为了应对日新月异的时代变化，我参与了这个课题来提高自己对二叉树的掌握与语言本系统使用Viscal C+语言开发，主界面清晰显示所有功能项，使用简单。各个功能项均定义一个函数来实现，在主函数中调用各个子函数实现不同的功能。第2章 概要设计模块划分1题目应实现的具体功能；创建二叉树的存储结构并保存；非递归实现中序遍历二叉树；非递归实现先序遍历二叉树；递归实现层次遍历二叉树；求出二叉树的叶子节点数和层次树；2.2 数据结构的选择系统数据的逻辑结构采用树形结构，物理结构采用链式存储结构二叉链表。存储结构定义如下：typedef struct lnodechar data;struct lnode *lchild,*rchild;lnode,*tree;第3章 系统详细设计与编码完整的源程序#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define MaxSize 100typedef char TElemType;typedef int Status;/二叉树的链式存储结构typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/栈的链式存储结构typedef struct LNodeBiTree data;struct LNode *next;LNode,*LinkList;/进栈Status Push(LinkList& S,BiTree T)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)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; /创建成功/CreatBiTree/非递归中序访问二叉树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) coutdatarchild) t=GoFarLeft(t-rchild,S); else if(!StackEmpty(S) /栈空明确遍历完毕 Pop(S,t); else t=NULL;/whilecout0) 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,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 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-lchild&(!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;elsedepthLeft=Depth(T-lchild); /左子树高度depthRight=Depth(T-rchild); /右子树高度depthval=1+(depthLeftdepthRight ?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;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); 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); CountLeaf(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; 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结点的平衡因子等于其左子树结点层次减去其右子树结点层次，因此要想求得每个结点的平衡因子，就得在遍历每个结点的时候，算出其左，右子树的层次，程序中用到了递归调用子函数 btheight(bitnode *bt)第5章 总结这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候确实有很多地方我很不理解，每次上课时教师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。教师会给我们需要编程的容一些讲解，顺着教师的思路，来完成自己的设计，我们可以开始运行自己的程序。刚开始学的时候确实有很多地方我很不理解，每次上上机课时教师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。教师会给我们需要编程的容一些讲解，顺着教师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我屡次请教了教师和同学，逐渐能自己找出错误，并加以改正。TC里检查错误都是用英文来显示出来的，经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。本人签字：参考文献1 徐孝凯编著. 数据结构M第一版2 文博编著.数据结构M第二版3 许卓群编著.数据结构M第一版4 廉治编著.数据结构教程M第一版5 晋良颍编著.数据结构简明教程M第三版