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

1、  数据结构教程 第三十一课 动态查找表数据结构教程 第三十一课 动态查找表 教学目的： 掌握二叉排序树的实现方法教学重点： 二叉排序树的实现教学难点： 构造二叉排序树的方法授课内容：一、动态查找表的定义动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。以政是动态查找表的定义：ADT DymanicSearchTable数据对象：是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。

2、数据关系：数据元素同属一个集合。基本操作：InitDSTable(&DT);DestroyDSTable(&DT);SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,Visit();ADT DynamicSearchTable二、二叉排序树及其查找过程二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；、它的左、右子

3、树了分别为二叉排序树。如果取二叉链表作为二叉排序树的存储结构，则上述查找过程如下：BiTree SearchBST(BiTree T,KeyType key)if(!T)|EQ(key,T->data.key) return (T);else if LT(key,T->data.key) return (SearchBST(T->lchild,key);else return (SearchBST(T->rchild.key);/SearchBST三、二叉排序树的插入和删除二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在查找过程中，当树中不存在关键

4、字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)if(!T) p=f;return FALSE;else if EQ(key,T->data.key) p=T;return TRUE;else if LT(key,T->data.key) SearchBsT(T->lchild,key,T,p);else SearchBST(T->rchild,key,T,p

5、);/SearchBST插入算法：Status InsertBST(BiTree &T,ElemType e)if(!SearchBST(T,e.key,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s->data=e;s->lchild=s->rchild=NULL;if(!p) T=s;else if (LT(e.key,p->data.key) p->lchild=s;else p->rchild=s;return TRUE;else return FALSE;/InsertBST在二叉排序树中删除一个节点的算

6、法： Status DeleteBST(BiTree &T,KeyType key)if(!T) return FALSE;elseif EQ(key,T->data.key) Delete(T);else if LT(key,T->data.key) DeleteBST(T->lchild,key);else DeleteBST(T->rchild,key);return TRUE;void Delete(BiTree &p)if(!p->rchild)q=p; p=p->lchild; free(q);else if(!p-&g

7、t;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的右子树else q->lchild=s->lchild;/重接*q的左子树 （方法一结束）/或可用方法二：/q=s=(*p)->l; /while(s->r) s=s-&

8、gt;r; /s->r=(*p)->r; /free(*p); /(*p)=q; 请看一个示例源程序。#include <alloc.h>#define ERROR 0;#define FALSE 0;#define TRUE 1;#define OK 1;typedef int ElemType;typedef int Status;typedef int KeyType;#define EQ(a,b) (a)=(b)#define LT(a,b) (a)< (b)#define LQ(a,b) (a)<=(b)typedef struct BinaryT

9、ree ElemType data; struct BinaryTree *l; struct BinaryTree *r;*BiTree,BiNode;BiNode * new() return( (BiNode *)malloc(sizeof(BiNode) );CreateSubTree(BiTree *T,ElemType *all,int i) if (alli=0)|i>16) *T=NULL; return OK; *T=new(); if(*T=NULL) return ERROR; (*T)->data=alli; CreateSubTree(&(*T)-

10、>l),all,2*i); CreateSubTree(&(*T)->r),all,2*i+1);CreateBiTree(BiTree *T) ElemType all16=0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,; CreateSubTree(T,all,1);printelem(ElemType d) printf("%dn",d);PreOrderTraverse(BiTree T,int (*Visit)(ElemType d) if(T) if(Visit(T->data) if(PreOrderTraverse

11、(T->l,Visit)if(PreOrderTraverse(T->r,Visit) return OK; return ERROR; else return OK;InOrderTraverse(BiTree T,int (*Visit)(ElemType d) if(T) if(InOrderTraverse(T->l,Visit) if(Visit(T->data) if(InOrderTraverse(T->r,Visit) return OK; return ERROR; else return OK;Status SearchBST(BiTree T

12、,KeyType key,BiTree f,BiTree *p) if(!T) *p=f;return FALSE; else if EQ(key,T->data) *p=T;return TRUE; else if LT(key,T->data) SearchBST(T->l,key,T,p); else SearchBST(T->r,key,T,p);Status InsertBST(BiTree *T,ElemType e) BiTree p; BiTree s; if(!SearchBST(*T,e,NULL,&p) s=(BiTree)malloc(s

13、izeof(BiNode); s->data=e;s->l=s->r=NULL; if(!p) *T=s; else if (LT(e,p->data) p->l=s; else p->r=s; return TRUE; else return FALSE;void Delete(BiTree *p) BiTree q,s; if(!(*p)->r) q=(*p); (*p)=(*p)->l; free(q); else if(!(*p)->l) q=(*p); (*p)=(*p)->r; free(q); else /* q=(*p

14、); s=(*p)->l; while(s->r) q=s; s=s->r; (*p)->data=s->data; if(q!=(*p) ) q->r=s->l; else q->l=s->l; free(s); */ q=s=(*p)->l; while(s->r) s=s->r; s->r=(*p)->r; free(*p); (*p)=q; Status DeleteBST(BiTree *T,KeyType key) if (!(*T) ) return FALSE; else if ( EQ(key

15、,(*T)->data) Delete(T); else if ( LT(key,(*T)->data) DeleteBST( &(*T)->l), key); else DeleteBST( &(*T)->r),key); return TRUE; main() BiTree root; BiTree sroot=NULL; int i; int a10=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