二叉树排序查找

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef int KeyType;
  6. typedef char ElemType[10];
  8. typedef struct tnode
  9. {    
  10.     KeyType key;
  11.     ElemType data;
  12.     struct tnode *lchild,*rchild;
  13. } BSTNode;
  15. BSTNode *BSTSearch(BSTNode *bt,KeyType k)
  16. {
  17.     BSTNode *p=bt;
  18.     while (p!=NULL && p->key!=k)
  19.     {
  20.         if (k<p->key)
  21.             p=p->lchild;  /*沿左子树查找*/
  22.         else
  23.             p=p->rchild;  /*沿右子树查找*/
  24.     }
  25.     return(p);
  26. }
  28. int BSTInsert(BSTNode *&bt,KeyType k)
  29. {
  30.     BSTNode *f,*p=bt;
  31.     while (p!=NULL)
  32.     {
  33.         if (p->key==k)
  34.             return(0);
  35.         f=p;                        /*f指向*p结点的双亲结点*/
  36.         if (p->key>k)
  37.             p=p->lchild;            /*在左子树中查找*/
  38.         else
  39.             p=p->rchild;            /*在右子树中查找*/
  40.     }
  41.     p=(BSTNode *)malloc(sizeof(BSTNode));    /*建立新结点*/
  42.     p->key=k;
  43.     p->lchild=p->rchild=NULL;
  44.     if (bt==NULL)                    /*原树为空时,*p作为根结点插入*/
  45.         bt=p;
  46.     else if (k<f->key)
  47.         f->lchild=p;                /*插入*p作为*f的左孩子*/
  48.     else
  49.         f->rchild=p;                /*插入*p作为*f的右孩子*/
  50.     return(1);
  51. }
  53. void CreateBST(BSTNode *&bt,KeyType str[],int n)
  54. {
  55.     bt=NULL;                       /*初始时bt为空树*/
  56.     int i=0;
  57.     while (i<n) 
  58.     {      
  59.         BSTInsert(bt,str[i]); /*将关键字str[i]插入二叉排序树bt中*/
  60.         i++;
  61.     }
  62. }
  64. void DispBST(BSTNode *bt)
  65. {
  66.     if (bt!=NULL)
  67.     {    printf("%d",bt->key);
  68.         if (bt->lchild!=NULL || bt->rchild!=NULL)
  69.         {    printf("(");
  70.             DispBST(bt->lchild);                /*递归处理左子树*/
  71.             if (bt->rchild!=NULL) printf(",");
  72.             DispBST(bt->rchild);                /*递归处理右子树*/
  73.             printf(")");
  74.         }
  75.     }
  76. }
  78. int BSTDelete(BSTNode *&bt,KeyType k)
  79. {
  80.     BSTNode *p=bt,*f,*r,*f1;
  81.     f=NULL;                        /*p指向待比较的结点,f指向*p的双亲结点*/
  82.     while (p!=NULL && p->key!=k)/*查找值域为x的结点*/
  83.     {    f=p;
  84.             if (p->key>k) 
  85.             p=p->lchild;        /*在左子树中查找*/
  86.             else
  87.             p=p->rchild;        /*在右子树中查找*/
  88.     }
  89.     if (p==NULL)                /*未找到key域为k的结点*/
  90.         return(0);
  91.     else if (p->lchild==NULL)  /**p为被删结点,若它无左子树*/
  92.     {
  93.         if (f==NULL)            /**p是根结点,则用右孩子替换它*/
  94.             bt=p->rchild;
  95.         else if (f->lchild==p)    /**p是双亲结点的左孩子,则用其右孩子替换它*/
  96.         {    f->lchild=p->rchild;
  97.             free(p);
  98.         }
  99.         else if(f->rchild==p)    /**p是双亲结点的右孩子,则用其右孩子替换它*/
  100.         {    f->rchild=p->rchild;
  101.             free(p);
  102.         }
  103.     }
  104.     else if (p->rchild==NULL)    /**p为被删结点,若它无右子树*/
  105.     {
  106.         if (f==NULL)            /**p是根结点,则用左孩子替换它*/
  107.             bt=p->lchild;
  108.         if (f->lchild==p)        /**p是双亲结点的左孩子,则用其左孩子替换它*/
  109.         {    f->lchild=p->lchild;
  110.             free(p);
  111.         }
  112.         else if(f->rchild==p)    /**p是双亲结点的右孩子,则用其左孩子替换它*/
  113.         {    f->rchild=p->lchild;
  114.             free(p);
  115.         }
  116.     }
  117.     else                        /**p为被删结点,若它有左子树和右子树*/
  118.     {
  119.         f1=p;r=p->lchild;        /*查找*p的左子树中的最右下结点*r*/
  120.         while (r->rchild!=NULL)    /**r一定是无右子树的结点,*f1作为r的双亲*/
  121.         {    f1=r;
  122.             r=r->rchild;
  123.         }
  124.         if (f1->lchild==r)        /**r是*f1的左孩子,删除*r*/
  125.             f1->lchild=r->rchild;
  126.         else if (f1->rchild==r)    /**r是*f1的右孩子,删除*r*/
  127.             f1->rchild=r->lchild;
  128.         r->lchild=p->lchild;    /*以下语句是用*r替代*p*/
  129.         r->rchild=p->rchild;    
  130.         if (f==NULL)            /**f为根结点*/
  131.             bt=r;                /*被删结点是根结点*/
  132.         else if (f->lchild==p)    /**p是*f的左孩子*/
  133.             f->lchild=r;
  134.         else                    /**p是*f的右孩子*/
  135.             f->rchild=r;
  136.         free(p);
  137.     }
  138.     return(1);
  139. }
  141. void main()
  142. {
  143.     BSTNode *bt=NULL,*p;
  144.     KeyType a[]={10,6,12,8,3,20,9,25,15},k;
  145.     int n=9;
  146.     CreateBST(bt,a,n);
  147.     printf("BST:");DispBST(bt);printf("\n");
  148.     k=9;
  149.     printf("查找关键字为%d的结点\n",k);
  150.     p=BSTSearch(bt,k);
  151.     if (p!=NULL)
  152.         printf("存在关键字为%d结点\n",k);
  153.     else
  154.         printf("不存在关键字为%d结点\n",k);
  155.     k=7;
  156.     printf("插入关键字为%d的结点\n",k);
  157.     BSTInsert(bt,k);
  158.     printf("BST:");DispBST(bt);printf("\n");
  159.     k=10;
  160.     printf("删除关键字为%d的结点\n",k);
  161.     BSTDelete(bt,k);
  162.     printf("BST:");DispBST(bt);printf("\n");
  163. }