二叉树的二叉链表表示

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 二叉树的二叉链表表示 专业 计算机科学与技术 班级 10计本2班 学号10012125姓名 张亚飞 联系方式导教师江家宝20 年 月 日目 录1、数据结构课程设计任务书1.1、题目1.2、要求2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计3.1、程序中所采用的数据结构及存储结构的说明3.2、算法的设计思想3.3、稀疏矩阵各种运算的性质变换4、调试与测试：4.1、调试方法与步骤：4.2、测试结果的分析与讨论：4.3、测试过程中遇到的主要问题及采取的解决措施：5、时间复杂

2、度的分析：6、源程序清单和执行结果7、C程序设计总结8、致谢9、参考文献1、数据结构课程设计任务书1.1、题目题目22：二叉树用二叉链表表示（1人完成）1.2、要求【设计要求】1 实现二叉树的建立、前序（非递归）、中序和层次遍历；2 求二叉树高度、结点数、度为1的结点数和叶子结点数；3 插入结点到指定位置、删除指定结点；4 将二叉树所有结点的左右子树交换。2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：#define maxsize 100 typedef struct Bitree Elemmaxsize; int top; SqStack; void

3、 PreOrderUnrec(Bitree t) SqStack s; StackInit(s); p=t; while (p!=null | !StackEmpty(s) 数据结构习题解 while (p!=null) /遍历左子树 visite(p->data); push(s,p); p=p->lchild; /endwhile if (!StackEmpty(s) /通过下一次循环中的内嵌 while 实现右子树遍历 p=pop(s); p=p->rchild; /endif /endwhile /PreOrderUnrec 6-12 写一算法求二叉树中结点的总数，可

4、以写出多少种方法？ 答案： #include <stdio.h> #include <stdlib.h> typedef struct node char data; /*此例中二叉树的结点采用字符类型*/ struct node *lchild, *rchild; NODE; NODE *crt_bt_pre( ) /*按先序遍历序列创建二叉树的二叉链表*/ /* 输入 ABC00DE0G00F000 */ NODE *bt; char ch; printf("nttt"); scanf("%c",&ch); getch

5、ar( ); if(ch=' ') bt=NULL; else bt=(NODE *)malloc(sizeof(NODE); bt->data=ch; printf("nttt 请输入%c 结点的左孩子：",bt->data); bt->lchild=crt_bt_pre( ); printf("nttt 请输入%c 结点的右孩子：",bt->data); bt->rchild=crt_bt_pre(); return(bt); 数据结构习题解 void CountNode(NODE* bt,int *p)

6、 /*统计二叉树中结点的总数*/ if(bt=NULL) return; else (*p)+; CountNode(bt->lchild,p); CountNode(bt->rchild,p); return; main() NODE *crt_bt_pre( ) CountNode(bt,&b); /*调用统计结点总数的函数*/ printf("nttt 该二叉树共有%d 个结点。n",b); 6-13 写一算法将二叉树中所有结点的左、右子树相互交换。 答案： #include "datastru.h" #include <

7、stdio.h> #include <malloc.h> #include "二叉树.c" BTCHINALR *change(BTCHINALR *bt) /*二叉树左右子树交换递归算法*/ BTCHINALR *p; if(bt!=NULL) if(bt->lchild!=NULL | bt->rchild!=NULL) p=(BTCHINALR*)malloc(sizeof(BTCHINALR); p->data=bt->data; p->rchild=NULL; p->lchild=bt->lchild;

8、bt->lchild=bt->rchild; bt->rchild=p->lchild; bt->lchild=change(bt->lchild); bt->rchild=change(bt->rchild); return bt; 输入矩阵12.2、所有功能模块的流程图【示例1】略3、详细设计模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等【示例1】中所采用的数据结构及存储结构的说明#include<iostream.h> #include<stdio.h> #include<iomanip.h&

9、gt; #include<malloc.h> #include<stdlib.h> #include<conio.h> #include<shlobj.h> #define MAXNODE 100 /树的建立 typedef struct bitnode char data; struct bitnode *lchild,*rchild; bitnode,*bintree; /二叉树的二叉链表的存储算法 void createbintree(bintree *t) char ch; cin>>ch; if(ch='0'

10、) (*t)=NULL; else (*t)=new bitnode; (*t)->data=ch; createbintree(&(*t)->lchild); createbintree(&(*t)->rchild); /9.中序遍历 void inorderout(bintree bt) if(bt!= NULL) inorderout(bt->lchild); /* 中序遍历左子树 */ printf("%c", bt->data); /* 访问根结点 */ inorderout(bt->rchild); /* 中序

11、遍历右子树 */ return; /* 11.按层遍历 */ void levelorder(bintree bt) bintree queueMAXNODE; int front,rear; if(bt=NULL) return; front=-1; rear=0; queuerear=bt; while(front!=rear) front+; cout<<queuefront->data; if(queuefront->lchild!=NULL) rear+; queuerear=queuefront->lchild; if(queuefront->r

12、child!=NULL) rear+; queuerear=queuefront->rchild; /* 6.输出二叉树(前序遍历) */ void printBTree(bintree bt) /* 树为空时结束递归，否则执行如下操作 */ if(bt!=NULL) printf("%c", bt->data); /* 输出根结点的值 */ if(bt->lchild!= NULL|bt->rchild!=NULL) printBTree(bt->lchild); if(bt->rchild!= NULL) printBTree(bt-

13、>rchild); return; /*求树的高度 */ int depth(bitnode *b) int dep1,dep2; if(b=NULL) return(0); else dep1=depth(b->lchild); dep2=depth(b->rchild); if(dep1>dep2)return(dep1+1); else return(dep2+1); /*所有叶子结点数 */ int countleaf(bintree bt) if(bt=NULL) return 0; if(bt->lchild=NULL&&bt->

14、rchild=NULL) return 1; return (countleaf(bt->lchild)+countleaf(bt->rchild); /*所有结点数 */ int btreecount(bintree bt) if(bt=NULL) return 0; else return btreecount(bt->lchild)+btreecount(bt->rchild)+1; void main() bintree bt; createbintree(&bt); printf("树的高度为：n"); printf("%

15、d",depth(bt); printf("n"); printf("叶子结点数为：n"); printf("%d",countleaf(bt); printf("n"); printf("所有结点数为：n"); printf("%d",btreecount(bt); printf("n"); printf("前序遍历为：n"); printBTree(bt); printf("n"); printf(&q

16、uot;中序遍历为：n"); inorderout(bt); printf("n"); printf("层次遍历为："); levelorder(bt); printf("n"); 4.2、测试结果的分析与讨论： （略）7、C程序设计总结【示例1】本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写