• 二叉树排序查找

    二叉树排序查找

    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. }