二叉排序树中删除一个.ppt

二叉排序树上的删除，相当于删去有序序列上的一个记录，应保证删除结点后，二叉排序树的特性不变。删除结点可有三种情况：1.若被删除结点*p为叶子结点，即其pL和pR均为空树。由于叶子结点的存在若不破坏整株树的结构，则只需修改其父结点的指针即可。2.若*p结点只有左子树pL或只有右子树pR，此时只要令pL或pR直接成为其父结点*f的左子树即可。可见，也不破坏二叉排序树的特性。3.若*p结点的左、右子树均不空，不能简单处理，可有两种情况。例：二叉排序树中删除一个

结点的算法DeleteBST(T,key){if(!T)returnFalse;else{if(EQ(key,T-data.key))returnDelete(T);if(LT(key,T-data.key))returnDeleteBST(T-lchild,key);elsereturnDeleteBST(T-rchild,key);}}//DeleteBST上述三种情况的删除算法Delete(p)/*p被删除点*/{if(!p-rchild)/*右子树空接其左子树*/{q=p;p=p-lchild;free(q);}elseif(!p-lchild)/*只接其右子树*/{q=p;p=p-rchild;free(q);}else{q=p;s=p-lchild;while(s-rchild){q=s;s=p-lchild;}/*转左，然后向右到尽头*/p-data=s-data;/*s指向删除结点的前驱*/if(q!=p)q-rchild=s-lchild;/*接*p的右子树*/elseq-lchild=s-lchild;/*接*p的左子树*/deletes;}returnTRUE;}//Delete三.二叉排序树的查找分类从平均查找长度分析：设有6个记录，其关键字序列为(45,24,53,12,37,93)或由另一种序列构成(12,24,37,45,53,93)其对应的二叉排序树：(a)树的深度为3(b)树的深度为6若每个记录的查找概率相等，为，则树的平均查找长度为：AsL(a)=(1+2+2+3+3+3)=AsL(b)=(1+2+3+4+5+6)=查找关键字与给定值的结点的过程，是从根结点到该结点路径的过程，和给定值比较的关键字个数等于路径长度加1（或结点所在层次数）。可见，含有n个结点的二叉排序树的平均查找时间和树的形态有关。若构造二叉排序树时，按关键字有序构造，树的深度为n。其平均查找长度为，这是最差的情况。若二叉排序树的形态和折半查找的判定树相同。其平均查找长度Log2n成正比。第十章内部排序10.1术语和约定排序(ordering)也叫分类(sorting)，是将一组数据按照规定顺序进行排列，其目的是为了方便查询和处理。按分类时分类对象存放的设备，分为内部排序和外部排序。排序过程中数据对象全部在内存中进行，叫内部排序。排序过程中数据对象并非完全在内存中进行叫外部排序。分类的稳定性：对于给定数组A，经排序处理后，满足关系：A[1].keyA[2].key…A[n].key若在排序前存在关系：A[i].keyA[j].key(1ijn)经排序后，A[i]和A[j]分别被移至A[i1]和A[j1]，并且i1和j1满足关系1ijn我们称这种排序是稳定的，否则称其为不稳定的。影响排序性能的因素：比较关键字的次数—当关键字是字符串时，只主要因素。交换记录位置和移动记录的次数—当记录很大时，是主要因素。上述两条是排序过程中进行的基本操作。待排序记录序列可有三种存贮方式：待排序的一组记录存放在地址连续的一组存贮单元中。存放在静态链表中。地址排序，即记录存放在一组地址连续的单元中。另设一个指示各记录存贮位置的地址向量。排序过程中不移动记录本身，而移动地址向量中记录的地址。待排记录的数据类型：#definemaxsize20typedefintkeytype;typedefstruct{