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

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章 绪论11.1系统的开发背景11.2开发工具及语言1第2章 概要设计12.1模块划分12.2 数据结构的选择1第3章 系统详细设计与编码23.1完整的源程序23.2程序的输入和输出33.3调试程序中遇到的问题及解决方案4第4章 思考题解析54.1 思考题的选择54.2类C算法54.3程序分析5第5章 总结6参考文献7附 录8II第1章 绪论1.1系统的开发背景二叉树结构是C语言中的难点，但是近年来二叉树的应用越发的广泛，实用性越来越强。为了应对日新月异的时代变化，我参与了这个课题来提高自己对二叉树的掌握1.2开

4、发工具及语言本系统使用Viscal C+语言开发，主界面清晰显示所有功能项，使用简单。各个功能项均定义一个函数来实现，在主函数中调用各个子函数实现不同的功能。第2章 概要设计2.1模块划分1）题目应实现的具体功能；创建二叉树的存储结构并保存；非递归实现中序遍历二叉树；非递归实现先序遍历二叉树；递归实现层次遍历二叉树；求出二叉树的叶子节点数和层次树；2.2 数据结构的选择系统数据的逻辑结构采用树形结构，物理结构采用链式存储结构（二叉链表）。存储结构定义如下：typedef struct lnodechar data;struct lnode *lchild,*rchild;lnode,*tree

5、;第3章 系统详细设计与编码3.1完整的源程序#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 LNo

6、de *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

7、;/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); /生成

8、右子树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) co

9、utdatarchild) 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,

10、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 &coun

11、t)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&

12、(!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);

13、 /取高度最高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,计算二叉树的结点总数，双

14、孩子个数，单孩子结点数，叶子结点数目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; PostO

15、rder(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双孩子结点数目

16、: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); cou

17、tch; 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+14.3程序分析结点的平衡因子等于其左子树结点层次减去其右子树结点层次，因此要想求得每个结点的平衡因子，就得在遍历每个结点的时候，算出其左，右子树的层

18、次，程序中用到了递归调用子函数 btheight(bitnode *bt)，以求出每个节点的左右子树的高度，然后作差，结果保留在bt-num中，最后结果用return.返回第5章 总结这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序。刚开始学的时候确实有很多地方我很不理解，每次上上机课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定