ch5_10.c

数据结构（ C语言版） 讲义daima数据结构（ C语言版） 讲义daima

#include <stdio.h>
#include <alloc.h>
typedef struct node
{  int data;
   struct node *lchild,*rchild;
}JD;

JD *insertbst(JD *r,int x)
{  JD *p,*q,*s;
   s=(JD *)malloc(sizeof(JD));
   s->data=x;  s->lchild=s->rchild=NULL;
   q=NULL;
   if(r==NULL) {  r=s; return(r);}
   p=r;
   while(p!=NULL)
   {  q=p;
      if(x<p->data)
	 p=p->lchild;
      else
	 p=p->rchild;
   }
   if(x<q->data)
      q->lchild=s;
   else
      q->rchild=s;
   return(r);
}

void inorder(JD *bt)
{  if(bt!=NULL)
   {  inorder(bt->lchild);
      printf("%d  ",bt->data);
      inorder(bt->rchild);
   }
}

JD *delnode(JD *r,JD *p,JD *f)
{  JD *q,*s;
   int flag=0;
   if(p->lchild==NULL)  s=p->rchild;
   else if(p->rchild==NULL)  s=p->lchild;
   else{  q=p;
	  s=p->lchild;
	  while(s->rchild!=NULL)
	  {  q=s;
	     s=s->rchild;
	  }
	  if(q==p)  q->lchild=s->lchild;
	  else      q->rchild=s->lchild;
	  p->data=s->data;
	  free(s);
	  flag=1;
       }
   if(flag==0)
   {  if(f==NULL)  r=s;
      else if(f->lchild==p)  f->lchild=s;
      else   f->rchild=s;
      free(p);
   }
   return(r);
}

void main()
{  static int key[]={80,50,60,55,53,70,120,110,150};
   JD *head=NULL,*p,*f;
   int i,n=9;
   for(i=0;i<n;i++)
     head=insertbst(head,key[i]);
   printf("\n");
   inorder(head);

   p=head->lchild;
   f=head;
   head=delnode(head,p,f);
   printf("\n");
   inorder(head);

   p=head->lchild;
   f=head;
   head=delnode(head,p,f);
   printf("\n");
   inorder(head);

   p=head;
   f=NULL;
   head=delnode(head,p,f);
   printf("\n");
   inorder(head);
}