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

1、数据结构课程设计（论文）树的综合操作院（系）名称专业班级学号学生指导教师起止时 间： 2014.12.29 课程设计（论文）任务及评语号 学课程设计论文>任务保轧保 并O灿 叉 构裂 二 储O竝 构 皿序能 何 建卸切 用 创4非划 采 。(1)®* nao匕匕雀 :树5)， 擲个破 咖划构 ，各可 3二； 结 晰用乂<0 树 形 清调M収 mM二 F 界计 Mddf 剿J3层 辑r、壬cc用 m遡现>-正有爪型 K:號非皿K:时怵桃用据 WM遡W数)0钿系利妳 <:.；4):1>!<23>4>鼻 任 存-技 链指导教师评语及成绩日月

2、绩?:年 指成辩成轨 时 成 平 总教研室：软件工程院（系）：电子与信息工程学院注：平时成绩占20%，答辩成绩占40%，论文成绩占40%。摘要这次的课题主要是创建二叉树的存储结构并保存，通过这一过程了解并掌握 数据结构与算法的设计方法，具备初步的独立分析和设计能力并提高综合运用所 学的理论知识和方法独立分析和解决问题的能力主要解决以下问题 创建二叉树的存储结构并保存； 非递归实现中序遍历二叉树； 非递归实现先序遍历二叉树； 递归实现层次遍历二叉树； 求出二叉树的叶子节点数和层次树；关键词： 存储结构；二叉树； C+目录第1章 绪论 11.1系统的开发背景 11.2开发工具及语言 1第2章 概要

3、设计 22.1模块划分 22.2 数据结构的选择 2第 3 章 系统详细设计与编码 23.1完整的源程序 23.2 程序的输入和输出 错. 误!未定义书签。3.3调试程序中遇到的问题及解决方案 14第4章 思考题解析 154.1 思考题的选择 154.2类C算法154.3 程序分析 16第5章 总结 17参考文献 18附 录 错. 误!未定义书签。第 1 章 绪论1.1 系统的开发背景二叉树结构是 C 语言中的难点，但是近年来二叉树的应用越发的广泛，实用性越来 越强。为了应对日新月异的时代变化，我参与了这个课题来提高自己对二叉树的掌握1.2 开发工具及语言本系统使用Viscal C+语言开发，

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

5、3.1 完整的源程序#include<iostream.h> #include<stdlib.h> #include<stdio.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MaxSize 100 typedef char TElemType; typedef int Status;/二叉树的链式存储结构 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; /栈

6、的链式存储结构 typedef struct LNode BiTree 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 &

