int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data
if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree 9.32 int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素 {
if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现 if(last
if(last<=x&&T->data>x) //找到了大于x的最小元素 printf(\ last=T->data;
if(T->rchild) MaxLT_MinGT(T->rchild,x); }//MaxLT_MinGT 9.33
void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素 {
if(T->rchild) Print_NLT(T->rchild,x);
if(T->data if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历 }//Print_NLT 9.34 void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间 { if(T->rchild) Delete_NLT(T->rchild,x); if(T->data T=T->lchild; free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T) Delete_NLT(T,x); //继续在左子树中执行算法 }//Delete_NLT 9.35 void Print_Between(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素 { p=T; while(!p->ltag) p=p->lchild; //找到最小元素 while(p&&p->data if(p->data>a) printf(\输出符合条件的元素 if(p->rtag) p=p->rtag; else { p=p->rchild; while(!p->ltag) p=p->lchild; } //转到中序后继 }//while }//Print_Between 9.36 void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x { if(T->data if(T->rtag) //T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p; //修改原线索 } else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if else if(T->data>x) //插入到左子树中 { if(!T->lchild) //T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T; //修改自身的线索 } else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if }//BSTree_Insert_Key 9.37 Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉排序树T中删除元素x { BTNode *pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL; //last始终指向当前结点p的前一个(前驱) while(!p->ltag) p=p->lchild; //找到中序起始元素 while(p) { if(p->data==x) //找到了元素x结点 { pre=last; ptr=p; } else if(last&&last->data==x) suc=p; //找到了x的后继 if(p->rtag) p=p->rtag; else { p=p->rchild; while(!p->ltag) p=p->lchild; } //转到中序后继 last=p; }//while //借助中序遍历找到元素x及其前驱和后继结点 if(!ptr) return ERROR; //未找到待删结点 Delete_BSTree(ptr); //删除x结点 if(pre&&pre->rtag) pre->rchild=suc; //修改线索 return OK; }//BSTree_Delete_key void Delete_BSTree(BiThrTree &T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动 { q=T; if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树 T=T->lchild; else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树 T=T->rchild; else if(!T->ltag&&!T->rtag) //结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild; //找到结点的前驱r和r的双亲s } T->data=r->data; //用r代替T结点 if(s!=T) s->rchild=r->lchild; else s->lchild=r->lchild; //重接r的左子树到其双亲结点上 q=r; }//else free(q); //删除结点 }//Delete_BSTree 分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了. 9.38 void BSTree_Merge(BiTree &T,BiTree &S)//把二叉排序树S合并到T中 { if(S->lchild) BSTree_Merge(T,S->lchild); if(S->rchild) BSTree_Merge(T,S->rchild); //合并子树 Insert_Key(T,S); //插入元素 }//BSTree_Merge void Insert_Key(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上 { if(S->data>T->data) { if(!T->rchild) T->rchild=S; else Insert_Key(T->rchild,S); } else if(S->data if(!T->lchild) T->lchild=S; else Insert_Key(T->lchild,S); } S->lchild=NULL; //插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL; //否则会导致树结构的混乱 }//Insert_Key 分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱. 9.39 void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x { if(T->lchild) BSTree_Split(T->lchild,A,B,x); if(T->rchild) BSTree_Split(T->rchild,A,B,x); //分裂左右子树 if(T->data<=x) Insert_Key(A,T); else Insert_Key(B,T); //将元素结点插入合适的树中 }//BSTree_Split void Insert_Key(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上 { if(!T) T=S; //考虑到刚开始分裂时树A和树B为空的情况 else if(S->data>T->data) //其余部分与上一题同 { if(!T->rchild) T->rchild=S; else Insert_Key(T->rchild,S); } else if(S->data if(!T->lchild) T->lchild=S; else Insert_Key(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key 9.40 typedef struct { int data; int bf; int lsize; //lsize域表示该结点的左子树的结点总数加1 BlcNode *lchild,*rchild; } BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型 BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针 { if(!T) return NULL; //k小于1或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k) return Locate_BlcTree(T->lchild,k); //在左子树中寻找 else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值 }//Locate_BlcTree 9.41 typedef struct { enum {LEAF,BRANCH} tag; //结点类型标识 int keynum; BPLink parent; //双亲指针 int key[MAXCHILD]; //关键字 union { BPLink child[MAXCHILD];//非叶结点的孩子指针 struct { rectype *info[MAXCHILD];//叶子结点的信息指针 BPNode *next; //指向下一个叶子结点的链接 } leaf; } } BPNode,*BPLink,*BPTree;//B+树及其结点类型 Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos { p=T; while(p.tag==BRANCH) //沿分支向下查找 { for(i=0;i p=p->child[i]; } for(i=0;i }//BPTree_Search 9.42 void TrieTree_Insert_Key(TrieTree &T,StringType key)//在Trie树T中插入字符串key,StringType的结构见第四章 { q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key; //建叶子结点 klen=key[ 0 ]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; } //自上而下查找 if(p->kind==BRANCH) //如果最后落到分支结点(无同义词): { p->bh.ptr[ord(key[i])]=q; //直接连上叶子 p->bh.num++; } else //如果最后落到叶子结点(有同义词): { r=(TrieNode*)malloc(sizeof(TrieNode)); //建立新的分支结点 last->bh.ptr[ord(key[i-1])]=r; //用新分支结点取代老叶子结点和上一层的联系 r->kind=BRANCH;r->bh.num=2; r->bh.ptr[ord(key[i])]=q; r->bh.ptr[ord(p->lf.k[i])]=p; //新分支结点与新老两个叶子结点相连 } }//TrieTree_Insert_Key 分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层. 9.43 Status TrieTree_Delete_Key(TrieTree &T,StringType key)//在Trie树T中删除字符串key { p=T;i=1; while(p&&p->kind==BRANCH&&i<=key[ 0 ]) //查找待删除元素 { last=p; p=p->bh.ptr[ord(key[i])]; i++; } if(p&&p->kind==LEAF&&p->lf.k=key) //找到了待删除元素 { last->bh.ptr[ord(key[i-1])]=NULL; free(p); return OK; } else return ERROR; //没找到待删除元素 }//TrieTree_Delete_Key 9.44 void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法 { for(i=1;i<=26;i++) for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测 if(H(H.elem[j].key)==i) printf(\}//Print_Hash int H(char *s)//求Hash函数 { if(s) return s[ 0 ]-96; //求关键字第一个字母的字母序号(小写) else return 0; }//H 9.45 typedef *LNode[MAXSIZE] CHashTable; //链地址Hash表类型 Status Build_Hash(CHashTable &T,int m)//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突. { if(m<1) return ERROR; T=malloc(m*sizeof(WORD)); //建立表头指针向量 for(i=0;i while((key=Inputkey())!=NULL) //假定Inputkey函数用于从键盘输入关键字 { q=(LNode*)malloc(sizeof(LNode)); q->data=key;q->next=NULL; n=H(key); if(!T[n]) T[n]=q; //作为链表的第一个结点 else { for(p=T[n];p->next;p=p->next); p->next=q; //插入链表尾部.本算法不考虑排序问题. } }//while return OK; }//Build_Hash 9.46 Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k { h=2*(100*(row/10)+col/10); //作者设计的Hash函数 while(H.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1) 000; if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash 分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1). 数据结构辅导站 返回主页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第八章查找(2)在线全文阅读。
相关推荐：