查找技术综合应用.doc

《查找技术综合应用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、查找技术综合应用1、源程序代码#include#include#definemax25typedefstructbst〃定义二叉树{intkey;//intdate;structbst*lchild,*Tchild;〃左右孩子////////////////////////////////二叉树的插入函数intInsertbst(bst*&p,intk)〃在二叉树中插入一个数{if(p=NULL)〃如果二叉树为空直接插入p=(bst*)malloc(sizeof(bst));p->key=k;p->lchild=p->rchil

2、d=NULL;//左右孩子的初值为NULLreturn1;}elseif(k==p->key)〃如果插入的是已经存在，就不在插入return0;elseif(kkey)〃如果小于关键字，递归调用左子树{returnInsertbst(p->lchild,k);}else〃如果大于关键字，递归调用右子树returnInsertbst(p->rchild,k);}bst*Creatbst(inta[J,intn)〃二叉排序树的创建{bst*bt=NULL;〃初始化树为空inti=0;while(i

3、中returnbt;〃返回建立的二叉树的更指针IIIIIIIIIIIIIIIIIIIIIIIIIIIvoidInorderCbst^b)//屮序遍历二叉树的递归算法{if(b!=NULL){Inorder(b->lchild);printf(n%dtH,b->key);Inorder(b->rchild);}}/////////////////////查找函数intSearchbst(bst*&bt,int&k)〃二叉树的查找{if(bt==NULL)//如果为空返回0return0;if(bt->key==k)returnk;〃如果有则返冋k值if(k

4、key)returnSearchbst(bt->lchild,k);//递归调用左子树elsereturnSearchbst(bt->rchild,k);//递归调用右子树}/////////////////删除函数voidDelatel(bst*p,bst*&r)〃当结点有左右子树的删除过程{bst*q;if(r->rchild!=NULL)Delatel(p,r->rchild);〃递归找到最右下结点else{p->key=r->key;//将r的关键字赋值给Pq=r；r=r->lchild;〃直接将其左子树的根结点放在被删除的位置上free(q);〃释放原r的

5、空间}voidDelate(bst*&p)〃从二叉树中删除*P结点bst*q;if(p->rchild=NULL)//结点没有右子树的情况{q=p；p=p->lchild；//直接将其右子树的跟结点放在删除的结点位置free(q);}elseif(p->lchild=NULL)〃结点没有左子树的情况{q=p;p=p->rchild;//直接将其左子树的跟结点放在删除的结点位置free(q);}elseDelatel(p,p->lchild);//结点既没有左子树也没有右子树intDelatebst(bst*&bt,intk)〃删除函数if(bt==NULL)retu

6、rn0;//空二叉树删除失败else{if(kkey)returnDelatebst(bt->lchild,k);elseif(k>bt->key)returnDelatebst(bt->rchild,k);else{Delate(bt);return1;}}}lllllllllllllllllllllllllllllllllllllllllvoidmain()bst*p;inta[max],i,n,m;printfC输入要排序的个数n:n);scanf(M%dH,&n);for(i=0;i

7、st(a,n);system(HclsH);printfC输入排序后的序列：rT);Inorder(p);printf(nH);printfC输入要插入的数:H);scanf(H%dH,&m);Insertbst(p,m);Inorder(p);printf(n");printf（n输入要查询的数「）；scanf(n%d!&m);if(Searchbst(p,m)==O)printf(”该序列中没有该元素・”);printf(喳询成功该数是%dn,m);printf(nH);printf(”输入要删除的数:n);scanf(n%dn,