二叉排序树问题说明书

目录摘要 (1)1.采用类C语言定义相关的数据类型 (2)2.各模块的伪码算法 (2)3.函数的调用关系图 (3)4.调试分析 (4)5.测试结果 (5)6.源程序（带注释） (7)总结 (10)参考文献 (11)致谢 (12)附件Ⅰ任务一源程序代码 (13)摘要本次课程设计要求学生设计程序，实现二叉树的相关操作。

在设计过程中，加深对二叉树的逻辑结构、存储结构的理解，掌握二叉树上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会把学到的知识用于解决实际问题，培养学生的动手能力。

在本次课程设计中，二叉排序树以二叉链表作为存储结构，主要实现了在Microsoft visual c++ 6.0环境下二叉排序树的创建、计算平均查找长度、中序遍历、插入结点、查找结点、删除结点以及判断是否是平衡二叉树等七大功能。

关键词：二叉排序树；中序遍历；平均查找长度；查找结点；删除结点1.采用类c语言定义相关的数据类型typedef struct tree //声明树的结构{int key; //存放节点的内容int other ;struct tree *lchild,*rchild; //存放左、右子树的指针}Bsttree; //声明二叉树的链表2.各模块的伪码算法(1) 二叉树创建算法为代码如下：1.先建立结构体typedef struct tree，声明树的结构；2.设置一个int key，用来存放结点的内容；3.建立struct tree 类型指针*lchild,*rchild，用来存放二叉树的左右子树。

（2）二叉排序树插入算法伪代码如下：1．若root是空树，则将结点s作为根结点插入；否则2. 若s->data＜root->data，则把结点s插入到root的左子树中；否则3. 把结点s插入到root的右子树中。

（3）二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1. 若结点p是叶子，则直接删除结点p；2. 若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3. 若结点p的左右子树均不空，则3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s。

（4）计算二叉排序树平均查找长度的算法的伪代码如下：1.设置int i用来记录当前结点的在当前树中的深度；2.设置*s，用来记录已遍历过的点的深度之和；3.计算左子树的ASL,记录树中结点的数目，计算右子树的ASL；4.比较左右子树的的ASL，大的就是二叉树的平均查找长度。

3.函数的调用关系图主菜单menu() 1.创建并输出二树CreateBST()2.计算平均查找长度calculateASL()3.插入结点InsertBST()4.查找并删除Bsearch(),DeleteBST()5.层序遍历LevelTravel()6.平衡二叉树判断balanceBST()7.先序遍历Preorder()8.中序遍历Inorder()9.后续遍历Postorder()10.退出4.调试分析a、调试中遇到的问题及对问题的解决方法用随机函数产生二叉树的结点，插入到原有的空二叉树中去。

由于for（）循环应用不当，产生的个数不足。

后来用给随机函数产生的值取余来控制结点值范围，采用一维数组存储随机函数产生的值并赋给结点，可以正常创建二叉树。

刚开始创建并输出的二叉树连在一起，无法分清。

最后改变了遍历输出时的格式控制符，增加了空格键之后，输出正常。

b、算法的时间复杂度和空间复杂度二叉排序树的查找与二分查找类似，是一个逐渐缩小查找范围的过程。

具有n个结点的二叉排序树是一棵深度为n的单枝树，平均查找长度与顺序表查找相同，为（n+1）/2，即平均查找长度的数量级为O（n）。

算法所需要的存储空间分为三部分：输入数据所占用的空间、程序代码所占用的空间和辅助变量所占用的空间。

一般以最坏情况下的空间复杂度作为算法的空间复杂度，故算法的空间复杂度为O（n）。

