CH5_10.C
上传用户:lgb298
上传日期:2013-03-22
资源大小:1025k
文件大小:2k
源码类别:

软件工程

开发平台:

C/C++

  1. #include <stdio.h>
  2. #include <alloc.h>
  3. typedef struct node
  4. {  int data;
  5.    struct node *lchild,*rchild;
  6. }JD;
  7. JD *insertbst(JD *r,int x)
  8. {  JD *p,*q,*s;
  9.    s=(JD *)malloc(sizeof(JD));
  10.    s->data=x;  s->lchild=s->rchild=NULL;
  11.    q=NULL;
  12.    if(r==NULL) {  r=s; return(r);}
  13.    p=r;
  14.    while(p!=NULL)
  15.    {  q=p;
  16.       if(x<p->data)
  17.  p=p->lchild;
  18.       else
  19.  p=p->rchild;
  20.    }
  21.    if(x<q->data)
  22.       q->lchild=s;
  23.    else
  24.       q->rchild=s;
  25.    return(r);
  26. }
  27. void inorder(JD *bt)
  28. {  if(bt!=NULL)
  29.    {  inorder(bt->lchild);
  30.       printf("%d  ",bt->data);
  31.       inorder(bt->rchild);
  32.    }
  33. }
  34. JD *delnode(JD *r,JD *p,JD *f)
  35. {  JD *q,*s;
  36.    int flag=0;
  37.    if(p->lchild==NULL)  s=p->rchild;
  38.    else if(p->rchild==NULL)  s=p->lchild;
  39.    else{  q=p;
  40.   s=p->lchild;
  41.   while(s->rchild!=NULL)
  42.   {  q=s;
  43.      s=s->rchild;
  44.   }
  45.   if(q==p)  q->lchild=s->lchild;
  46.   else      q->rchild=s->lchild;
  47.   p->data=s->data;
  48.   free(s);
  49.   flag=1;
  50.        }
  51.    if(flag==0)
  52.    {  if(f==NULL)  r=s;
  53.       else if(f->lchild==p)  f->lchild=s;
  54.       else   f->rchild=s;
  55.       free(p);
  56.    }
  57.    return(r);
  58. }
  59. void main()
  60. {  static int key[]={80,50,60,55,53,70,120,110,150};
  61.    JD *head=NULL,*p,*f;
  62.    int i,n=9;
  63.    for(i=0;i<n;i++)
  64.      head=insertbst(head,key[i]);
  65.    printf("n");
  66.    inorder(head);
  67.    p=head->lchild;
  68.    f=head;
  69.    head=delnode(head,p,f);
  70.    printf("n");
  71.    inorder(head);
  72.    p=head->lchild;
  73.    f=head;
  74.    head=delnode(head,p,f);
  75.    printf("n");
  76.    inorder(head);
  77.    p=head;
  78.    f=NULL;
  79.    head=delnode(head,p,f);
  80.    printf("n");
  81.    inorder(head);
  82. }