二叉排序树的实现(最终版)

课程名称数据结构课程设计 题目名称二叉树的实现 学生学院应用数学学院 学号 学生姓名阮志敏 指导教师刘志煌 二叉排序树的实现1)编程实现二叉排序树，包括生成、插入、删除；2)对二叉排序树进行先根、中根和后根非递归遍历；3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项)，对比查找效率，并说明在什么情况下二叉排序树效率高，为什么？5)格式按照作业的要求，对数据测试，分析，总结和改进的工作要做详细一点。二、解决方案和关键代码1)首先定义二叉树的结构体，代码如下：TreeNodetypedefstructTreeNode*TreePosition;typedefstructTreeNode*SearchTree;typedefstructTreeNode*Tree;typedefintTreeElementType;structTreeNode{//二叉树TreeElementTypeelement;//节点中的元素SearchTreeleft;//左儿子SearchTreeright;//右儿子intleght;//节点的深度，用于打印intposition;//节点的位置，用于打印2)实现插入和生成二叉树节点的方法。在这里用到了递归插入的方法。chTreeinsertTreeNodeTreeElementTypexSearchTreetreeif(tree==NULL){tree=makeTree(x,NULL,NULL);//插入在该处}elseif(x<tree->element){tree->left=insertTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=insertTreeNode(x,tree->right);}//如果相等，什么也不做ree}当tree==NULL时，就是递归终止的条件，也是插入该节点的地方，在这里，用makeTree()其代码如下：emakeTreeTreeElementTypexSearchTreeleftSearchTreerightSearchTreenode=(SearchTree)malloc(sizeof(structTreeNode));if(node==NULL){printf("makeTreeNodefail!\n");}else{node->element=x;node->left=left;node->right=right;}returnnode;}3)实现二叉树节点删除的方法。情况一：被删除的节点同时含有左儿子和右儿子。在这种情况下，必须找出一个合适的节点来替代被删除的节点。由于二叉树的特性，被删除节点右子树中的节点都比左子树节点大，因此，可以替代原节点的节点必然在被删除节点的右子树中，并且是右子树的最小节点。所以，在这种情况下，应该把被删除节点的右子树中最小节点替代被删除节点。情况二：被删除节点只有一个子节点。显然，应该把它的子节点替代它。情况三：被删除节点没有子节点。此时，直接删除它。archTreedeleteTreeNodeTreeElementTypexSearchTreetreeTreePositiontmpNode;if(tree==NULL){//到叶节点了，还没找到可以删除的printf("notfound!\n");}elseif(x<tree->element){tree->left=deleteTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=deleteTreeNode(x,tree->right);}elseif(x==tree->element){if(tree->left&&tree->right){tmpNode=findMin(tree->right);//找出右子树中最小的tree->element=tmpNode->element;//把右子树中最小的值给当前树>节点//把tree右子树中最小值的节点删除了,那个要删除的节点不可能有左>儿子tree->right=deleteTreeNode(tree->element,tree->right);}else{//只有一个子节点，或者没有子节点tmpNode=tree;if(tree->left==NULL){//0个子节点也包含在内tree=tree->right;}elseif(tree->right==NULL){tree=tree->left;}free(tmpNode);}}ree}其中的findMin()方法为找出以某个节点为根的树的最小节点，在这里可以用循环遍历tree->left来实现，也可以用递归来实现，代码如下：TreePositionfindMin(SearchTreetree){//递归实现if(tree==NULL){returnNULL;}if(tree->left!=NULL){returnfindMin(tree->left);}else{ntree}}2.对二叉排序树进行先根、中根和后根非递归遍历1)先根遍历先根遍历先访问根，再访问左儿子，接着访问右儿子。上图中的树，如果用先根遍历，顺序则是A-B-E-F-C要实现非递归遍历，必须使用循环来进行遍历。这就需要使每次循环时，都有一致的操作。为了一致性，先定义每次循环中的一致性操作：每次循环只处理一个节点，也就是打印当前节点，其左节点要等到下次循环再打印，这时，如果当前节点有左右节点，则需要储存当前节点的左节点和右节点，以便下次循环时取出打印，如果没有左右节点，则直接进入下次循环。在这里，有两种数据结构可用于储存待打印节点，一个是队列，一个是栈。先尝试队列，队列的特性是先进先出，我们希望在访问完当前节点后，储存当前节点的左节点和右节点，以便下次循环进取出进行打印，因此，节点储存的顺序必须为先储存左节点，再储存右节点。以上图的树为例：当用队列时，会先访问A节点，然后储存B到队列，再储存C到队列，此时，队列中的元素为BC。下次循环时，会把B出列，访问完B后，再储存E和F，此时，队列中的元素为CEF。下次循环时，会把C出列进行访问。显然，这种访问顺序A-B-C不是正确的访问顺序，正确的应该是A-B-E，因此队列并不能满足接下来用栈进行储存尝试。当使用栈时，由于栈的特性为后进先出，故在第一次循环BCBB栈进行访问，然后把F入栈，再把E入栈。这时，访问顺序为A-B-E-F-C，因此，我们可以用栈来作为循环遍历时的储存数据结构。此时，每轮循环的步骤就很清晰了：如果栈非空，出栈一个元素作为当前节点，先访问或者打印当前节点，接着，如果当前节点有左儿子或者右儿子，则先把右儿子入栈，再把左儿子入栈然后进入下次循环。如果当前节点没有儿子，则直接进入下次循环。具体代码如下：voidpreorderTraversalTreetree){Stackstack=createStack(10);push(tree,stack);while(!isStackEmpty(stack)){TreePositionnode=pop(stack);printf("%d",node->element);if(node->right!=NULL){push(node->right,stack);}if(node->left!=NULL){push(node->left,stack);}}}子。上图的树中，中根遍历的顺序为D-B-F-E-A-C。在中根遍历过程中，要访问当前节点，首先要访问当前节点的左节点，而如果左节点又有左节点，则会一直向左下去。比如要访及其左边的节点全部压入栈中，此时，栈中的元素为ABD，然后开始循环遍历。在循环中，先从栈中弹出一个节点，访问该节点，然后判断该节点是否有右节点，如果有右节点，则把其右子树中右节点开始的所有左节点压入栈中，这样，下一次循环就能访问到右节点所在子树的最左边节点了。因为要访问右节点，必须先访问右节点的左子树中的最左B的时候，访问B，然后B有右节点E，因此，把EF都入栈，然后开始下一次循环。下一次循环开始时，就能取出F进行访问了。具体代码如/**中序遍历voidinorderTraversal(Treetree){Stackstack=createStack(30);if(tree==NULL){printf("thetreeisNULL,can'ttraversal\n");}else{pushLeftToStack(tree,stack);while(!isStackEmpty(stack)){TreePositionnode=pop(stack);printf("%d",node->element);if(node->right){pushLeftToStack(node->right,stack);}}printf\n");}}其中的pushLeftToStack()方法从该节点开始，一直向左，把左节点全部压入栈中，代码staticvoidpushLeftToStack(Treetree,Stackstack){while(tree){push(tree,stack);tree=tree->left;}}3)后根非递归遍历后根遍历中，先访问当前节点的左儿子，再访问右儿子，最后才访问当前节点。在上图的树中，访问的顺序为D-F-E-B-C-A。要实现非递归遍历，必须明确每一次循环中要进行的操作。和中根遍历相似，在循环开始前应该先把根节点开始，一直向左的节点压入栈中。然后再开始循环，循环开始时先出栈一个节点，如果该节点没有右儿子，那么就可以直接访问该节点了，但如果该节点有右儿子，那么就还不能访问该节点，必须先访问完该节点的右子树。如上图中，先弹出D，由于D没有右儿子，则可以直接访问，进入下一次循环。但弹出B时，由于B有右儿子E，那么此时还不能访问B，因此要将B重新压回栈中，然后再把EF入栈。这里的问题在于，当访问完FE后，又回把B重新出栈。如果按照刚才的做B，B又会重新压入栈，同时EF也会再次入栈，这样就会造成无限循环。一种解决这种无限循环的方式是：访问完D后，出栈B，由于B有右儿子，为了避免后面的无限循环，可以在把B重新入栈时，先用临时变量T保存B的右儿子，然BB入栈，接着再把临时变量T作为原B的右儿子入栈，这样，再次弹出B时，由于B的儿子为空了，所以这次会直接访问B，从而避免了无限循环。但是这样破坏了树的结构，显然是不好的。因此要寻找另外的办法来避免无限循环，现在的重点是标识出B已经被重新压入过一次栈了，也就是说B被压了两次栈了。如果可B了。在这里采取的做法是：创建多一个栈，设其为T，第一次弹出B时，由于B有右儿子。则把B压回到原本的栈中，同时也把B压入栈T中。这样，每次弹出一个节点时，如果这个节点有右儿子则先和栈T中的最顶元素做下对比，如果和栈T中的最顶元素相同，则证明这个有右儿子的节点在之前已经被压入多一次栈了。因此，可以直接访问这个节点了。在上面例子中，访问完FE后，再次把B出栈，此时B有右儿子，故和栈T中的最顶元素做比较，发现栈T中的最顶元素也是B，因此证明B已经被压入过两次了，故可以直/**后序遍历voidpostorderTraversalTreetree{Stackstack=createStack(30);Stacktmp=createStack(30);//保存入栈两次的，有右子树的节点pushLeftToStacktreestackwhile(!isStackEmpty(stack)){TreePositionnode=pop(stack);if(node->right==NULL){//如果右儿子为空，则直接输出printf("%d",node->element);}else{if(isStackEmpty(tmp)||node!=top(tmp)){push(node,stack);//再次把有右儿子的节点入栈push(node,tmp);//同时也把该节点压入临时栈中pushLeftToStack(node->right,stack);}else{//如果该节点两次入栈了，就把它访问并输出poptmp;printf("%d",node->element);}}}printfn");disposeStack(stack);disposeStack(tmp);}3.打印树为了在终端中打印一棵树，则需要确定在打印一个节点时，前面需要打印多少个空格。在这里，我们可以为每个节点设置一个位置。位置的设置方式如下图：这棵树高为3,故根节点的位置为=8，这个8代表在打印根节点时，需要在其前面打印8-1=7个空格。确定好根节点的位置后，就可以确定其子节点的位置了。从最高的层开始，设置第1层所有节点的深度为0,第2层所有节点的深度为1,依此类推。设某个节点pp-R/2^l。如上面的根节点的左儿子的位置为8-2^1=4。同理，根的右儿子的位置为8+2^1=12。第3层中的第一个节点的位置为4-8/2^2=4-2=2。这样，只要知道根节点的位置，可以知道整棵树的位置了。而根节点的位置R=2^h,其中h为树的高度。先是获取树中每个节点的深度和整棵树的高度的代码，在这里，用层序遍历树来进行staticinttreeHeight=-1;voidgetLegthOfTreeTreetreeQueueparentQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);//保存父节点的队列QueuechildQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);//保存子节点的队列intleght=0;//当前的深度treeHeight=-1;Enqueue(tree,parentQueue);while(!IsQueueEmpty(parentQueue)){while(!IsQueueEmpty(parentQueue)){TreePositionnode=FrontAndDequeue(parentQueue);//出列node->leght=leght;if(node->left!=NULL)Enqueue(node->left,childQueue);//把子节点入子队列中if(node->right!=NULL)Enqueue(node->right,childQueue);}//交换父子队列QueuetempQueue=parentQueue;parentQueue=childQueue;childQueue=tempQueue;leght++;//每遍历一层，深度加一treeHeight++;//树高度加一}DisposeQueue(parentQueue);DisposeQueue(childQueue);}接下来是获取树中每个节点的位置的代码，这里同样使用层序遍历来获取每个节点的staticvoidgetPositionOfTreeTreetree{QueueparentQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);QueuechildQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);Enqueue(tree,parentQueue);tree->position=1<<treeHeight;inttopPosition=tree->position;while(!IsQueueEmpty(parentQueue)){while(!IsQueueEmpty(parentQueue)){TreePositionnode=FrontAndDequeue(parentQueue);if(node->left!=NULL){intleftStep=topPosition>>node->left->leght;node->left->position=node->position-leftStep;Enqueue(node->left,childQueue);}if(node->right!=NULL){intrightStep=topPosition>>node->right->leght;node->right->position=node->position+rightStep;Enqueue(node->right,childQueue);}}QueuetempQueue=parentQueue;parentQueue=childQueue;childQueue=tempQueue;}DisposeQueue(parentQueue);DisposeQueue(childQueue);}voidprintTree(Treetree){getLegthOfTreetreegetPositionOfTreetree);printfn");QueueparentQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);QueuechildQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);intprePosition=0;Enqueue(tree,parentQueue);while(!IsQueueEmpty(parentQueue)){while(!IsQueueEmpty(parentQueue)){TreePositionnode=FrontAndDequeue(parentQueue);intspaceNum=node->position-prePosition-1;printSpace(spaceNum);printf("%2d",node->element);prePosition=node->position;if(node->left!=NULL)Enqueue(node->left,childQueue);if(node->right!=NULL)Enqueue(node->right,childQueue);}prePosition=0;printf\n");QueuetempQueue=parentQueue;parentQueue=childQueue;childQueue=tempQueue;}DisposeQueue(parentQueue);DisposeQueue(childQueue);}4.对比存储50个学生信息的二叉树和数组的查找效率。二叉树和数组的查找效率是看情况而言的，二叉树的查找效率显然受到插入方式的影先设50名学生的学号为0至49,二叉树中以学生学号为比较依据。学生结构体如下代structStu;typedefstructStu{dechar*name;}*Student;typedefStudentTreeElementType;情况一：每个学生插入二叉树时，学号是随机的，这样，生成的二叉树比较理想。数组中储存的学生和插入二叉树中的学生的顺序一样。查找学生时，数组的查找方法是一个如在二叉树中依次插入学号为18、24、28、26、44的学生，那么数组中的第一到第在这种情况下，显然是二叉树的效率高，因为二叉树中查找需要时间是O(logn)的，而查找时间是O(n^2)的。下面编写代码测试这种情况。先编写生成随机学号数组的代码，为了生成随机的数组，可以先声明一个50元素的数组，每个元素的初始值依次为0到49,然后遍历数组，根据随机产生的位置来交换数组中的voidgenRandArray(inta[50]){for(inti=0;i<50;i++)a[i]=i;printf("正在生成随机数组...\n");sleep(1);srand((unsignedint)(time(NULL)));for(inti=49;i>=1;i--){intindex=rand()%i;s[i],&a[index]);//随机交换位置}}然后用随机的学号数组来生成学生数组，然后根据学生数组中学号的顺序来生成二叉代码：voidgenStudentArray(Studentstudents[50],inta[50]){//a为学号随机数组char*nameArray[4]={"Tom","Jenny","Alice","Bob"};for(inti=0;i<50;i++){char*name=malloc(6);strcpy(name,nameArray[rand()%4]);students[i]=createStudent(a[i],90+(rand()%10),name);}}其中，学生的成绩均为90到99分，名字为"Tom","Jenny","Alice","Bob"中的一个，学下面是根据学生数组生成二叉树的方法代码，该方法返回一棵和数组一致的树：TreemakeStudentTree(Studentstudents[50]){Treetree=NULL;for(inti=0;i<50;i++){tree=insertTreeNode(students[i],tree);}tree}查找的方法是进行N次的随机查找，统计两种结构的查找时间。每次查找的过程如下，先用随机函数生成五个随机的学号，然后用分别用这个学号执行N次查找，然后计算每个学号查找的平均值。其中查找数组中元素的代码如下，采取的是遍历数组来查找StudentfindStudentInArray(Studentstudents[50],intid){Studentstudent;for(inti=0;i<50;i++){if(students[i]->id==id){student=students[i];}}eturnstudent}TreePositionfind(TreeElementTypex,SearchTreetree){if(tree==NULL){returnNULL;}if(x->id<tree->element->id){returnfind(x,tree->left);}elseif(x->id>tree->element->id){returnfind(x,tree->right);}else{ntree}}#defineNUM1000000intids;for(inti=0;i<5;i++)ids[i]=rand()%50;doublearrayTimes[5];doubletreeTimes[5];clock_tstart,finish;for(inti=0;i<5;i++){intid=ids[i];start=clock();for(intj=0;j<NUM;j++){findStudentInArray(students,id);}finish=clock();arrayTimes[i]=(double)(finish-start)/CLOCKS_PER_SEC;Studentst=findStudentInArray(students,id);start=clock();for(intk=0;k<NUM;k++){find(st,randTree);}finish=clock();treeTimes[i]=(double)(finish-start)/CLOCKS_PER_SEC;}for(inti=0;i<5;i++){printf("学号%d的数组查找用了%f秒\n",ids[i],arrayTimes[i]);}doublearrTime=average(arrayTimes);printf("平均时间为%f\n",arrTime);for(inti=0;i<5;i++){printf("学号%d的二叉树查找用了%f秒\n",ids[i],treeTimes[i]);}doubletreeTime=average(treeTimes);printf("平均时间为%f\n",treeTime);经过几次的测试，如下图，发现数组查找的时间基本为二叉树查找的一倍，显然在这种这种情况下，二叉树的查找效率比数组快。可以看到，在这种极端情况下，二叉树的查找效率十分差，比数组查找慢一倍多。可以看到，在这种极端情况下，二叉树的查找效率十分差，比数组查找慢一倍多。情况三：情况三：二叉树元素插入的顺序是随机的，数组按学号升序储存学生，但这次数组的查找算法不同，考虑到数组中的下标就是学号，可以直接通过学号ID映射到数组下标来查情况二：考虑一种极端的情况，二叉树按照学号的升序或者降序来插入学生，为了比较，数组也是按照升序来储存。这样会使二叉树变成一条由左节点或者右节点组成的长链。这种情况下，二叉树中的查找时间就是O(n^2)，和数组的遍历查找时间处于同一个数量级。但由于二叉树中的查找是指针操作，比数组操作慢，故二叉树效率会低。以下为测试代码，先生成一个50元素的Student数组，数组中元素的学号ID从0开intafor(inti=0;i<50;i++)a[i]=i;Studentstudents[50];genStudentArray(students,a);Treetree=makeStudentTree(students);testTime(students,tree);其中testTime()函数中的代码为测试代码，和上一种情况的代码一样，现在只关注测试时间就行了，测试的时间如下。