大话数据结构-8.6 二叉排序树 - 高飞网

8.6 二叉排序树

2017-01-05 00:29:19.0

    对无序的顺序存储表查找:插入操作就是将记录放在表的末端,表记录数加一;删除操作可以是删除后,后面的记录往前移,或删除的元素与最后一个元素互换(反正没有顺序),表记录数减一;应该说插入和删除操作对顺序存储结构来说,效率是可以接受的,但由于它无序,造成的顺序查找,效率很低,为O(n)。

    对有序且顺序存储的线性表:查找可以使用折半、插值、斐波那契等查找算法来实现,但因为有序,因此在插入和删除操作时,就要耗时大量时间来排序。

    在查找时同时更新数据,这样的查找,叫做动态查找表,动态查找不但要求查询效率,也要求插入和删除数据效率。

    现假设有{62,88,58}数列,第一次查找62,没有,则插入;查找88,没有,则插入,由于88比62大,因此放在62的右边;查找58,没有则插入,由于58比62还少,如果使用顺序结构,则需要62和88往后移动。但如果使用的是二叉树,则只需要将62作为根结点,88比62大,作为62的右结点,58比62小,作为62的左结点。如下图示:

    假设现在需要集合{62,88,58,47,35,73,51,99,37,93}做查找,在打算创建此集合时就考虑用二叉树结构,而且排好序的二叉树来创建。如下图:

    上面的二叉树,当对它进行中序遍历时,就可以得到一个有序的序列{35,37,47,51,62,73,88,93,99},通常称之为二叉排序树。

    二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树。

  1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
  2. 若它的右子树不空,则右子树上所有结点的值均小于它的根结点的值。
  3. 它的左、右子树也分别为二叉排序树。

8.6.1 二叉排序树查找操作

    如果想查找93,首先,判断62是否为叶子结点,不是,则继续,判断62是否等于93,否,所以判断62与93的大小关系,62小于93,因此,继续查找62的右子树,即88结点,依次进行,最后找到93,并把获取93的位置。


typedef struct BiTNode              /*结点结构*/
{
    int data;                       /*结点数据*/
    struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,*BiTree;

/*递归查找二叉排序树T中是否存在key*/
/*指针f指向T的双亲,其初始调用值为NULL*/
/*若查找成功,则指针p指向该数据元素的结点,并返回TRUE*/
/*否则指针p指向查找路径上访问的最后一个结点并返回FALSE*/
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
    if(!T)
    {
        *p =f ;
        return FALSE;
    }
    else if(key==T->data)
    {
        *p =T;
        return TRUE;
    }
    else if(key<T->data)
    {/*在左子树继续查找*/
        return SearchBST(T->lchild,key,T,p);
    }
    else
    {/*在右子树继续查找*/
        return SearchBST(T->rchild,key,T,p)
    }
}

构建二叉树:


{
    int i;
    int a[10] = {62,88,58,47,35,73,51,99,37,93};
    BiTree T = NULL;
    for(i=0;i<10;i++)
    {           
        InsertBST(&T,a[i])  
    }                   
}


8.6.2 二叉排序树的插入操作

    先判断该值在二叉排序树中是否存在,调用的是上面的查找操作方法,如果存在返回FALSE,否则将新结点(如95)插入到93的右结点上。


/*当二叉排序树T中不存在关键字等于key的数据元素日韩时*/
/*插入key并返回TRUE,否则返回FALSE*/
Status InsertBST(BiTree *T,int key)
{
    BiTree p,s;
    if(SearchBST(*T,key,NULL,&p))
    {/*查找失败*/
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!p)
        {
            *T = s; /*插入s为新的根结点*/
        }
        else if(k<p->data)
        {
            p->lchild=s;    /*插入s为左孩子*/
        }
        else
        {
            p->rchild=s;    /*插入s为右孩子*/
        }
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}


8.6.3 二叉排序树的删除操作

    删除结点的三种情况:

  1. 叶子结点
  2. 仅有左或右子树的结点;
  3. 左右子树都有的结点(找到该结点的直接前驱或后继代替它)
/* 若二叉排序树T中存在关键字等于key的数据元素,则删除数据元素结点, */
/* 并返回TRUE,否则返回FALSE */
Status DeleteBST(BiTree *T,int key)
{
    if(!*T)         /*不存在关键字等于key的数据元素*/
    {
        return FALSE;
    } 
    else
    {
        if(key==(*T)->data) /*找到关键字等于key的数据元素*/
        {
            return Delete(T);
        }
        else if(key<(*T)->data)
        {
            return DeleteBST(&(*T)->lchild,key);
        }
        else
        {
            return DeleteBST(&(*T)->rchild,key);
        }
    }
}
/*从二叉排序树中删除结点p,并重接它的左或右子树*/
Status Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL)
    {/*右子树空则只需重接它的左子树*/
        q=*p;*p=(*p)->lchild;free(q);
    }
    else if((*p)->lchild==NULL)
    {/*只需重接它的右子树*/
        q=*p;*p=(*p)->rchild;free(q);
    }
    else
    {
        q=*p;s=(*p)->lchild;
        while(s->rchild)
        {/*转左,然后向右到尽头(找待删结点的前驱)*/
            q=s;s=s->rchild;
        }
        (*p)->data=s->data; /*s指向被删结点的直接前驱*/
        if(p!=*q)
        {
            p->rchild=s->lchild;/*重接q的右子树*/
        }
        else
        {
            q->lchild=s->lchild;/*重接q的左子树*/
        }
        free(s);
    }
    return TRUE;
}


8.6.4 二叉排序树总结

    总之,二叉排序树是以链接的方式存储,保持了链接存储结构在执行插入或删除操作时不用移动元素的优点,只要找到合适的插入和删除位置后,仅需要修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找,走的就是从根结点到要查找的结点的路径,其比较次数等于给定值的结点在二叉排序树的层数。最少为一次,最多为树的深度。也就是说,二叉排序树的查找性能取决于二叉排序树的形状。但二叉排序树的形状是不确定的。

    如上图所示,左图是之前讨论的一种,而右图比较极端,是因为数据本身是有序的,因此造成的二叉树是一棵右斜树,像右斜树这样的情况,查找性能最差,是O(n),而左图相对来说比较平衡,但也不是非常平衡,可以认为于完全二叉树越相近则越平衡。

    因此,希望对一个集合按二叉排序树查找,最好是把它构建成一棵二平衡二叉排序树。