数据结构实验
实验四
二叉树的建立及相关算法的实现
计算机科学与技术系0901班
组 长： 组 员：
日 期：2011-05-05
二叉树的建立及相关算法的实现
2009级 0901班 2011年05月05日
实验类型：综合设计型 实验室：软件实验室三
组长： 组员：
1. 实验题目
二叉树的建立及相关算法的实现
2. 需求分析
本演示程序用VC++编写，实现了以下功能
① 建立一棵二叉树，然后对其进行先序、中序和后序遍历。 ② 显示二叉树
③ 求二叉树的高度及二叉树的叶子个数等等
④ 在主函数中设计一个简单的菜单，分别调试上述算法
3. 概要设计
为了实现上述程序功能，需要定义栈的抽象类型如下： ADT Stack{
数据对象：D={ai |ai∈ElemSet,i=1,2,…，n, n≧0}
数据对象：R1={ 约定an端为栈顶，ai端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。 }ADT Stack ADT Binary Tree{ 数据对象 D：D是具有相同特性的数据元素的集合。 基本操作 P： InintBiTree(&T) 操作结果：构造空二叉树T。 CreateBiTree(&T,definition); 初始条件：definition给出二叉树T的定义 操作结果：按definition构造二叉树T. 第一页 二叉树的建立及相关算法的实现 Preordertraverse(T,Visit()); 初始条件：二叉树T存在，Visit是对节点操作的应用函数。 操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次。一旦visit() 失败，则操作失败。 Inordertraverse(T,Visit()); 初始条件：二叉树T存在，Visit是对节点操作的应用函数。 操作结果：中序序遍历T，对每个节点调用函数Visit一次且仅一次。一旦visit() 失败，则操作失败。 Postordertraverse(T,Visit()) 初始条件：二叉树T存在，Visit是对节点操作的应用函数。 操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次。一旦visit() 失败，则操作失败。 Levelordertraverse(T,Visit()) 初始条件：二叉树T存在，Visit是对节点操作的应用函数。 操作结果：层序遍历T，对每个节点调用函数Visit一次且仅一次。一旦visit() 失败，则操作失败。 }ADT BinaryTree 本程序还包含个函数： （1） 计算叶子总数函数：int Sumleaf(BiTree T) （2） 左右子数交换函数：void jiaohuan(BiTree T) （3） 节点数计算函数：int jiedianshu(BiTree T) （4） 深度计算函数：int Depth(BiTree T) （5） 显示二叉树函数：void xianshi(BiTree T) 函数调用图如下： 主函数 构造二叉树 先 序 遍历 二叉树 中序遍历二叉树 后序遍历二叉树 层序遍历二叉树 输出二叉树的叶子数 输出二叉树的深度 显示二叉树 非递归先序遍历二叉树 非递归中序遍历二叉树 非递归后序遍历二叉树 左右子树交换 输出二叉树的节点数 返回 第二页 二叉树的建立及相关算法的实现 4． 详细设计 #include struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef struct{ BiTNode *base; BiTNode *top; int stacksize; }sqstack; void initstack (sqstack *s) //建栈 {s->base=(BiTNode *)malloc(maxqsize * sizeof(BiTNode)); if(!s->base) printf(\"存储空间失败!\"); else {s->top=s->base; s->stacksize=maxqsize;}} void push(sqstack *s,BiTNode e) //压栈 {if(s->top-s->base==s->stacksize) {s->base=(BiTNode sizeof(BiTNode)); *)realloc(s->base,(s->stacksize+stackincrement) * if(!s->base) printf(\"存储空间失败\"); else {s->top=s->base+s->stacksize;s->stacksize+=stackincre *(s->top)=e; s->top++;} BiTNode pop(sqstack *s) //弹出 {s->top--;return *s->top;}int sety(sqstack *s) {if(s->top==s->base) return 1; else return 0;} BiTree Create(BiTree T) //构造二叉链表 { char ch; ch=getchar(); if(ch=='@') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf(\"Error!\"); T->data=ch; T->lchild=Create(T->lchild); T->rchild=Create(T->rchild); } 第三页 二叉树的建立及相关算法的实现 return T; } void Preordertraverse(BiTree T) //先序遍历 { if(T) { printf(\"%c \ } void fPreordertraverse(BiTree T) //非递归先序遍历 {sqstack s; BiTree p=T; initstack (&s); if(p) push(&s,*p); while(!sety(&s)) {p=(BiTNode *)malloc(sizeof(BiTNode)); *p=pop(&s); printf(\"%c \push(&s,*(p->rchild)); if(p->lchild) push(&s,*(p->lchild));}} int Sumleaf(BiTree T) //叶子总数 { int sum=0,m,n; if(T) { if((!T->lchild)&&(!T->rchild)) sum++; m=Sumleaf(T->lchild); sum+=m; n=Sumleaf(T->rchild); sum+=n; } return sum; } void jiaohuan(BiTree T) //左右子数交换 {BiTree temp; if(T) {temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; jiaohuan(T->lchild); jiaohuan(T->rchild); return -1; } else return 0;} void Inordertraverse(BiTree T) //中序遍历 { if(T) { Inordertraverse(T->lchild); printf(\"%c \ Inordertraverse(T->rchild); }} void fInordertraverse(BiTree T) //非递归中序遍历 {sqstack s; BiTree p=T; initstack (&s); while(p||!sety(&s)) {while(p) {push(&s,*p); p=p->lchild;} if(!sety(&s)) {p=(BiTNode *)malloc(sizeof(BiTNode)); *p=pop(&s); printf(\"%c \int jiedianshu(BiTree T) //节点数数目 第四页 二叉树的建立及相关算法的实现 {if(T==NULL) return 0; else return(jiedianshu(T->lchild)+jiedianshu(T->rchild)+1); } void Postordertraverse(BiTree T) //后序遍历 { if(T) { Postordertraverse(T->lchild); Postordertraverse(T->rchild); printf(\"%c \void fPostordertraverse(BiTree T) //非递归后序遍历 {sqstack s; BiTNode p, *l, *r; initstack(&s);push(&s,*T); while(!sety(&s)) { p=pop(&s); l=p.lchild; r=p.rchild; if (l==NULL && r==NULL) {printf(\"%c \ else {p.lchild = NULL; p.rchild = NULL; push(&s, p); if (r != NULL) push(&s, *r); if (l != NULL) push(&s, *l) } } int Depth(BiTree T) //二叉树深度 { int dep=0,depl,depr; if(!T) dep=0; else { depl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?depl:depr); } return dep; } void xianshi(BiTree T) //显示二叉树 {BiTree stack[100],p; int leave[100][2],top,n,i,width=4; if(T!=NULL) 第五页 二叉树的建立及相关算法的实现 top=1; stack[top]=T; leave[top][0]=width; while(top>0) {p=stack[top]; n=leave[top][0]; for(i=1;i<=n;i++) printf(\" \"); printf(\"%c\for(i=n+1;i<50;i++) printf(\"-\"); printf(\"\\n\"); top--; if(p->rchild!=NULL) {top++; stack[top]=p->rchild; leave[top][0]=n+width; } if(p->lchild!=NULL) {top++; stack[top]=p->lchild; leave[top][0]=n+width; } } } void Levelordertraverse(BiTree T) //层序遍历二叉树 {int i,j; BiTree q[100],p; p=T; if(p!=NULL) {i=1;q[i]=p;j=2; } while(i!=j) 第六页 二叉树的建立及相关算法的实现 {p=q[i]; printf(\"%c \if(p->lchild!=NULL) {q[j]=p->lchild; j++; } if(p->rchild!=NULL) {q[j]=p->rchild; j++; } i++; } } void main() { BiTree T=NULL; int sum,dep,sun; int ch1,ch2,a; ch1=1; while(ch1) { printf(\"\\n\"); printf(\" 二叉树子系统 \\n\"); printf(\"*************************\\n\"); printf(\"* 1--建立一棵二叉树 *\\n\"); printf(\"* 2--先序遍历二叉树 *\\n\"); printf(\"* 3--中序遍历二叉树 *\\n\"); printf(\"* 4--后序遍历二叉树 *\\n\"); printf(\"* 5--层序遍历二叉树 *\\n\"); printf(\"* 6--二叉树的叶子数 *\\n\"); printf(\"* 7--输出二叉树的深度 *\\n\"); printf(\"* 8--显示二叉树 *\\n\"); printf(\"* 9--非递归先序遍历 *\\n\"); printf(\"* 10--非递归中序遍历 *\\n\"); printf(\"* 11--非递归后续遍历 *\\n\"); printf(\"* 12-- 左右子树交换 *\\n\"); 第八页 二叉树的建立及相关算法的实现 printf(\"* 13--二叉树的节点数 *\\n\"); printf(\"* 0--返 回 *\\n\"); printf(\"*************************\\n\"); printf(\"提示：“空”用@表示\\n\"); printf(\" 请输入你的选项:\"); scanf(\"%d\ printf(\"\\n\"); getchar(); switch(ch2) {case 1: printf(\"请输入先序序列:\"); T=Create(T); printf(\"\\n您的树已经建立好!\\n\\n\"); break; case 2: printf(\"此二叉树的先序遍历是:\"); Preordertraverse(T); printf(\"\\n\");break; case 3: printf(\"此二叉树的中序遍历是:\"); Inordertraverse(T); printf(\"\\n\"); break; case 4: printf(\"此二叉树的后续遍历是:\"); Postordertraverse(T); printf(\"\\n\"); break; case 5: printf(\"此二叉树的层序遍历是:\"); Levelordertraverse(T); printf(\"\\n\");break; case 6: printf(\"此二叉树的叶子树为:\"); sum=Sumleaf(T); printf(\"%d\case 7: 第九页 二叉树的建立及相关算法的实现 printf(\"此二叉树的深度为:\"); dep=Depth(T); printf(\"\\n%d\case 8: printf(\"此二叉树的凹回显示如下:\\n\"); xianshi(T); printf(\"\\n\");break; case 9: printf(\"非递归前序为：\"); fPreordertraverse(T); printf(\"\\n\");break; case 10: printf(\"非递归中序为：\"); fInordertraverse(T); printf(\"\\n\");break; case 11: printf(\"非递归后序为：\"); fPostordertraverse(T); printf(\"\\n\");break; case 12: jiaohuan(T);break; case 13: printf(\"此二叉树的节点总数是:\"); sun=jiedianshu(T); printf(\"%d \ case 0: } } } ch1=0;break; 5. 调试分析 第九页 二叉树的建立及相关算法的实现 调试程序时主要的错误是语法的错误，对函数的定义以及调用还不够熟悉。 6. 使用说明 （1）运行程序,界面如下： （2）输入“1”，先序建立一棵二叉树，界面如下： （3）输入“2”，先序遍历二叉树，界面如下： （4）输入“3”，中序遍历二叉树，界面如下： （5）输入“4”，后序遍历二叉树，界面如下： （6）输入“5”，层序遍历二叉树，界面如下： （7）输入“6”，得到二叉树的叶子数，界面如下： 第十页 二叉树的建立及相关算法的实现 （8）输入“7”，得到二叉树的深度，界面如下： （9）输入“8”，显示二叉树，界面如下： （10）输入“9”，非递归先序遍历二叉树，界面如下： （11）输入“10”，非递归中序遍历二叉树，界面如下： （12）输入“11”，非递归后序遍历二叉树，界面如下： （13）输入“12”，左右子树交换，之后显示二叉树。界面如下： （14）输入“13”，输出二叉树的节点数，界面如下： 第十一页 二叉树的建立及相关算法的实现 （15）输入“0”，返回。 7. 测试结果 运行程序 》输入“1”，先序建立一棵二叉树，输入“ab@@c@@”建立二叉树完成。 》输入“2”，先序遍历二叉树，结果为：abc 》输入“3”，中序遍历二叉树，结果为：bac 》输入“4”，后序遍历二叉树，结果为：bca 》输入“5”，层序遍历二叉树，结果为：abc 》输入“6”，得到二叉树的叶子数，结果为：2 》输入“7”，得到二叉树的深度，结果为：2 》输入“8”，显示二叉树，abc 》输入“9”，非递归先序遍历二叉树，abc 》输入“10”，非递归中序遍历二叉树，bac 》输入“11”，非递归后序遍历二叉树，bca 》输入“12”，左右子树交换，之后显示二叉树，acb 》输入“13”，输出二叉树的节点数，3 8. 实验总结 本程序由小组内的四个成员对各个模块进行编写，之后由我们共同对各个模块进行进行组合调试，期间经过了王春红老师的指导，让我们发现了我们许多的不足之处： (1) 许多概念性的知识还不够扎实，需要我们继续巩固。 (2) 各模块进行组合时，出现了许多错误，原因是组员之间没有对函数的定义名进行好的沟通，定义名出现了几种不同的写法。 9. 模块分工 王斌：建立二叉树及其各种遍历。 贺永林：二叉树的叶子数，树的深度。 郝云霞：凹回显示二叉树。 汤海平：主函数。 第十二页 因篇幅问题不能全部显示，请点此查看更多更全内容