数据结构教程第三十一课动态查找表

►数据结构教程第三十一课动态查找表数据结构教程第三十一课动态查找表教学目的：掌握二叉排序树的实现方法教学重点：二叉排序树的实现教学难点：构造二叉排序树的方法授课内容：一、动态查找表的定义动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。以政是动态查找表的定义：ADTDymanicSearchTable{数据对象Ｄ：Ｄ是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系Ｒ：数据元素同属一个集合。基本操作Ｐ：InitDSTable(&DT);DestroyDSTable(&DT);SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,Visit());}ADTDynamicSearchTable二、二叉排序树及其查找过程二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：１、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；２、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；３、它的左、右子树了分别为二叉排序树。如果取二叉链表作为二叉排序树的存储结构，则上述查找过程如下：BiTreeSearchBST(BiTreeT,KeyTypekey){if(!T)||EQ(key,T-data.key))return(T);elseifLT(key,T-data.key)return(SearchBST(T-lchild,key));elsereturn(SearchBST(T-rchild.key));}//SearchBST三、二叉排序树的插入和删除二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){if(!T){p=f;returnFALSE;}elseifEQ(key,T-data.key){p=T;returnTRUE;}elseifLT(key,T-data.key)SearchBsT(T-lchild,key,T,p);elseSearchBST(T-rchild,key,T,p);}//SearchBST插入算法：StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p){s=(BiTree)malloc(sizeof(BiTNode));s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;elseif(LT(e.key,p-data.key)p-lchild=s;elsep-rchild=s;returnTRUE;}elsereturnFALSE;}//InsertBST在二叉排序树中删除一个节点的算法：StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;else{ifEQ(key,T-data.key)Delete(T);elseifLT(key,T-data.key)DeleteBST(T-lchild,key);elseDeleteBST(T-rchild,key);returnTRUE;}}voidDelete(BiTree&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=s-rchild}//转左，然后向右到尽头p-data=s-data;//s指向被删结点的前驱if(q!=p)q-rchild=s-lchild;//重接*q的右子树elseq-lchild=s-lchild;//重接*q的左子树（方法一结束）//或可用方法二：//q=s=(*p)-l;//while(s-r)s=s-r;//s-r=(*p)-r;//free(*p);//(*p)=q;}}请看一个示例源程序。#includealloc.h#defineERROR0;#defineFALSE0;#defineTRUE1;#defineOK1;typedefintElemType;typedefintStatus;typedefintKeyType;#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))typedefstructBinaryTree{ElemTypedata;structBinaryTree*l;structBinaryTree*r;}*BiTree,BiNode;BiNode*new(){return((BiNode*)malloc(sizeof(BiNode)));}CreateSubTree(BiTree*T,ElemType*all,inti){if((all[i]==0)||i16){*T=NULL;returnOK;}*T=new();if(*T==NULL)returnERROR;(*T)-data=all[i];CreateSubTree(&((*T)-l),all,2*i);CreateSubTree(&((*T)-r),all,2*i+1);}CreateBiTree(BiTree*T){ElemTypeall[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};CreateSubTree(T,all,1);}printelem(ElemTyped){printf(%d\n,d);}PreOrderTraverse(BiTreeT,int(*Visit)(ElemTyped)){if(T){if(Visit(T-data))if(PreOrderTraverse(T-l,Visit))if(PreOrderTraverse(T-r,Visit))returnOK;returnERROR;}elsereturnOK;}InOrderTraverse(BiTreeT,int(*Visit)(ElemTyped)){if(T){if(InOrderTraverse(T-l,Visit))if(Visit(T-data))if(InOrderTraverse(T-r,Visit))returnOK;returnERROR;}elsereturnOK;}StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree*p){if(!T){*p=f;returnFALSE;}elseifEQ(key,T-data){*p=T;returnTRUE;}elseifLT(key,T-data)SearchBST(T-l,key,T,p);elseSearchBST(T-r,key,T,p);}StatusInsertBST(BiTree*T,ElemTypee){BiTreep;BiTrees;if(!SearchBST(*T,e,NULL,&p)){s=(BiTree)malloc(sizeof(BiNode));s-data=e;s-l=s-r=NULL;if(!p)*T=s;elseif(LT(e,p-data))p-l=s;elsep-r=s;returnTRUE;}elsereturnFALSE;}voidDelete(BiTree*p){BiTreeq,s;if(!(*p)-r){q=(*p);(*p)=(*p)-l;free(q);}elseif(!(*p)-l){q=(*p);(*p)=(*p)-r;free(q);}else{/*q=(*p);s=(*p)-l;while(s-r){q=s;s=s-r;}(*p)-data=s-data;if(q!=(*p))q-r=s-l;elseq-l=s-l;free(s);*/q=s=(*p)-l;while(s-r)s=s-r;s-r=(*p)-r;free(*p);(*p)=q;}}StatusDeleteBST(BiTree*T,KeyTypekey){if(!(*T)){returnFALSE;}else{if(EQ(key,(*T)-data))Delete(T);elseif(LT(key,(*T)-data))DeleteBST(&((*T)-l),key);elseDeleteBST(&((*T)-r),key);returnTRUE;}}main(){BiTreeroot;BiTreesroot=NULL;inti;inta[10]={45,23,12,3,33,27,56,90,120,62};system(cls);CreateBiTree(&root);printf(PreOrderTraverse:\n);PreOrderTraverse(root,printelem);printf(InOrderTraverse:\n);InOrderTraverse(root,printelem);for(i=0;i10;i++)InsertBST(&sroot,a[i]);printf(InOrderTraverse:\n);InOrderTraverse(sroot,printelem);for(i=0;i3;i++)DeleteBST(&sroot,a[i]);printf(Nowsroothasnodes:\n);InOrderTraverse(sroot,printelem);}