hao 05.c

来自「二叉排序树的建立,查找,删除,插入等功能. 是数据结构的设计性实验的代码,使用」· C语言 代码 · 共 210 行

#include "stdio.h"
#include "conio.h"

typedef struct BiTree
{ int key;
  struct BiTree *lchild,*rchild;
}BiTree;
BiTree *f=NULL;

BiTree *BSTSearch(BiTree *r,int k)/*查找节点*/
{
    f=r;
    while(r!=NULL)
        { if(r->key==k)
            return r;
          else
            { f=r;r=k<r->key? r->lchild:r->rchild;}
        }       /*这里循环结束后，r就是要找的p结点，f就是p的双亲结点*/
    return r;
}

BiTree *BSTInsert(BiTree *r,int x)  /*插入节点*/
{
    BiTree *p,*q,*s;
    if(r==NULL)
        { r=(BiTree *)malloc(sizeof(BiTree));
          r->key=x;
          r->rchild=r->lchild=NULL;
        }
    else
        { p=r;
          while(p!=NULL&&p->key!=x)
            { q=p;             /*如果x结点已存在,q为p的双亲如果x结点不存在
                                 q为x的插入点*/
              p=x<p->key? p->lchild:p->rchild;
            }
          if(x==p->key)
            printf("find %d node!",p->key);
          else
            { s=(BiTree *)malloc(sizeof(BiTree));
              s->key=x;
              s->rchild=s->lchild=NULL;
              if(x<q->key)
                q->lchild=s;
              else
                q->rchild=s;
            }
        }
    return r;
}


BiTree *BSTdel(BiTree *r,BiTree *p,BiTree *f)/*删除节点*/
{
    BiTree *q,*s;
    if(p->lchild==NULL)
        { if(p==r)
            r=r->rchild;
          else if(p==f->rchild)
            f->rchild=p->rchild;
          else
            f->lchild=p->rchild;
        }
    else
        { if(p->rchild==NULL)
            { if(p==r)
                r=r->lchild;
              else if(p==f->rchild)
                f->rchild=p->lchild;
              else
                f->lchild=p->lchild;
            }
          else
            { q=p;
              s=q->lchild;      /*这里q为s的双亲，s为p的替代结点*/
              while(s->rchild!=NULL)
                { q=s;
                  s=s->rchild;
                }
              s->rchild=p->rchild;
              if(p!=q)
                { q->rchild=s->lchild;
                  s->lchild=p->lchild;
                }
              if(p==r)
                r=s;
              else if(p==f->rchild)
                f->rchild=s;
              else
                f->lchild=s;
            }
       }
    free(p);
    return r;
}

void Inorder(BiTree *r)
{
    if(r!=NULL)
        { Inorder(r->lchild);
          printf("%-5d",r->key);
          Inorder(r->rchild);
        }
}


void main()
{int a[1000],nChioce;
 BiTree *r=NULL,*p;
    int k;




while(1)
{printf("Welcome \n");
 printf("/**************************************/\n");
 printf("/**1.Init a new BiTrtee              **/\n");
 printf("/**2.Insert a new node               **/\n");
 printf("/**3.Lookup one node                 **/\n");
 printf("/**4.Delete one node                 **/\n");
 printf("/**5.Inorder travesal                **/\n");
 printf("/**6.exit the system                 **/\n");
 printf("/**************************************/\n");

 printf("input the choose number:1 to 6\n ");
 scanf("%d",&nChioce);

 switch(nChioce)
 {case 1:
   printf("input the number (input -1 end the input):\n");
    scanf("%d",&k);
    while(k!=-1)
        { r=BSTInsert(r,k);
          scanf("%d",&k);
        }      
  printf("Press any key to the RequireMen...\n");
  getch();
  clrscr();
  break;
   case 2:
  printf("input the number you want to insert: \n");
  scanf("%d",&k);
   r=BSTInsert(r,k);
  printf("Press any key to the RequireMen...\n");
  getch();
  clrscr();
  break;
  case 3:
  printf("\nsearch k=");
    scanf("%d",&k);
    p=BSTSearch(r,k);       /*查找键值为k结点p,f为其双亲*/
    if(p)
        { printf("find k=%d!",p->key);
          if(p==r)
            printf("no parent\n");
          else
            printf(",parent=%d\n",f->key);

               }
    else
        printf("no find!");
  printf("Press any key to the RequireMen...\n");
  getch();
  clrscr
  ();
  break;
  case 4:
  printf("input the number you want to delete: \n");
  scanf("%d",&k);
  p=BSTSearch(r,k);
  if(p)
        { printf("find k=%d!",p->key);
          if(p==r)
            printf("no parent\n");
          else
          printf(",parent=%d\n",f->key);
          r=BSTdel(r,p,f);
          printf("after deleted:");
          Inorder(r);
          printf("\nroot is=%d\n",r->key);
        }
         else
        printf("no find!\n");

  printf("Press any key to the RequireMen...\n");
  getch();
  clrscr();
  break;
  case 5:
    Inorder(r);
    printf("\nroot is=%d",r->key);
     printf("\n");
     printf("Press any key to the RequireMen...\n");
     getch();
     clrscr();
     break;

  case 6:
  printf("think you use the system\n");
  printf("bye bye\n");
  getch();
  clrscr();
   exit(0);
   
 }
}
getch();
}