资源描述：
《数据结构c语言课设-二叉树排序》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、题目:二叉排序树的实现1内容和要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?2解决方案和关键代码2.1解决方案：先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。前中后根遍历需要用到栈的数据结构，分模块编写栈与遍历代码。要求对比二叉排序树和数组的查找效率，首先建立一个数组
2、存储一个班的成员信息，分别用二叉树和数组查找，利用clock（）函数记录查找时间来对比查找效率。2.2关键代码2.2.1树的基本结构定义及基本函数typedefstruct{KeyTypekey;}ElemType;typedefstructBiTNode//定义链表{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree,*SElemType;//销毁树intDestroyBiTree(BiTree&T){if(T!=NULL)free(T);return0;}//清空树intClearBiTree(BiTree&T){if(T!
3、=NULL){T->lchild=NULL;T->rchild=NULL;T=NULL;}return0;}//查找关键字,指针p返回intSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){if(!T){p=f;returnFALSE;}elseifEQ(key,T->data.key){p=T;returnTRUE;}elseifLT(key,T->data.key)returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}2.2.2二叉树的生成、插入，删除
4、生成voidCreateBST(BiTree&BT,BiTreep){inti;ElemTypek;printf("请输入元素值以创建排序二叉树:");scanf_s("%d",&k.key);for(i=0;k.key!=NULL;i++){//判断是否重复if(!SearchBST(BT,k.key,NULL,p)){InsertBST(BT,k);scanf_s("%d",&k.key);}else{printf("输入数据重复！");return;}}}插入intInsertBST(BiTree&T,ElemTypee){BiTrees,p;if(!SearchBST(T,e.
5、key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseifLT(e.key,p->data.key)p->lchild=s;elsep->rchild=s;returnTRUE;}elsereturnFALSE;}删除//某个节点元素的删除intDeleteEle(BiTree&p){BiTreeq,s;if(!p->rchild)//右子树为空{q=p;p=p->lchild;free(q);}elseif(!p->lchild)//左子树为空{q=p;p
6、=p->rchild;free(q);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;deletes;}returnTRUE;}//整棵树的删除intDeleteBST(BiTree&T,KeyTypekey)//实现二叉排序树的删除操作{if(!T){returnFALSE;}else{if(EQ(key,T->data.key))//是否相等returnDeleteEle(T);elseif(
7、LT(key,T->data.key))//是否小于returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}return0;}2.2.3二叉树的前中后根遍历栈的定义typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;intInitStack(S
