binarysortseach2.cpp

数据结构c++-书的一些源代码

#include <stdio.h>

typedef int keytype;

typedef struct BSNode
{
   keytype key;
   struct BSNode *lchild, *rchild;
} bsnodetype;

bsnodetype *BinarySortInsert(bsnodetype *t,keytype key,bsnodetype *p);
bsnodetype *BinarySortDelete(bsnodetype *t,bsnodetype *p,bsnodetype *q);
bsnodetype *BinarySortSeach(bsnodetype *t, keytype key, bsnodetype **q);
void InOrder(bsnodetype *t);
void PriorOrder(bsnodetype *t);

main()
{
   int Test[5]={190,12,40,35,9};
   int i, n=5;
   keytype key;
   bsnodetype *t, *p, *q;

   p=(bsnodetype *)malloc(sizeof(bsnodetype));
   p->lchild=NULL;
   p->rchild=NULL;
   p->key=-1;
   t=p;
   for(i=0;i<n;i++)
   {
      p=(bsnodetype *)malloc(sizeof(bsnodetype));
      p->lchild=NULL;
      p->rchild=NULL;
      p->key=Test[i];
      t=BinarySortInsert(t,p->key,p);
   }

   printf("\n\nInOrder is:");
   InOrder(t->rchild);
   printf("\nPriorOrder is:");
   PriorOrder(t->rchild);

   key=190;
   p = BinarySortSeach(t,key,&q);
   q=t;
   t=BinarySortDelete(t,p,q);

   printf("\n\nInOrder is:");
   InOrder(t->rchild);
   printf("\nPriorOrder is:");
   PriorOrder(t->rchild);

}

bsnodetype *BinarySortSeach(bsnodetype *t, keytype key, bsnodetype **q)
/*在二叉排序树t上递归查找关键字为key的记录*/
{
   if(t==NULL) return t;

   /*查找成功*/
   if(t->key == key) return t;

   (*q)=t;
   /*在左子树上继续查找*/
   if(key < t->key) return(BinarySortSeach(t->lchild,key,q));

   /*在右子树上继续查找*/
   else return(BinarySortSeach(t->rchild,key,q));
}

void InOrder(bsnodetype *t)
/*先序遍历打印二叉树*/
{
   if(t==NULL) return ;

   if(t->lchild!=NULL) InOrder(t->lchild);
   printf("%d    ", t->key);
   if(t->rchild!=NULL) InOrder(t->rchild);
}

void PriorOrder(bsnodetype *t)
/*先序遍历打印二叉树*/
{
   if(t==NULL) return ;
   printf("%d    ", t->key);
   if(t->lchild!=NULL) PriorOrder(t->lchild);
   if(t->rchild!=NULL) PriorOrder(t->rchild);
}

bsnodetype *BinarySortDelete(bsnodetype *t,bsnodetype *p,bsnodetype *q)
/**/
{
   bsnodetype *s, *r, *w, *u;
   int flag=0;

   if(p->lchild == NULL && p->rchild == NULL)
   {
      if(p->key <q->key) q->lchild = NULL;
      else q->rchild = NULL;

      if(p==t) flag=1;
      free(p);
      if(flag==1) return q;
      else return t;
   }

   if(p->lchild != NULL && p->rchild == NULL)
   {
      if(q->key < p->key)
      {
	 q->rchild=p->rchild;
	 w=q->rchild;
	 q->lchild=NULL;
      }
      else
      {
	 q->lchild=p->lchild;
	 w=q->lchild;
	 q->rchild=NULL;
      }
      if(p==t) flag=1;
      free(p);
      if(flag==1 ) return w;
      else return t;
   }

   if(p->lchild == NULL && p->rchild != NULL)
   {
      if(q->key < p->key) q->rchild=p->rchild;
      else q->lchild=p->rchild;

      if(p==t) flag=1;
      free(p);
      if(flag==1) return q;
      else return t;
   }

   if(p->lchild != NULL && p->rchild != NULL)
   {
      if(q->key < p->key)
      {
	 u=p->rchild;
	 s=u;
	 while(s->lchild != NULL)
	 {
	    u=s;
	    s=s->lchild;
	 }

	 r=s->rchild;
	 q->rchild=s;

	 s->lchild=p->lchild;
	 if(s==u) s->rchild=NULL;
	 else s->rchild=p->rchild;


	 if(u!=s && r != NULL) u->lchild=r;
	 else if(u!=s && r==NULL) u->lchild = NULL;
      }
      else
      {
	 u=p->rchild;
	 s=u;
	 while(s->lchild != NULL)
	 {
	    u=s;
	    s=s->lchild;
	 }

	 r=s->rchild;
	 q->rchild=s;

	 s->lchild=p->lchild;
	 if(s==u) s->rchild=NULL;
	 else s->rchild=p->rchild;

	 if(u!=s && r != NULL) u->lchild=r;
	 else if(u!=s && r==NULL) u->lchild = NULL;

      }

      if(p==t) flag=1;
      free(p);
      if(flag==1) return q;
      else return t;

   }
}

bsnodetype *BinarySortInsert(bsnodetype *t,keytype key,bsnodetype *p)
/*在以t为根结点的二叉树上查找（不存在时插入）关键字为key结点的*/
/*非递归算法*/
{
   bsnodetype *s;

   if(t==NULL)
   {
      t=p;
      return t;
   }

   s=t;
   while(s != NULL)
   {
      /*查找成功*/
      if(s->key == key) s=NULL;

      /*若key在左子树则继续沿lchild链向下查找*/
      else if(key < s->key )
      {
	 if(s->lchild != NULL) s=s->lchild;

        /*未查找到把该结点插入当前结点的左子树*/
	 else
	 {
	    s->lchild = p;
	    s=NULL;
	 }
      }

      /*若key在右子树则继续沿rchild链向下查找*/
      else
      {
	 if(s->rchild != NULL) s=s->rchild;

        /*未查找到把该结点插入当前结点的右子树*/
	 else
	 {
	    s->rchild = p;
	    s=NULL;
	 }
      }
   }
   return t;
}