《构建一棵二叉排序树的C程序的设计方案》由会员分享，可在线阅读，更多相关《构建一棵二叉排序树的C程序的设计方案（28页珍藏版）》请在金锄头文库上搜索。
1、构建一棵二叉排序树的C程序的设计方案与目标一、目的 数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。 二、目标1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。 2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该
2、二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要 解决以下几个问题：1、 如何构造二叉排序树。2、 如何通过中序遍历输出二叉排序树。3、 如何实现多种查找。4、 如何实现插入删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值
3、大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。3.总体设计用二叉链表作为二叉排序树的存储结构，其中key为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示：节点是否为0
4、输入节点值开始N非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0输入i进入主菜单Y总流程图4.具体设计首先定义二叉排序树的数据类型如下：typedef struct nodeint key;/关键字项struct node *lchild,*rchild;/左右孩子指针Bstnode;然后按一定顺序来编写算法程序：4.1递归查找算法具体思想如下：（1）若二叉树为空，则查找失败。（2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的叶
5、子结点时，还没有找到待查结点，则查找不成功。if(t=NULL)return NULL;elseif(t-data=x)return t;if(xdata)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)/二叉排序树
6、不为空 if(p-key=x)/查找成功printf(该结点值存在!);flag=1;break;/查找不成功，到下一层继续查找 if(xkey)p=p-lchild;/查找左子树elsep=p-rchild;/查找右子树if(flag=0)printf(找不到值为%d的结点!,x);p=NULL;return p;p=p-lchild;(p-key=x)下一层？Yp=p-rchild找不到节点YN查找成功二叉排序树非递归查找算法流程图4.3插入算法从根结点开始，根据比较规则，逐一与待插入结点的值比较，查找到插入结点在二叉排序树中的未来位置，然后插入该结点。将一个关键字的值为x的结点s插入到二
7、叉排序树中，方法如下：（1）若二叉排序树为空，则关键字值为x的结点s成为二叉排序树的根。（2）若二叉排序树非空，则将x与二叉排序树的根进行比较，如果x的值等于根结点关键字的值，则停止插入；如果x的值小于根结点关键字的值，则将x插入左子树；如果x的值大于根结点关键字的值，则将x插入右子树。在左右子树中插入方法与整个二叉排序树相同。Bstnode *InsertBST(Bstnode *t,int x)/ 插入关键值为x的元素Bstnode *s,*p,*f;/*s为待插结点，*p为逐层查找结点，*f为待插结点的父结点p=t;while(p!=NULL)f=p;/查找过程中，f指向*p的父结点if
8、(x=p-key)/若二叉树中已有关键值为x的元素，无需插入return t;if(xkey)p=p-lchild;elsep=p-rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL)/原树为空，新结点作为二叉排序树的根return s;if(xkey)f-lchild=s;/新结点作为*f左孩子else f-rchild=s;/新结点作为*f右孩子return t;开始输入节点数n调用插入函数结束插入算法流程图4.4二叉排序树的生成算法建立二叉排序树，就是反复在二叉排
9、序树中插入新的结点。插入的原则是如果待插入结点的值小于根结点的值，则插入到左子树中，否则插入到右子树中。大致方法是：首先建一棵空二叉排序树，然后逐个读入元素，每读入一个元素，就建一个新结点，并调用上述二叉排序树的插入算法，将新结点插入到当前已生成的二叉排序树中，最终生成一棵二叉排序树。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
10、(Bstnode *t)if(t!=NULL)Inorder(t-lchild);Printf(“%4dn”,t-key);Inorder(t-rchild);先遍历左孩子，再遍历父结点，最后遍历右孩子。由于是对一个二叉排序树进行中序遍历，遍历结果则是一个有序序列4.6删除算法1.待删除结点*p无左孩子，也无右孩子，则*p的父结点对应的孩子指针置空；2.待删除结点*p有左孩子，无右孩子，则*p的左孩子替代自己；3.待删除结点*p无左孩子，有右孩子，则*p的右孩子替代自己；4.待删除结点*p有左孩子，也有右孩子，本课程（数据结构与算法）给出了两种法： 方法一： 首先找到待删结点*p的前驱结点*s
11、，然后将*p的左子树改为*p父结点的左子树，而*p的右子树改为*s的右子树： 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);我采用的是第二种算法。开始s-dataT-datap=NULLNYp=ss=InserBST(T-)lchilds=InserBST(T-)rchild结束删除算法流程图4.7主函数void m
12、ain()int i,j,k;Bstnode *tree,*p; system(cls);printf( 请先建立一棵二叉排序树nn);printf(输入其结点信息(输入一组正整数,当输入0时结束):n); tree=CreateBST(); printf(中序遍历的二叉排序树:n);Inorder(tree); printf(二叉排序树的根为:%dn,tree-key); for(;)switch(i=mainmenu()case 0:exit(0);case 1:switch(j=searchmenu() case 1:search_Bitree(tree);break; case 2:p
13、rintf(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(二叉排序树的根为:%dn,tree-key); printf(中序遍历后的序列为:n); print_Bitree(tree); printf(中序遍历的二叉排序树:n); Inorder(tree); printf(n); break; /default:print
