建立二叉排序树_c语言建立二叉排序树_平衡二叉排序树的构建

B. 写出规范的课程设计报告书；时间安排：6月27日---7月1 日第一天 布置题目，确定任务、查找相关资料 第二天～第四天 功能分析，编写程序，调试程序、运行系统；② 总体方案与说明③ 软件主要模块的流程图④ 源程序清单与注释⑤ 问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）；⑥ 小结与体会附录：① 源程序（必须有简单注释） ② 使用说明 ③ 参考资料2．每位学生应独立完成各自的任务且每天至少在设计室工作半天；指 导 教 师 签 名： 2016 年 6月 25日教研室主任（或责任教师）签名：邱珊 2016年 6月 25日目 录1实验目的与目标 32.问题分析 33.总体设计 44.具体设计 54.1递归查找算法 54.2非递归查找算法 64.3插入算法 74.4二叉排序树的生成算法 84.5中序遍历算法 94.6删除算法 94.7主函数 104.8注意事项： 115.运行环境 116.上机调试 116.1语法错误及修改 116.2程序输出调整： 136.3时间和空间性能分析： 137.测试结果及分析 148.用户使用说明 209.参考文献 20附录 211实验目的与目标一、目的数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。

通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。NY总流程图4.具体设计首先定义二叉排序树的数据类型如下：typedef struct node{int key;//关键字项struct node *lchild,*rchild;//左右孩子指针}Bstnode;然后按一定顺序来编写算法程序：4.1递归查找算法具体思想如下：（1）若二叉树为空，则查找失败。（2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。if(t==NULL)return NULL;else{if(t->data==x)return t;if(x<t->data)return(Bsearch(t->lchild,x));elsereturn(Bsearch(t->rchild,x));}二叉排序树归查找算法流程图4.2非递归查找算法查找过程是从根结点开始逐层向下进行的。

并定义一个标记量记录是否找到结点。Bstnode *searchBST(Bstnode *t,int x){Bstnode *p;int flag=0;p=t;//定义*p结点用于逐层查找，丛根结点开始查找while(p!=NULL)//二叉排序树不为空{if(p->key==x)//查找成功{printf("该结点值存在!");flag=1;break;}//查找不成功，到下一层继续查找if(x<p->key)p=p->lchild;//查找左子树elsep=p->rchild;//查找右子树}if(flag==0){printf("找不到值为%d的结点!",x);p=NULL;}return p;}YY N二叉排序树非递归查找算法流程图4.3插入算法从根结点开始，根据比较规则，逐一与待插入结点的值比较，查找到插入结点在二叉排序树中的未来位置，然后插入该结点。{Bstnode *s,*p,*f;//*s为待插结点，*p为逐层查找结点，*f为待插结点的父结点p=t;while(p!=NULL){f=p;//查找过程中，f指向*p的父结点if(x==p->key)//若二叉树中已有关键值为x的元素，无需插入return t;if(x<p->key){p=p->lchild;}else{p=p->rchild;}}s=(Bstnode *)malloc(sizeof(Bstnode));s->key=x;s->lchild=NULL;s->rchild=NULL;if(t==NULL)//原树为空，新结点作为二叉排序树的根return s;if(x<f->key)f->lchild=s;//新结点作为*f左孩子elsef->rchild=s;//新结点作为*f右孩子return t;}插入算法流程图4.4二叉排序树的生成算法建立二叉排序树，就是反复在二叉排序树中插入新的结点。

插入的原则是如果待插入结点的值小于根结点的值，则插入到左子树中，否则插入到右子树中。Bstnode *CreateBST(){Bstnode *t;int key;t=NULL;//设置二叉排序树的初态为空scanf("%d",&key);while(key!=endflag){t=InsertBST(t,key);scanf("%d",&key);}return t;}4.5中序遍历算法void Inorder(Bstnode *t){if(t!=NULL){Inorder(t->lchild);Printf(“%4d\n”,t->key);Inorder(t->rchild);}}先遍历左孩子，再遍历父结点，最后遍历右孩子。由于是对一个二叉排序树进行中序遍历，遍历结果则是一个有序序列待删除结点无左孩子，也无右孩子，则父结点对应的孩子指针置空；待删除结点有左孩子，无右孩子，则的左孩子替代自己；待删除结点无左孩子，有右孩子，则的右孩子替代自己；待删除结点有左孩子，也有右孩子， f-> lchild=p->lchild;s->rchild=p->rchild;free(p);方法二：首先找到待删结点*p的前驱结点*s，然后用结点*s的值替代结点*p的值，再将结点*s删除，结点*s的原左子树改为*s的双亲结点*q的右子树：p->data=s->data;q->rchild=s->lchild;free(s);我采用的是第二种算法。

NY删除算法流程图4.7主函数void main(){int i,j,k;Bstnode *tree,*p;system("cls");printf(" ★☆★☆★请先建立一棵二叉排序树★☆★☆★\n\n");printf("输入其结点信息(输入一组正整数,当输入0时结束):\n");tree=CreateBST();printf("中序遍历的二叉排序树:\n");Inorder(tree);printf("二叉排序树的根为:%d\n",tree->key);for(;;)switch(i=mainmenu()){case 0:exit(0);case 1:switch(j=searchmenu()){case 1:search_Bitree(tree);break;case 2:printf("\n请输入要查找的结点的值:");scanf("%d",&k);p=searchBST(tree,k);printf("\n");break;//default:printf("输入有误!");}break;case 2:tree=insert_Bitree(tree);break;case 3:tree=delete_Bitree(tree);break;case 4:printf("\n");printf("二叉排序树的根为:%d\n",tree->key);printf("中序遍历后的序列为:\n");print_Bitree(tree);printf("中序遍历的二叉排序树:\n");Inorder(tree);printf("\n");break;//default:printf("输入有误!");}}4.8注意事项：其中，某些函数顺序一定不能颠倒。

例如建立二叉排序树函数一定是在插入算法之后。编写完基本操作算法后，为最后主函数的输出模块作准备，又分别写了递归查找模块、插入模块、删除模块、显示模块。5.运行环境Microsoft Visual C++ 6.0；Microsoft Word 20106.上机调试6.1语法错误及修改在编写程序时，很容易出现分号漏写和括号不匹配的现象，以及缺少返回值的问题。例如：在编写非递归查找算法时：Bstnode * searchBST (Bstnode *t,int x){Bstnode *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;elsep=p->rchild;}if(flag==0){printf("找不到值为%d的结点",x);return NULL;}}结果编译时出现了警告warning : ' searchBST ' : not all control paths return a value然后我做了改动，改后程序如下：Bstnode *searchBST(Bstnode *t,int x){Bstnode *p;int flag=0;p=t;while(p!=NULL){if(p->key==x){ printf("该结点值存在!");flag=1;break;}if(x<p->key)p=p->lchild;elsep=p->rchild;}if(flag==0){ printf("找不到值为%d的结点!",x);p=NULL;}return p;}将NULL值赋给指针p，再在程序结尾返回p，此时，编译结果就正确了！6.2程序输出调整：在递归查找算法(Bsearch)中针对查找结果如何,没有用明确的输出函数表示出来。

于是我添加了一个递归查找模块如下：search_Bitree(Bstnode *t){int s;Bstnode *p;printf("\n请输入要查找的结点的值:");scanf("%d",&s);if(s!=0){ p=Bsearch(t,s);if(p==NULL)printf("该结点值不存在!\n");elseprintf("找不到值为%d的结点!\n",s);}}这样主函数便可直接调用该函数来实现查找过程。6.3时间和空间性能分析：由于二叉排序树的中序遍历序列为一个递增的有序序列，这样可以将二叉排序树看作是一个有序表。其查找过程：若查找成功，则是从根结点出发走了一条从根到某个结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子结点的路径。和关键字比较次数不超过二叉排序树的深度。二叉排序树的平均查找长度与其形态有关。最坏情况是具有n个结点的单支树，其平均查找长度与顺序查找相同，为（n+1）/2；即平均查找长度的数量级为O（n）。在最好情况下，二叉排序树形态均匀，它的平均查找长度与二分查找相似，大约是log2n，其平均查找长度的数量级为O（log2n）。

经验与体会：由于该设计问题是对数据结构与算法课程中二叉树章节的灵活应用，所以课本给了我很大的帮助，结合所学知识以及对二叉排序树的理解，来编写该程序。7.测试结果及分析建立如图（a）的二叉排序树，输入的数据依次为：45 24 53 12 28 90 0（0为输入结束符），屏幕（图（1））上显示的是横置的二叉树图（a） 图（b）图（1）2、选择方框中给定的项目（输入0~4中任意数）。若输入错误会有提示，可以重新输入。图（2）输入1，则出现查找菜单。选择查找方法。图（3）4、在查找菜单选1，则进行递归查找。建立二叉排序树图（4）5、同理，若选择2，则进行非递归查找。查找的值存在与否都会有显示。图（5）6、选2，则进行插入操作。插入关键值为13的结点后，显示如图（6），即插入13后的横置的二叉排序树（图（c）——图（d））。图（c） 图（d）图（6）选3，进行删除操作。删除关键值为24的结点后，显示如图（7），即删除24后的横置的二叉排序树（图（e）——图（f））、图（e） 图（f）图（7）选4则显示详细信息。如图（8）所示，按中序遍历（从小到大）依次输出，并显示每个结点的孩子情况，最后打印出横置的二叉排序树。

图（8）选0则退出程序。图（9）8.用户使用说明用户可以根据本程序运行过程中出现的提示性语句来进行操作。要注意括号中的提示，若没有按照提示输入的话，程序可能将无法继续进行下去。例如开始输入数据时直到输入0时才算结束输入，从而进行下一步操作。在遇到选项时，选择错误会给你重新选择的机会。提示：进行一系列插入删除等操作后，可以选择显示项来显示最后的二叉排序树状态 (二叉排序树显示的是中序遍历后的序列) 。9.参考文献(1)王昆仑.李红.数据结构与算法.北京：中国铁道出版社，2007.6(2)王昆仑.李红.数据结构与算法试验指导，2009(3)谭浩强.c程序设计.北京：清华大学出版社，2005.7(4)严蔚敏.数据结构：ｃ语言版.北京：清华大学出版社，2002(5)耿国华.等.数据结构:用c语言描述.北京：高等教育出版社，2004设计过程中质疑（或答辩）记载：二叉树运行过程中用了什么排序？答：运用了中序遍历排序。2．中序遍历排序是怎样的？答：先遍历左孩子，再遍历父结点，最后遍历右孩子。3.在设计过程中遇到过那些困难？答:在编程序的过程的程序一直不能正确运行，最后发现函数的调用出现了问题。最后通过修改解决。建立二叉排序树

指导教师评语：签名：2016年 7 月5 日附录#include "stdio.h"#include "malloc.h"#include "stdlib.h"#define endflag 0//定义endflag为关键字输入结束的标志//二叉排序树的结点结构typedef struct node{int key;//关键字项struct node *lchild,*rchild;//左右孩子指针}Bstnode;//二叉排序树的查找算法之一（递归）Bstnode *Bsearch(Bstnode *t,int x){if(t==NULL)//二叉排序树为空，查找失败return NULL;else{if(t->key==x)//查找成功，返回当前结点return t;if(x<t->key)return(Bsearch(t->lchild,x));//进入左子树递归查找elsereturn(Bsearch(t->rchild,x));//进入右子树递归查找}}//递归查找函数（显示查找结果）void search_Bitree(Bstnode *t){int s;//定义待查结点的关键值Bstnode *p;//定义待查的结点printf("\n请输入要查找的结点的值:");scanf("%d",&s);if(s!=0){p=Bsearch(t,s);//递归查找if(p!=NULL)printf("该结点值存在!\n");elseprintf("找不到值为%d的结点!\n",s);}}//二叉排序树的查找算法之二（非递归）Bstnode * searchBST(Bstnode *t,int x){Bstnode *p;int flag=0;p=t;//定义*p结点用于逐层查找，丛根结点开始查找while(p!=NULL)//二叉排序树不为空{if(p->key==x)//查找成功{printf("该结点值存在!");flag=1;break;}//查找不成功，到下一层继续查找if(x<p->key)p=p->lchild;//查找左子树elsep=p->rchild;//查找右子树}if(flag==0){printf("找不到值为%d的结点!",x);p=NULL;}return p;}//二叉排序树的结点插入算法Bstnode *InsertBST(Bstnode *t,int x)// 插入关键值为x的元素{Bstnode *s,*p,*f;//*s为待插结点，*p为逐层查找结点，*f为待插结点的父结点p=t;while(p!=NULL){f=p;//查找过程中，f指向*p的父结点if(x==p->key)//若二叉树中已有关键值为x的元素，无需插入return t;if(x<p->key){p=p->lchild;}else{p=p->rchild;}}s=(Bstnode *)malloc(sizeof(Bstnode));s->key=x;s->lchild=NULL;s->rchild=NULL;if(t==NULL)//原树为空，新结点作为二叉排序树的根return s;if(x<f->key)f->lchild=s;//新结点作为*f左孩子elsef->rchild=s;//新结点作为*f右孩子return t;}//中序遍历（递归法）void Inorder(Bstnode *t){if(t!=NULL)//若二叉树不空{Inorder(t->lchild);//遍历左孩子printf("%4d",t->key);Inorder(t->rchild);//遍历右孩子}}//二叉排序树的结点删除算法Bstnode *DeleteBST(Bstnode *t,int k)//删除关键值为k的元素{Bstnode *p,*f,*s,*q;//*p为待删结点，*f为*p父结点，*s为*p的中序前驱结点，*q为*s的父结点p=t;f=NULL;//从根结点开始查找，并将*f置空//查找关键值为k的待删结点*pwhile(p!=NULL){if(p->key==k) break;//若找到，则退出循环f=p;//未找到时将*f替代*p，*p则下移进入左右子树继续查找if(p->key>k)p=p->lchild;elsep=p->rchild;}if(p==NULL) return t;//若找不到，则返回原二叉排序树的根指针//查找成功后，对*p的删除过程if(p->lchild==NULL||p->rchild==NULL)//若*p无左子树或无右子树{if(f==NULL)//若*p是原二叉排序树的根{if(p->lchild==NULL) t=p->rchild;//无左孩子，右孩子做根else t=p->lchild;}//无右孩子，左孩子做根else if(p->lchild==NULL)//若*p无左子树{if(f->lchild==p) f->lchild=p->rchild;//p是*f的左孩子else f->rchild=p->lchild;//p是*f的右孩子}else //若*p无右子树{if(f->lchild==p) f->lchild=p->lchild;//p是*f的左孩子else f->rchild=p->lchild;//p是*f的右孩子}free(p);}else//若*p有左右子树{q=p;s=p->lchild;while(s->rchild)//在*p的左子树中查找最右下结点(即其中序前驱结点){q=s;s=s->rchild;}if(q==p) q->lchild=s->lchild;else q->rchild=s->lchild;p->key=s->key;//将*s的值赋给*pfree(s);}return t;}//插入函数（显示插入结果）Bstnode *insert_Bitree(Bstnode *t){int s;//定义待插结点的关键值Bstnode *p;//定义待插的结点printf("\n");printf("请输入要插入的结点的值:");scanf("%d",&s);if(s!=0){p=Bsearch(t,s);if(p==NULL){t=InsertBST(t,s);printf("插入结点中序遍历后的二叉排序树:\n");Inorder(t);printf("\n二叉排序树的根为:%d\n",t->key);}else printf("该结点值存在,不插入!\n");}return t;}//删除函数（显示删除结果）Bstnode *delete_Bitree(Bstnode *t){int s;//定义待删结点的关键值Bstnode *p;//定义待删的结点printf("\n请输入要删除的结点的值:");scanf("%d",&s);if(s!=0){p=Bsearch(t,s);if(p==NULL)printf("找不到值为%d的结点!",s);else{t=DeleteBST(t,s);printf("删除结点后中序遍历的二叉排序树:\n");Inorder(t);printf("\n二叉排序树的根为:%d\n",t->key);}}return t;}//设置二叉排序树的初值Bstnode *CreateBST(){Bstnode *t;int s;t=NULL;//设置二叉排序树的初态为空scanf("%d",&s);while(s!=endflag)//输到结束符为止{t=InsertBST(t,s);scanf("%d",&s);}return t;}//显示函数void print_Bitree(Bstnode *t){if(t!=NULL)//中序遍历二叉排序树,并显示遍历结果{print_Bitree(t->lchild);printf("遍历结点%d",t->key);if(t->lchild!=NULL)printf("(该结点的左孩子为%d",t->lchild->key);elseprintf("(该结点的左孩子为空");if(t->rchild!=NULL)printf(" 该结点的右孩子为%d)",t->rchild->key);elseprintf(" 该结点的右孩子为空)");printf("\n\n");print_Bitree(t->rchild);}}//主菜单int mainmenu(){int choice;int flag=1;//标记量printf("\n\n\n");printf("\t\t\t┏***对二叉排序树进行操作***┓\n");printf("\t\t\t┇┏┅┅┅┅┅┅┅┅┅┅┅┓┇\n");printf("\t\t\t┇┃ ┃┇\n");printf("\t\t\t┇┃1.二叉排序树------查找┃┇\n");printf("\t\t\t┇┃2.二叉排序树------插入┃┇\n");printf("\t\t\t┇┃3.二叉排序树------删除┃┇\n");printf("\t\t\t┇┃4.二叉排序树------显示┃┇\n");printf("\t\t\t┇┃0.退出该程序┃┇\n");printf("\t\t\t┇┃ ┃┇\n");printf("\t\t\t┇┗┅┅┅┅┅┅┅┅┅┅┅┛┇\n");printf("\t\t\t┗**************************┛\n");printf("\n\n\n");do{if(flag==0)printf("!您的输入有误,请重新输入\n");printf("请选择您要进行的项目:");scanf("%d",&choice);flag=0;}while(choice<0||choice>4);return choice;}//查找方法菜单int searchmenu(){int choice;int flag=1;//标记量printf("\n\n\n");printf("\t\t\t┏*****二叉树的查找方法*****┓\n");printf("\t\t\t┋┏┅┅┅┅┅┅┅┅┅┅┅┓┇\n");printf("\t\t\t┇┃ ┃┇\n");printf("\t\t\t┇┃1.方法1-------递归查找┃┇\n");printf("\t\t\t┇┃2.方法2-----非递归查找┃┇\n");printf("\t\t\t┇┃ ┃┇\n");printf("\t\t\t┇┗┅┅┅┅┅┅┅┅┅┅┅┛┇\n");printf("\t\t\t┗**************************┛\n");printf("\n\n\n");do{if(flag==0)printf("!您的输入有误,请重新输入\n");printf("请选择查找方法:");scanf("%d",&choice);flag=0;}while(choice!=1&&choice!=2);return choice;}//主函数void main(){int i,j,k;Bstnode *tree,*p;system("cls");printf(" ★☆★☆★请先建立一棵二叉排序树★☆★☆★\n\n");printf("输入其结点信息(输入一组正整数,当输入0时结束):\n");tree=CreateBST();printf("中序遍历的二叉排序树:\n");Inorder(tree);printf("二叉排序树的根为:%d\n",tree->key);for(;;)switch(i=mainmenu()){case 0:exit(0);case 1:switch(j=searchmenu()){case 1:search_Bitree(tree);break;case 2:printf("\n请输入要查找的结点的值:");scanf("%d",&k);p=searchBST(tree,k);printf("\n");break;//default:printf("输入有误!");}break;case 2:tree=insert_Bitree(tree);break;case 3:tree=delete_Bitree(tree);break;case 4:printf("\n");printf("二叉排序树的根为:%d\n",tree->key);printf("中序遍历后的序列为:\n");print_Bitree(tree);printf("中序遍历的二叉排序树:\n");Inorder(tree);printf("\n");break;//default:printf("输入有误!");}}8节点是否为0输入节点值开始非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0输入i进入主菜单p=p->lchild;(p->key==x)下一层？p=p->rchild找不到节点查找成功开始输入节点数n调用插入函数结束开始s-〉data〉T-〉datap=NULLp=ss=InserBST(T->)lchilds=InserBST(T->)rchild结束4524531228904524531228904524531228901345245312289013451353122890451353122890

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26294-1.html