数据结构报告正文.doc

1第一章1.1 数据结构课程设计要求1.1.1 数据结构课程设计问题描述从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作1.1.2 数据结构课程设计基本要求建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度1.2.1 数据结构课程设计测试数据由学生依据软件工程的测试技术自己确定注意测试边界数据1.2.2 数据结构课程设计的选作内容实现二叉排序树的插入、删除操作2第二章2.1 数据结构课程设计的算法思想为了实现任务书的几个要求，本次课程设计的算法思想主要包括以下三部分2.1.1 主菜单设计为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主菜单以实现对二叉排序树的各个操作本系统的主菜单界面如图 1 所示图 1.二叉排序树操作的主菜单2.1.2 存储结构的设计本程序主要采用二叉树结构类型来表示二叉排序树其中二叉树节点由 1 个表示关键字的 key 表示，还有指向该左孩子和右孩子的指针，通过 keykey 的 if 语句来判断，其中 p 表示二叉排序树2.2.1 系统功能的设计本程序设置了 5 个子功能菜单，其设计如下1)建立二叉排序树。

主要通过 Bstree Create()函数来实现根据系统提示，输入节点的关键字，二叉树上面的各个元素，并以-1 作为结束的标识符2)往二叉树当中插入数据主要通过 Bstree Insert(y)函数实现While 语句对二叉树状态的判断，通过 keykey，以及 key==p->key，对二叉树的左右之树进行定义，其中p 表示二叉排序树，每次只能够插入一个新的数据，不能插入已经存在的元素3)二叉树当中查找某数据主要通过 Bstree Search()函数实现每次进行查询，成功则显示“查询到该节点” ，不成功则“显示查询不到该节点，通过 if 语句对结点在二叉树当中左右子树进行判断4)遍历该二叉排序树主要通过 void Traverse()函数实现遍历二叉排序树可以显示该二叉排序树的全部节点信息如果一开始没有创造二叉树，还会提醒你先创建树在进行遍历3（5)删除二叉排序树当中某个数据主要通过 Bstree Delete()函数实现可以对二叉排序树中不需要的节点进行删除，通过对输入关键字的查找进行删除的操作，主要运用了队列的知识，头尾指针的定义来查找相关的数据6） 树状打印二叉排序树 主要通过 void TranslevelPrint(Bstree bt)函数实现。

通过队列当中的头尾指针定义到树的结点以及结点所在的层次从而确定打印之后结点应该到的位置While 语句主要对结点深度进行横向控制，使打印图形比较美观从而树状输出你定义的二叉排序树4第三章3.1 模块划分3.1.1 主程序与子程序之间的对应关系本程序主要分为两部分：主程序模块以及二叉树各个操作模块主程序模块——————>二叉树各个操作模块图 2.本设计当中主程序与子程序之间的主要调用关系注释：(1) Bstree Create()； //创建二叉排序树(2) Bstree Insert(Bstree tree,int key)； //插入(3)Bstree Search(Bstree tree,int key)； //查找(4)void Traverse(Bstree tree)； //遍历(5) Bstree Delete(Bstree tree,int key)； //删除信息（6）void TranslevelPrint(Bstree bt)； //树状打印输出3.1.2 子程序的详细设计如下：（1）Bstree Create 二叉排序树的创建函数，主要用来创建二叉树进而进行操作。

