CH5_10.C
上传用户:lgb298
上传日期:2013-03-22
资源大小:1025k
文件大小:2k
- #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);
- }