二叉平衡排序树.docx

数据结构课程设计报告专业：计算机科学与技术班级：2009级1姓名：陈雪敏指导教师：张珑学号：2009040608二叉平衡排序树一、课程设计内容问题描述：从一棵空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基本要求：L创建(插入、调整、改组)2.输出二、概要设计1、.主要数据结构定义typedefstructnodenode;structnodenode*parent;node*left;node*right;intbalance;左右子树高度之差intkey;I.2：主要函数说明intSearchNode(intkey,node*root,node*parent)：按key查找结点node*minNode(node*root)：树root的最小结点node*maxNode(node*root)：树root的最大结点node*preNode(node*target)：求前驱结点node*nextNode(node*target)：求后继结点node*adjustAVL(node*root,node*parent,node*child)：调整，保证二叉树的平衡性node*insertNode(intkey,node*root)：插入node*deleteNode(intkey,node*root)：删除node*CreateAVL(int*data,intsize)：建造新的二叉树voidinterordertraverse(node*root)：中序遍历voidpreordertraverse(node*root)：先序遍历3、二叉排序树的插入和删除a.二叉排序树的插入在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。插入过程：若二叉排序树已存在，则返回根节点；当节点不存在时，将待插结点关键字key和树根关键字parent->key进行比较，若key<parent->key,则插入到根的左子树中，否则，则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。并且注意二叉树的平衡性，时刻调整。b.二叉排序树的删除假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性，可设*parent是*Parent->left;的左孩子。下面分3种情况进行讨论：(1)若*parent结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需要修改其双亲结点的指针即可。(2)若*parent结点只有左子树PL或者只有右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。(3)若*parent结点的左子树和右子树均不空。并且注意二叉树的平衡性，时刻调整。4、中序遍历和先序遍历voidinterordertraverse(node*root)中序遍历(if(root!=NULL)(interordertraverse(root->left);printf(,%d,%dn”,root->key,root->balance);interordertraverse(root->right);)voidpreordertraverse(node*root)先序遍历if(root!=NULL)printf(z,%d,%dn”,root->key,root->balance);preordertraverse(root->left);preordertraverse(root->right);1J5、调整二叉树的平衡性node*adjustAVL(node*root,node*parent,node*child)主要有四种调整类型根据平衡因子主要有LR、LL、RL、RR(1)>根据Parent->balance的值为2时，child->balance=-1时是LR型，否则为LL型；if(child->balance=-1)LR型(cur-child->right;cur->parent=parent->parent;child->right=cur->left;if(cur->left!=NULL)cur->left->parent=child;parent->left=cur->right;if(cur->right!=NULL)cur->right->parent-parent;cur->left=child;child->parent-cur;cur->right=parent;if(parent->parent!-NULL)if(parent->parent->left=parent)parent->parent->left-cur;elseparent->parent->right=cur;elseroot=cur;parent->parent-cur;if(cur->balance=0)parent->balance=0;child->balance=0;)elseif(cur->balance=-1)(parent->balance-0;child->balance=1;elseparent->balance=-1;child->balance-0;)cur->balance=0;)else/LL型child->parent-parent->parent;parent->left=child->right;if(child->right!=NULL)child->right->parent=parent;child->right=parent;if(parent->parent!=NULL)if(parent->parent->left=parent)parent->parent->left=child;elseparent->parent->right-child;elseroot=child;parent->parent=child;if(child->balance=1)插入时child->balance-O;parent->balance=O;)else删除时child->balance=-1;parent->balance-1;)break;(2)、Parent->balance的值为-2时，child->balance=1时是RL型，否则为RRif(child->balance=1)/RL型(cur=child->left;cur->parent=parent->parent;child->left=cur->right;if(cur->right!=NULL)cur->right->parent=child;parent->right=cur->left;if(cur->left!=NULL)cur->left->parent=parent;cur->left=parent;cur->right=child;child->parent-cur;if(parent->parent!=NULL)if(parent->parent->left=parent)parent->parent->left=cur;elseparent->parent->right=cur;elseroot-cur;parent->parent=cur;if(cur->balance=0)(parent->balance=0;child->balance=0;elseif(cur->balance=1)parent->balance=0;child->balance-1;)else(parent->balance-1;child->balance=O;cur->balance=O;)else/RR型child->parent=parent->parent;parent->right=child->left;if(child->left!=NULL)child->left->parent=parent;child->left=parent;if(parent->parent!-NULL)if(parent->parent->left=parent)parent->parent->left-child;elseparent->parent->right=child;elseroot=child;parent->parent-child;if(child->balance=-1)插入时child->balance=0;parent->balance=0;else删除时child->balance-1;parent->balance=-1;)break;6、主函数Voidmain()给出了一组数据1,13,7,4),对数据中序遍历和先序遍历，然后是插入、删除、查询、退出操作。三、系统实现运行环境Windows7操作系统，MicrosoftVisualC+6.0。四、程序#include<stdio.h>include<string.h>#include<stdlib.h>#include<stdlib.h>#include<errno.h>include<assert.h>/assert用于调试声明宏，用于定位程序开发中的逻辑错误当参数expression为false时程序执行被中断tjedefstructnodenode;structnodenode*parent;node*left;node*right;intbalance;平衡因子(左右子树高度之差)intkey;)；externvoidinterordertraverse(node*root);中序遍历externvoidpreordertraverse(node*root);前序遍历intSearchNode(intkey,node*root,node*parent)按key查找结点(node*temp;assert(root!=NULL);temp=root;*parent=root->parent;while(temp!=NULL)(if(temp->key=key)return1;else*parent=temp;if(temp->key>key)temp=temp->left;elsetemp=temp->right;returnO;)node*minNode(node*root)树root的最小结点returnNULL;while(root->left!=NULL)root=root->left;returnroot;node*maxNode(node*root)树root的最大结点(if(root=NULL)returnNULL;while(root->right!=NULL)root=root->right;returnroot;node*preNode(node*target)求前驱结点(if(target=NULL)returnNULL;if(target->left!=NULL)returnmaxNode(target->left);elsewhile(target->parent!=NULL)&&(target!=target->parent->right)target=target->parent;returntarget->parent;)node*nextNode(node*target)求后继结点(if(target=NULL)returnNULL;if(target->right!=NULL)returnminNode(target->right);elsewhile(target->parent!=NULL)&&(target!=target->parent->left)target=target->parent;returntarget->parent;)node*adjustAVL(node*root,node*parent,node*Child)调整旋转操作保持二叉排序树的平衡性(node*cur;assert(parent!=NULL)&&(chiId!=NULL);switch(parent->balance)(case2:平衡因子由1增至2if(child->balance=-1)LR型双向旋转(先左后右)平衡处理cur=child->right;cur->parent=parent->parent;child->right=cur->left;if(cur->left!=NULL)cur->left->parent=child;parent->left=cur->right;if(cur->right!=NULL)cur->right->parent=parent;cur->left=child;child->parent=cur;cur->right=parent;if(parent->parent!=NULL)if(parent->parent->left=parent)parent->parent->Ieft=cur;elseparent->parent->right=cur;elseroot=cur;parent->parent=cur;if(cur->balance=0)(parent->balance=0;child->balance=0;)elseif(cur->balance=-1)(parent->balance=0;child->balance=1;else(parent->balance=-1;child->balance=0;cur->balance=0;elseLL型单向右旋平衡处理(child->parent=parent->parent;parent->left=child->right;if(child->right!=NULL)child->right->parent=parent;child->right=parent;if(parent->parent!=NULL)if(parent->parent->left=parent)parent->parent->left=child;elseparent->parent->right=child;elseroot=child;parent->parent=child;if(child->balance=1)插入时(child->balance=0;parent->balance=0;)else删除时(child->balance=-1;parent->balance=1;)break;case-2:平衡因子由T变为-2if(child->balance=1)RL型双向旋转(先右后左)平衡处理(cur=child->left;cur->parent=parent->parent;child->left=cur->right;if(cur->right!=NULL)cur->right->parent=child;parent->right=cur->left;if(cur->left!=NULL)cur->left->parent=parent;cur->left=parent;cur->right=child;child->parent=cur;if(parent->parent!=NULL)if(parent->parent->left=parent)parent->parent->left=cur;elseparent->parent->right=cur;elseroot=cur;parent->parent=cur;if(cur->balance=0)(parent->balance=0;child->balance=0;elseif(cur->balance=1)(parent->balance=O;child->balance=-1;)else(parent->balance=1;child->balance=O;cur->balance=O;)else/RR型单向左旋平衡处理(child->parent=parent->parent;parent->right=child->left;if(child->left!=NULL)child->left->parent=parent;child->left=parent;if(parent->parent!=NULL)if(parent->parent->left=parent)parent->parent->left=child;elseparent->parent->right=child;elseroot=child;parent->parent=child;if(child->balance=-1)插入时(child->balance=0;parent->balance=0;)else删除时(child->balance=1;parent->balance=-1;)break;)returnroot;node*insertNode(intkey,node*root)插入node*parent,*cur,*child;assert(root!=NULL);if(searchNode(key,root,arent)结点已存在returnroot;else节点不存在(cur=(node*)malIoc(sizeof(node);cur->parent=parent;cur->key-key;cur->left=NULL;cur->right=NULL;cur->balance=O;if(key<parent->key)(parent->left=cur;child=parent->left;)else(parent->right=cur;child=parent->right;)while(parent!=NULL)查找需要调整的最小子树(if(child=parent->left)if(parent->balance=-1)(parent->balance=O;returnroot;)elseif(parent->balance=1)(parent->balance=2;break;)else(parent->balance=1;child=parent;parent=parent->parent;)elseif(parent->balance=1)parent->balance=O;returnroot;elseif(parent->balance=-1)(parent->balance=-2;break;)else(parent->balance=-1;child=parent;parent=parent->parent;if(parent=NULL)returnroot;returnadjustAVL(root,parent,child);)node*deleteNode(intkey,node*root)删除(node*dNode,*parent,*child,*tp;inttemp,tc;assert(root!=NULL);if(!SearchNode(key,root,&parent)如果节点不存在returnroot;else节点存在(if(parent=NULL)dNode=root;elseif(parent->left!=NULL)&&(parent->Ieft->key=key)dNode=parent->left;elsedNode=parent->right;child=dNode;while(child->left!=NULL)(child->right!=NULL)确定需要删除的结点(if(child->balance=1)child=preNode(dNode);elsechild=nextNode(dNode);temp=child->key;child->key=dNode->key;dNode->key=temp;dNode=child;child=dNode;parent=dNode->parent;while(parent!=NULL)查找需要调整的最小子树(if(child=parent->left)if(parent->balance=1)(parent->balance=0;child=parent;parent=parent->parent;elseif(parent->balance=-1)(parent->balance=-2;child=parent->right;temp=Parent->right->balance;临时变量保存tp=Parent->parent;临时变量保存if(tp!=NULL)if(parent-tp->left)tc=1;elsetc=-1;elsetc=0;root=adjustAVL(root,parent,child);if(temp=0)break;else(if(tc=1)child=tp->left;elseif(tc=-1)child=tp->right;parent=tp;)else(parent->balance=一1;break;)elseif(parent->balance=-1)(parent->balance=0;child=parent;parent=parent->parent;elseif(parent->balance=1)(parent->balance=2;child=parent->left;temp=Parent->left->balance;临时变量保存tp=Parent->parent;临时变量保存if(tp!=NULL)if(parent=tp->left)tc=1;elsetc-1;elsetc=O;root=adjustAVL(root,parent,child);if(temp=0)break;else(if(tc=1)child=tp->left;elseif(tc=-1)child=tp->right;parent=tp;)else(parent->balance=1;break;)if(dNode->parent!=NULL)if(dNode=dNode->parent->left)dNode->parent->left=NULL;elsedNode->parent->right=NULL;free(dNode);if(root=dNode)root=NULL;rOOt被删除，避免野指针dNode=NULL;returnroot;node*CreateAVL(int*data,intSiZe)构造平衡二叉树inti;node*root;if(size<l)returnNULL;root=(node*)malIoc(sizeof(node);root->parent-NULL;root->left=NULL;root->right=NULL;root->key=dataO;root->balance=O;for(i=l;i<size;i+)root=insertNode(datai,root);returnroot;)voiddestroyAVL(node*root)销毁平衡二叉树(if(root!=NULL)(destroyAVL(root->left);destroyAVL(root>right);free(root);root=NULL;)voidinterordertraverse(node*root)中序遍历(if(root!=NULL)(interordertraverse(root->left);printf(zz%d,%dn”,root->key,root->balance);interordertraverse(root->right);)voidpreordertraverse(node*root)先序遍历(if(root!=NULL)(printf(,z%d,%dn,z,root->key,root->balance);preordertraverse(root->left);preordertraverse(root->right);/mainvoidmain()(intdata=1,13,7,4,flag=l,n=0;node*root;node*parent;root=CreateAVL(data,sizeof(data)sizeof(data0);printf("+n”);Printf("中序遍历r);interordertraverse(root);中序遍历printf(n);Printf("先序遍历n");preordertraverse(root);先序遍历while(flag)inta;Printf(请选择操作：ntl.插入nt2、删除nt3、查询nt4、退出n);scanf("%d",&n);switch(n)case 1:Printf(输入插入的值：);scanf("%d",&a);insertNode(a,root);printf("+n)；interordertraverse(root);printf(n);preordertraverse(root);break;case 2:Printf(输入待删除的值：)；scanf(z/%dz,&a);deleteNode(a,root);Printf(+n)interordertraverse(root);printf(n)；preordertraverse(root);break;case 3:Printf(输入待查询的值：)；scanf("%c,&a);if(searchNode(a,root,fcparent)Printf("存在该记录!n)；elsePrintf(“无记录!r);break;case 4:flag=O;break;)destroyAVL(root);)五、输出结果4,013,0请选择操作：插入2、删陇3、查询4、退出腌入插入的值：24.0Lak0卜，113,010 0 0入嚼. 插那查 色、：12 3 操。择六、心得体会通过这次数据结构课程设计,将所学知识应用在实践中，锻炼了自己的动手能力,学到了新的知识，同时也在设计过程中发现了自己的在某些知识点上掌握的不够扎实和透彻，这是在以后学习中要特别注意的问题。这次课程设计给我感悟最深的还有以下几点，这是我在以后学习和工作中要时刻牢记的：1 .编程过程中要认真谨慎，决不能有半点马虎，一些小的疏忽可能是以后程序检错中很难找到的错误。2 .在设计比较大程序时候，要多和同学交流，每一次有意义的交流将使自己受益匪浅或在某个难点上豁然开朗。3 .在设计比较大的程序时，必须要有一个总的构思，并对每个小的模块或函数要有详细的算法思想。