7、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;elsereturn ERROR;/以先序次序建立二叉树Status CreatBiTree(BiTree &T)TElemType ch;cin>>ch;if(ch='#') T=NULL;elseif(!(T=(BiTre

8、e)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;ret

9、urn T;/返回树头结点void Inorder_I(BiTree T)BiTree t;LinkList S;S=(LinkList)malloc(sizeof(LNode);S->next=NULL;t=GoFarLeft(T,S);/找到最左下的结点while (t)cout<<t->data<<" "if(t->rchild) t=GoFarLeft(t->rchild,S);else if(!StackEmpty(S)/栈空表明遍历结束Pop(S,t);else t=NULL;/while cout<<

10、endl; /Inorder_I /先序非递归遍历 算法 1 void PreOrder1(BiTree T) BiTree StackMaxSize,p;/定义栈int top=0;p=T;while (p!=NULL|top>0)while(p!=NULL) cout<<p->data<<" " / 输出结点 data Stacktop=p; /左树进栈 top+;p=p->lchild;if(top>0)top-;p=Stacktop;p=p->rchild; cout<<endl;/先序遍历非递归 算

11、法 2void PreOrder2(BiTree b)LinkList stack;BiTree p; p=(BiTree)malloc(sizeof(BiTree); stack=(LinkList)malloc(sizeof(LinkList); stack->next=NULL;Push(stack,b);/二叉树头结点进栈while(!StackEmpty(stack) / 是否为空 Pop(stack,p);/ 出栈while (p)cout<<p->data<<" " /输出当前指向结点 if(p->rchild)Pus

12、h(stack,p->rchild); / 访问右指点 p=p->lchild; cout<<endl; /后序非递归遍历 void PostOrder(BiTree T)BiTree stackMaxSize,p;int top=0;p=T;dowhile (p!=NULL) stack+top=p; p=p->lchild;while (top>0&&stacktop->rchild=p)p=stacktop-;/栈顶结点出栈cout<<p->data<<" " /访问 p 所指向的

13、结点 if (top>0)p=stacktop->rchild; / 开始遍历右子树 while(top>0);cout<<endl; /计算叶子结点的个数 void CountLeaf(BiTree T,int &count)if(T)if(!T->lchild)&&(!T->rchild)count+;CountLeaf(T->lchild,count); /左子树叶子个数 CountLeaf(T->rchild,count); /右子树叶子个数 /CountLeaf /计算双结点个数 void CountPar

14、ent(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 CountCh

15、ild(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=Dept

16、h(T->lchild);/左子树高度depthRight=Depth(T->rchild);/ 右子树高度/取高度最高depthval=1+(depthLeft>depthRight ?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)|(NodeLev

17、el(T->rchild,p,count) count+;return 1;return 0;/主函数void main()char flag;cout«"操作选项"<<endl;cout<<"1,非递归打印二叉树(前序，中序，后序)"<<endl;"<<endl;cout<<"2,计算二叉树的结点总数，双孩子个数，单孩子结点数，叶子结点数目cout<<"3,计算二叉树的高度"<<endl;cout<<&

18、quot;4,判断结点的层次"<<endl;doint item;coutvv"请输入要操作的选项(1-6):"cin>>item;switch (item)case 1 :BiTree T;cout<<" 请输入要建立的二叉树 ,以'#'表示空树 "<<endl; CreatBiTree(T);coutvv"先序非递归输出二叉树(两种算法)"<<endl;cout«"算法 1:"<<e ndl;PreOrd

19、er1(T);cout«"算法 2:"<<endl;PreOrder2(T);coutvv"中序非递归输出二叉树"<<endl;Inorder_I(T);coutvv"后序非递归输出二叉树"<<endl;PostOrder(T);coutvvendl;coutvv"是否继续操作？(y/n)"v<endl;cin>>flag;break;case 2:BiTree T;int nodeCount=0,leafCount=0,childCount=0,pa

20、rentCount=0; coutvv"请输入要建立的二叉树，以'#'表示空树"vvendl;CreatBiTree(T);Count(T,nodeCount);CountParent(T,parentCount);CountChild(T,childCount);CountLeaf(T,leafCount);coutvv"结点总数目为:"vvnodeCountvvendl;cout<<" 双孩子结点数目 :"<<parentCount<<endl;cout<<"

21、; 单孩子结点数目 :"<<childCount<<endl;cout<<" 叶子结点数目 :"<<leafCount<<endl;cout<<" 是否继续操作 ?(y/n)"<<endl;cin>>flag;break;case 3:BiTree T;cout<<" 请输入要建立的二叉树 ,以'#'表示空树 "<<endl;CreatBiTree(T);cout<<"

22、 该二叉树的高度为 :"<<Depth(T)<<endl;cout<<" 是否继续操作 ?(y/n)"<<endl;cin>>flag;break;case 4:BiTree T;int n=0;char ch;cout<<" 请输入要建立的二叉树 ,以'#'表示空树 "<<endl;CreatBiTree(T);coutvv"请输入要查询的结点："；cin>>ch;if(T=NULL)cout«&quo

23、t;空树"<<e ndl;elseNodeLevel(T,ch,n);coutvv"结点的层次为:"coutv <n+1<<e ndl;cout«"是否继续操作?(y/n)"«endl;cin> >flag;break;default : coutvv"无此选项请确定后再输入!"<<endl;break; while (flag='y'|flag='Y');3.2程序的输入和输出创建二叉树的操作如图3.1所示操2,3,树

24、点度 叉書次选 二的的层的 印作 项归二二结要 选递3耳断人单孩子结点数,叶子结点数目图3.1非递归先，中，后序排列如图3.2所示图3.2计算二叉树结点总数，双孩子单孩子结点数，叶子结点数如图3.3所示f以项叉 2 选二=2:1才 的的#:6目目-3?< 怅立fftmln作 要要AAS子子结继 鞭器点孩孩子否 请请ab结双单叮疋图3.3判断二叉树高度如图3.4所示请抛A要剰乍妙选顶q-计:3 请扁入要畫立的二叉树以呻表示空树abdttttScettttfttn图3.4判断结点层次如图3.5所示ill咅谿戒 匸表示空树abdttltttcettltntttfiller较養釐鱷饗罚常表示空树

25、图3.53.3调试程序中遇到的问题及解决方案问题：首先要按照提示输入，在创建二叉树的时候，要注意二叉树的输入，要用“ #”代替空，否则程序不能正确运行；每次执行新的任务的时候都要重新输入新的二 叉树。解决方案：按照先序遍历输入二叉树，如果结点左孩子或右孩子为空则用“#”代替；求叶子结点数和求层次时，所先用的子函数中的参数初始赋值为零，再从头结点 出发开始计数，直到所求结点。第 4 章 思考题解析4.1 思考题的选择所选择的思考题：编写一个算法，求一颗二叉树中每个结点平衡因子4.2类C算法int btheight(BitTNode *BT)int lh,rh,t;if(BT=NULL)return 0;elselh=btheight(BT->lchild);/* 计算左子数的高度 */ rh=btheight(BT->rchild);/* 计算右子数的高度 */ if(lh<=rh)t=rh;elset=lh;BT->num=lh-rh;/* 计算结点的平衡因子 */return t+14.3 程序分析结点的平衡因子等于其左子树结点层次减去其右子树结点层次，因此要想求得每 个结点的平衡因子，就得在遍历每个结点的时候，算出其左，右子树的层次，程序中用 到了递归调用子函数btheight(bit node *bt)，以求出每个节点的左右子树的高度，然后作差