数据结构课程设计完全二叉树操作演示

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 完全二叉树操作演示 专业 计算机科学与技术 班级 10计本2班 学号10012131 姓名 联系方式 指导教师 2011 年 12 月 27 目 录1、数据结构课程设计任务书1.1、题目1.2、要求2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计3.1、程序中所采用的数据结构及存储结构的说明3.2、算法的设计思想3.3、稀疏矩阵各种运算的性质变换4、调试与测试：4.1、调试方法与步骤：4.2、测试结果的分析与讨论：5、时间复杂度的分析：6、源程序清单和执行结果7、c程序设计总结8、致谢9、参考文

2、献1、数据结构课程设计任务书1.1、题目完全二叉树的操作演示1.2、要求（1）创建完全二叉树（2）实现二叉树的前序、中序和层次遍历（3）求二叉树的深度和叶子结点数（4）查找给定结点的双亲，祖先和左右孩子结点2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：建立结点左右孩子结束遍历二叉树创建二叉树二叉树的查找3、详细设计3.1、程序中所采用的数据结构及存储结构的说明1顺序存储结构#define max_tree_size 100typedef telemtype sqbitree【max_tree_size】；sqbitree bt;用一组地址连续的存储单元

3、一次自上而下，自左至又，存储完全二叉树上的节点元素,即将完全二叉树上编号为i节点元素存储在如上定义的一维数组中下标为i1的分量中。2链式存储结构由二叉树的定义可知，二叉树的节点由一个数据元素和分别指向其左右子树的两个分支构成。表示二叉树的结点至少要包含3个域：数据域，左右指针，还可增加一个指向双亲的结点，称三叉链表。链表的头指针指向二叉树根节点。3.2、算法的设计思想对一棵有n个结点完全二叉树的结点按层序编号，则对任一结点i,有（1）如果i=1，则结点i是二叉树的根，无双亲；如果i1,则双亲是i/2(2)如果2in,则结点i无左孩子;否则其左孩子lchild(i)是结点2i。（3）如果2i+1

4、n,则结点i无右孩子；否则其右孩子rchild（i）是结点2i+1.3.3、二叉树的遍历先序遍历：（1）访问根节点（2）先序遍历左子树（3）先序遍历右子树中序遍历：（1）中序遍历左子树（2）访问根节点（3）中序遍历右子树后序遍历：（1）后序遍历左子树（2）后序遍历右子树（3）访问根节点status preordertraverse（ bitree t,status( * visit)(telemtype)）/采用二叉链表存储结构，visit是对数据元素操作的应用函数。status printelement（ telemtype）printf（e）；return ok；if (t)if (vis

5、tit(t-data) if (preordertraverse(t-lchild,visit) if (preordertraverse(t-rchild,visit) return ok;return error;else return ok; status inordertravserse(bitree t,status (*visit)(telemtype)/采用二叉树链表存储结构，visit是对数据元素操作的应用函数initstack(s); push (s,t);while (!stackempty(s)while(gettop(s,p) &p)push(s,p-lchild);p

6、op(s,p);if (!stackempty(s)pop(s,p); if (!visit(p-data) return error;push(s,p-rchild);return ok;status createbitree(bitree &t)/按先序次序输入二叉树中的节点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树。scnaf（&ch）;if (ch =)t=null;elseif (!(t=(bitnode * )malloc(sizeof(bitnode) exit(overflow);t-data=ch;createbitree(t-lchild);createb

7、itree(t-rchild);return ok;4、调试与测试：调试方法与步骤：（1）测试二叉树的存储结构是否正确（2）测试二叉树的遍历是否正确（3）测试二叉树的查找是否正确（4）测试二叉树的输出是否正确6、源程序清单#include #define null 0#define maxsize 100typedef struct nodechar data; struct node *lch; struct node *rch;btnode;int count = 0;void creatbttree(btnode *&t,char *s)btnode *stmaxsize,*p=null

8、;int top=-1,k,j=0; char ch; t=null;ch=sj;while(ch!=0)switch(ch)case (:top+; sttop=p; k=1; break; case ):top-; break;case ,:k=2; break;default:p=new btnode;p-data=ch;p-lch=null;p-rch=null;if(t=null)t=p;elseswitch(k)case 1:sttop-lch=p;break;case 2:sttop-rch=p; break;j+；ch=sj;void dispbttree(btnode *t)

9、if(t!=null)coutdata;if(t-lch!=null)|(t-rch!=null)coutlch);if(t-rch!=null)coutrch)；coutdata=x)return t;elsep=findnode(t-lch,x);if(p!=null)return p;else return findnode(t-rch,x);void preorder (btnode *t)if(t!=null)cout data lch);preorder (t-rch);void inorder (btnode *t)if(t!=null)preorder (t-lch);cout

10、 data rch);void postorder (btnode *t)if(t!=null)preorder (t-lch);preorder (t-rch);cout data lch);rchildh = btnodedepth (t-rch);return (lchildh rchildh) ? (lchildh + 1) : (rchildh + 1); int countnode (btnode *t)int num;if (t = null)num = 0;else num = 1 + countnode (t-lch) + countnode (t-rch)；return (

11、num);void countleaf (btnode *t)if (t != null)if (t-lch = null & t-rch = null)count +;countleaf (t-lch);countleaf (t-rch);void main()char x；btnode *t=null,*p=null;creatbttree(t,a(b(,d),c);cout创建的树是：;dispbttree(t);coutendl;cout请输入要查找的结点：x;p=findnode(t,x);if(p=null)cout不存在！lch=null)cout没有左孩子！endl;else

12、cout左孩子是：lch-datarch=null)cout没有右孩子！endl;else cout右孩子是：rch-dataendl;cout 按先序遍历树为：;preorder (t);cout endl;cout 按中序遍历树为：;inorder (t);cout endl;cout 按后序遍历树为：;postorder (t);cout endl;cout 节点总数为：;cout countnode (t) endl;cout 叶子节点个数为：;countleaf(t);cout count endl;cout 这棵树的深度为：;cout btnodedepth (t);cout endl; 7、c程序设计总结程序的编写需要耐心，跟需要细心。程序的调试过程中会出现很