1.c

这是我做数据结构课程设计里面的一个设计程序

# define NULL 0
# define m 20
typedef struct node {int num; char name[m];int age;
                     struct node *lchild,*rchild;}BSTNode; 

BSTNode *searchnode(BSTNode *r,int k)        /*二叉排序树的查找*/
{ /*在以r为根的二叉排序树中查找学号为k的结点*/
  BSTNode *p;
  if(r!=NULL)
   { p=r;
     while(p!=NULL)
      { if(p->num==k) return(p);
        else if(k<p->num) p=p->lchild;
             else p=p->rchild;
      }
    }
  return(NULL);
}

BSTNode *insertnode(BSTNode *r,int k)              /*二叉排序树的插入*/
{ /*在以r为根的二叉排序树中插入学号为k的结点*/
  BSTNode *p,*q,*s;
  char a[m];
  s=(BSTNode *)malloc(sizeof(BSTNode));
  s->num=k;
  printf("请输入姓名:");
  scanf("%s",a);
  strcpy(s->name,a);
  printf("请输入年龄:");
  scanf("%d",&s->age);
  s->lchild=NULL;
  s->rchild=NULL;
  q=NULL;
  if(r==NULL){r=s;return(r);}
  p=r;
  while(p!=NULL)
  { q=p;
    if(k<p->num) p=p->lchild;
    else p=p->rchild;
  }
  if(k<q->num) q->lchild=s;
  else q->rchild=s;
  return(r);
}

BSTNode *deletenode(BSTNode *r,int k)           /*二叉排序树的删除*/
{ BSTNode *q,*s,*parent=NULL,*p=r;
  while(p)
  { if(p->num==k) break;
    parent=p;
    p=k<p->num?p->lchild:p->rchild;
  }
  q=p;
  if(q->lchild&&q->rchild)
  { parent=q;
    p=q->lchild;
    while(p->rchild)
    { parent=p;p=p->rchild; }
  }
  s=p->lchild?p->lchild:p->rchild;
  if(parent==NULL) r=s;
  else
   { if(p==parent->lchild)
      parent->lchild=s;
     else parent->rchild=s;
     if(p!=q)
      q->num=p->num;
   }
  free(p);
  return(r);
}

void disbstnode(BSTNode *r)                /*输出二叉排序树的信息*/
{ int i=0;
  BSTNode *p,*s[20];
  p=r;
  do{ while(p!=NULL)
       {s[i++]=p;p=p->lchild;}
      if(i>0)
       {p=s[--i];
        printf("%d\t%-18s%d\n",p->num,p->name,p->age);
        p=p->rchild;}
     }while(i>0||p!=NULL);
}

main()
{ BSTNode *r,*t;
  int k;
  while(k!=0)
  { printf("\n请输入学号(输入0标志结束):");
    scanf("%d",&k); 
    t=searchnode(r,k);
    if(t!=NULL) { r=deletenode(r,k);
                  printf("\n学号\t姓名\t\t年龄\n");
                  disbstnode(r);
                }
    else { r=insertnode(r,k);
           printf("\n学号\t姓名\t\t年龄\n");
           disbstnode(r);
         }
   }
}