brtree.txt

hash表的使用

#include<string.h>
#include<alloc.h>
#include<stdio.h>
#define TRUE 1
#define FALSE 0
KEYTYPE a[maxsize]={-1};
typedef struct node{KEYTYPE key;struct node *lchild,*rchild;}Bstnode;
Bstnode *searchnode(int w,Bstnode *r)                                        {Bstnode *p;
 if(r==NULL)p=NULL;
 else {if(w==r->key)p=r;
       else if(w>r->key)p=searchnode(w,r->rchild);
            else p=searchnode(w,r->lchild);
      }
 return p;
}
Bstnode *insert_bst(int w,Bstnode p)                                        {if(p==NULL){p=malloc(sizeof(Bstnode));
             p->lchild=NULL;
             p->rchild=NULL;
             p->key=w;
            }
 else if(w>p->key)p->rchild=insert_bst(w,p->rchild);
      else        p->lchild=insert_bst(w,p->lchild);
 return p;
}
Bstnode *getfather(Bstnode p,Bstnode r)                                    {Bstnode *pf;
 if(r==NULL||p==r) pf=NULL;
 else {if(p==r->lchild||p==r->rchild) pf=r;
       else if(p->key>r->key) pf=getfather(p,r->rchild);
            else              pf=getfather(p,r->lchild);
      }
 return pf;
}
Bstnode *dele_bst(Bstnode p,Bstnode r)                                     {Bstnode *temp,*tfather,*pf;
 pf=getfather(p,r);
 if(p->lchild==NULL&&p->rchild==NULL&&pf!=NULL)                                  if(pf->lchild==p) pf->lchild=NULL;
    else              pf->rchild=NULL;
 else if(p->lchild==NULL&&p->rchild==NULL&&pf==NULL)                                  r=NULL;
      else if(p->lchild==NULL&&p->rchild!=NULL&&pf!=NULL)                                   if(pf->lchild==p) pf->lchild=p->rchild;
               else              pf->rchild=p->rchild;
           else if(p->lchild==NULL&&p->rchild!=NULL&&pf==NULL)                                 r=p->rchild;
                else if(p->lchild!=NULL&&p->rchild==NULL&&pf!=NULL)                                  if(pf->lchild==p) pf->lchild=p->lchild;
                        else              pf->rchild=p->lchild;
                     else if(p->lchild!=NULL&&p->rchild==NULL&&pf==NULL)                                  r=p->lchild;
                          else if(p->lchild!=NULL&&p->rchild!=NULL)                                            {temp=p->lchild;
                                   tfather=p;                                                                   while(temp->rchild!=NULL)
                                      {tfather=temp;temp=temp->rchild;}
                                   p->key=temp->key;                                                            if(tfather!=p) tfather->rchild=temp->lchild;
                                   else tfather->lchild=temp->lchild;
                                  }
 return r;
}
int at(char str,char ch)                                                    {int r;
 while(*str!='\0'&&*str!=ch) str++;
 r=(*str==ch);
 return r;
}
int print_bst(Bstnode p)                                                    {int i=0,j;
 if(p!=NULL)
    {if(p->lchild==NULL&&p->rchild==NULL) a[i++]=p->key;
     else {print_bst(p->lchild);a[i++]=p->key;print_bst(p->rchild);}
    }
 return i;
}
void print(int i)                                                            {int j;
 for(j=0;j<i;j++)printf("%d  ",a[j]);printf("\n");
}
Bstnode *creat_bst()                                                         {Bstnode *Root,*p;int loop=FALSE;int s;Root=NULL;
 do
   {scanf("%d",&s);
    if(s==0) loop=TRUE;
    else {p=searchnode(s,Root);
          if(p==NULL)
            {Root=insert_bst(s,Root);                                                     print_bst(Root);
            }
         }
   }while(!loop);
 return Root;
}
Bstnode *insert(Bstnode Root)                                               {Bstnode *p;int s;scanf("%d",&s);
 if(s!=0)
    {p=searchnode(s,Root);
     if(p==NULL){Root=insert_bst(s,Root);
                 print_bst(Root);
                }
    }
 return Root;
}
Bstnode *search_bst(Bstnode Root)                                           {int s;Bstnode *p;scanf("%d",&s);
 if(s!=0)
   {p=searchnode(s,Root);
    if(p==NULL)return NULL;                                                      else return p;                                                              }
}
Bstnode *delete(Bstnode Root)                                               {int s;Bstnode *p;char ch[5];scanf("%d",&s);
 if(s!=0) {p=searchnode(s,Root);
           if(p==NULL) return NULL;
           else {gets(ch);
                 if(at(ch,'y')||at(ch,'r'))
                    Root=dele_bst(p,Root);
                }
          }
 print_bst(Root);
 return (Root);
}
main()
{Bstnode *Root;int loop,i,t=0; loop=TRUE;
 while(loop)
 {printf("\n");printf("\n");printf("\n");
  printf("1:create\n");
  printf("2:insert\n");
  printf("3:search\n");
  printf("4:delete\n");
  printf("5:disappear\n");
  printf("0:exit main\n");
  scanf("%d",&i);
  switch(i)
   {case 0:loop=FALSE;break;                                                    case 1:Root=creat_bst();break;                                               case 2:Root=insert(Root);break;                                              case 3:search_bst(Root);break;                                                case 4:Root=delete(Root);break;                                              case 5:printf("\n");
           if(Root!=NULL)printf("The root of the tree is:%d\n",Root->key);
           t=print_bst(Root);print(t);break;
   }
 }
}