5.测试结果（1）.创建并输出一个任意结点个数的二叉树，如图：（2）.计算二叉树的平均查找长度，如图：（3）.查找并删除某个特定结点，如图：（4）.判断是否是平衡二叉树，并分别先序、中序、后序遍历二叉树，如图：6.源程序（带注释）Bsttree *CreateBST() //创建一个新的二叉树{int i;Bsttree *t;int key[N], n;t=NULL; //设置二叉排序树的初态为空printf("请输入二叉树结点个数:");scanf("%d",&n);for(i=0;i<n;i++){key[i]=rand()%999+1;t=InsertBST(t,key[i]);} return t;}Bsttree *Bsearch(Bsttree *t,int x) //查找{Bsttree *p;int flag=0;p=t;while(p!=NULL){ if(p->key==x){ printf("已找到该节点！");flag=1;return(p);break;}if (x<p->key)p=p->lchild;else p=p->rchild;}if(flag==0){printf("找不到值为%d的节点！",x); return NULL; }}Bsttree *InsertBST(Bsttree *t,int x) //插入{Bsttree *s,*p,*f;p=t;while (p!=NULL){f=p; //查找过程中，f指向*p的父节点if(x==p->key) return t; //二叉排序树中已有关键字为x的元素，无序插入if(x<p->key) p=p->lchild;else p=p->rchild;}s=(Bsttree *)malloc(sizeof(Bsttree));s->key=x;s->lchild=NULL;s->rchild=NULL;if(t==NULL) return s; //原树为空，新节点成为二叉排序树的根if(x<f->key) f->lchild=s; //新节点作为*f的左孩子else f->rchild=s; //新节点作为*f的右孩子return t;}int calculateASL(Bsttree *t,int *s,int *j,int i) /*计算平均查找长度*/{if(t){i++; /*i记录当前结点的在当前树中的深度*/*s=*s+i; /*s记录已遍历过的点的深度之和*/if(calculateASL(t->lchild,s,j,i))/*计算左子树的ASL*/{ (*j)++; /*j记录树中结点的数目*/if(calculateASL(t->rchild,s,j,i)) /*计算右子树的ASL*/{i--; return(1);}}else return(1);}}int balanceBST(Bsttree *t,int *i) /*判断是否为平衡二叉树的函数*/{int dep1,dep2;if(!t) return(0);else{dep1=balanceBST(t->lchild,i);dep2=balanceBST(t->rchild,i);}if((dep1-dep2)>1||(dep1-dep2)<-1) *i=dep1-dep2;/*用i值记录是否存在不平衡现象*/if(dep1>dep2) return(dep1+1);else return(dep2+1);void LevelTravel(Bsttree *T) //层序遍历{int i; Bsttree *t[100];//将树的每个结点按一定编号存储到一维数组中printf("层序遍历为：\n");for(i=0;i<100;i++) t[i]=NULL;if(T!=NULL) t[1]=T;//根结点编号下标为1for(i=1;i<100;i++)if(t[i]!= NULL){if(t[i]->lchild != NULL)//若有左子树t[2*i]=t[i]->lchild;//存储左子树根结点if(t[i]->rchild!=NULL)//若有右子树t[2*i+1]=t[i]->rchild;//存储右子树根结点printf("%4d ",t[i]->key);//按数组顺序打印出各结点元素}printf("\n");}}}总结两个星期过去了，终于圆满完成了课程设计的所有预期目标。

通过这次的课程设计，我认识到：单一的掌握课本上的知识是远远不够的。

在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。

不过，经过自己阅读大量的参考资料、不断的思考，尝试着去修改代码中出现的问题，情况渐渐有所好转。

虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做好了准备。

个人的力量是薄弱的。

在本次课程设计中，我学会了咨询别人，不再胆怯，不再保守。

在请教老师、和同学相互讨论的过程中，不断进步。

这次课程设计也让我体会到了作为一个编程人员的艰难。

一个算法到具体实现，再到应用层面的开发需要走一段很长的路，不是一朝一夕就可以完成的，而且在编写好程序后，编程人员还要花很多的时间去测试，完善它，其中的辛苦，难以言尽。

看到完成并打印后的课程设计，心里充满了一种无法用言语来形容的欣慰，我终于成功了。

今后，我会继续更加努力的学习专业知识，提高自我的能力，实现自己的人生价值。

参考文献[1] 严蔚敏，吴伟民.数据结构（C语言版)[M].北京:清华大学出版社.2007[2] 严蔚敏，吴伟民.数据结构题集（C语言版)[M].北京:清华大学出版社.1999[3] William Ford,William Topp .DATA STRUCTURE WITH C++[M].清华大学出版社（影印版）.1991.[4] 谭浩强.c语言程序设计[M]. 北京:清华大学出版社.2008.[5] 朱战立.数据结构(Ｃ语言描述)[M].北京：高等教育出版社，2004.致谢首先感谢本次课程设计的指导老师张永老师，他在我的课程设计开始就针对我的设计题目提出了指导性的方案和架构，为我本次的课程设计指明了方向。