Bstree Create(){int key;Bstree tree=NULL; //初始化空树scanf("%d",&key); while(key!=0) //如果二叉排序树非空{tree=Insert(tree,key); //插入根节点scanf("%d",&key);}Main() Main() Insert() Search( ) Travers () Delte () 5return tree;} //初始化创建二叉排序树（2）Bstree Insert(Bstree tree,int key)二叉排序树的插入函数，主要用来对二叉树插入某个元素的操作Bstree Insert(Bstree tree,int key){Bstree p=tree; //二叉树用 P 表示Bstree s,f;while (p!=NULL) //判断二叉排序树是否为空{f=p; if(key==p->key) return tree; if(keykey) p=p->lchild; else p=p->rchild; //判断是二叉排序树的左孩子还是右孩子}s=(Bstree)malloc(sizeof(Bstnode));s->key=key;s->lchild=NULL;s->rchild=NULL;if(tree==NULL) return s; //新节点为二叉排序树的根if(keykey) f->lchild=s; else f->rchild=s; return tree;} //往二叉树当中插入数据（3）Bstree Search(Bstree tree,int key)二叉排序树的查询函数，主要用来对二叉树当中的元素进行查询。

Bstree Search(Bstree tree,int key){Bstree p=tree;int flag=0;while(p!=NULL){ if(p->key==key) //如果二叉树当中存在所要寻找的结点{ printf("查询到该节点！");6flag=1;return(p);break;}if (keykey) p=p->lchild; //往二叉树左孩子处查找else p=p->rchild; //往二叉树右孩子处查找} if(flag==0){printf("查询不到关键字为%d 的节点！",key);//return NULL; }} //查找二叉树当中某个元素是否存在（4）void Traverse(Bstree tree)二叉排序树的遍历函数，主要用来对二叉排序树的遍历int i=1; //避免递归时多次输出做得标志void Traverse(Bstree tree){if(tree==NULL&&i) //如果树为空不存在{printf("请先创建二叉树，在进行遍历操作!");return;}if(tree){ i=0;Traverse(tree->lchild); //遍历二叉树的左孩子printf("%4d",tree->key);Traverse(tree->rchild); //遍历二叉树的右孩子}} //遍历二叉排序树（5）Bstree Delete(Bstree tree,int key)二叉排序树的删除函数，主要用来对二叉排序树当中某个元素进行删除。

Bstree Delete(Bstree tree,int key)7{Bstree p=tree;Bstree f,s,q;f=NULL;while(p){ //查找关键字为 key 的节点if(p->key==key) break; f=p; if(p->key>key) p=p->lchild;else p=p->rchild;}if (p==NULL) return tree; if ((p->lchild==NULL)||(p->rchild==NULL)) //如果二叉排序树的左右孩子一方为空{ if(f==NULL) if(p->lchild==NULL) tree=p->rchild; //如果左孩子为空，则查找右孩子else tree=p->lchild;else if (p->lchild==NULL) if(f->lchild==p) f->lchild=p->rchild; else f->rchild=p->rchild; else if(f->lchild==p) f->lchild=p->lchild; else f->lchild=p->lchild; free(p);}else {q=p;s=p->lchild; while(s->rchild){q=s;s=s->rchild; }if(q==p) q->lchild=s->lchild;p->key=s->key; free(s);} //查找到所要删除的元素8return tree;}//删除二叉树当中某一个数据（6）void TranslevelPrint(Bstree bt)二叉排序树的打印函数，主要用来对二叉排序树进行树状打印输出。

void TranslevelPrint(Bstree bt){ //本算法实现二叉树的按层打印struct node{Bstree vec[MAXLEN]; //存放树结点int layer[MAXLEN]; //结点所在的层int locate[MAXLEN]; //打印结点的位置int front,rear;}q; //定义队列 qint i, j=1, k=0, nLocate;q.front = 0; q.rear = 0; //初始化队列 q 队头，队尾printf(" ");q.vec[q.rear]=bt; //将二叉树根结点如队列q.layer[q.rear]=1;q.locate[q.rear]=20;q.rear = q.rear+1;while(q.front key);q.front=q.front+1;if(bt->lchild !=NULL) //存放在左子树，将左子树根结点如队列{q.vec[q.rear]=bt->lchild;q.layer[q.rear]=i+1;q.locate[q.rear]=(int)(nLocate - pow(2, NLAYER-i));q.rear = q.rear +1;}if(bt->rchild !=NULL) //存放右子树，将右子树根结点入队列{q.vec[q.rear]=bt->rchild;q.layer[q.rear]=i+1;q.locate[q.rear]=(int)(nLocate+pow(2,NLAYER-i));q.rear=q.rear+1;}}//树状打印输出二叉排序树10第四章4.1 数据结构4.1.1 数据类型定义对二叉。