美文网首页
二叉排序树

二叉排序树

作者: ChenL | 来源:发表于2020-05-17 13:56 被阅读0次

1、二叉树的二叉链表结点结构定义

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

2、二叉排序树--查找

递归查找二叉排序树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);  /*  在右子树中继续查找 */
}

3、二叉排序树-插入

当二叉排序树T中不存在关键字等于key的数据元素时,插入key并返回TRUE,否则返回FALSE

Status InsertBST(BiTree *T, int key) {
    BiTree p,s;
    //1.查找插入的值是否存在二叉树中;查找失败则->
    if (!SearchBST(*T, key, NULL, &p)) {
        //2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        //3.
        if (!p) {
            //如果p为空,则将s作为二叉树新的根结点;
            *T = s;
        }else if(key < p->data){
            //如果key<p->data,则将s插入为左孩子;
            p->lchild = s;
        }else
            //如果key>p->data,则将s插入为右孩子;
            p->rchild = s;
        
        return  TRUE;
    }
    return FALSE;
}

4、从二叉排序树中删除结点p,并重接它的左或者右子树;

Status Delete(BiTree *p){
       BiTree temp,s;
      if((*p)->rchild == NULL){
       
        //情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
        //①将结点p临时存储到temp中;
        temp = *p;
        //②将p指向到p的左子树上;
        *p = (*p)->lchild;
        //③释放需要删除的temp结点;
        free(temp);
        
    }else if((*p)->lchild == NULL){
        //情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
        //①将结点p存储到temp中;
        temp = *p;
        //②将p指向到p的右子树上;
        *p = (*p)->rchild;
        //③释放需要删除的temp结点
        free(temp);
    }else{
        
        //情况③:删除的当前结点的左右子树均不为空;
       
        //①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
        temp = *p;
        s = (*p)->lchild;
      
        //②将s指针,向右到尽头(目的是找到待删结点的前驱)
        //-在待删除的结点的左子树中,从右边找到直接前驱
        //-使用`temp`保存好直接前驱的双亲结点
        while (s->rchild) {
            temp = s;
            s = s->rchild;
        }
        
        //③将要删除的结点p数据赋值成s->data;
        (*p)->data = s->data;
        
        //④重连子树
        //-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
        //-如果temp 等于p,则将S->lchild 赋值给temp->lchild
        if(temp != *p)
            temp->rchild = s->lchild;
        else
            temp->lchild = s->lchild;
        
        //⑤删除s指向的结点; free(s)
        free(s);
    }
   return  TRUE;

5、查找结点,并将其在二叉排序中删除;
若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点

Status DeleteBST(BiTree *T,int key)
{
   //不存在关键字等于key的数据元素
   if(!*T)
       return FALSE;
   else
   {
       //找到关键字等于key的数据元素
       if (key==(*T)->data)
           return Delete(T);
       else if (key<(*T)->data)
           //关键字key小于当前结点,则缩小查找范围到它的左子树;
           return DeleteBST(&(*T)->lchild,key);
       else
           //关键字key大于当前结点,则缩小查找范围到它的右子树;
           return DeleteBST(&(*T)->rchild,key);
   }
}

相关文章

  • 详解Java二叉排序树

    姓名: 李小娜 [嵌牛导读] :这篇文章主要介绍了Java二叉排序树,包括二叉排序树的定义、二叉排序树的性质、二叉...

  • Java数据结构:二叉排序树(BST)

    一、基本介绍 二叉排序树 BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一...

  • 2018-06-19/20 机试准备09

    数据结构 四、二叉排序树 对二叉排序树进行中序遍历 结果必然是一个递增序列 所以通过建立二叉排序树可以对无序序列进...

  • 二叉搜索树(BST)

    构造一棵二叉排序树的目的,其实并不是为了排序,而是为了提高查找的效率。 那么什么是二叉排序树呢?二叉排序树具有以下...

  • Binary Search Tree

    如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为 ,其查找效率为 ,近似于折半查找。如果二叉排序树完全不平衡...

  • 红黑树

    二叉排序树 非空二叉排序树具有如下特点: 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点...

  • 数据结构之二叉排序树

    二叉排序数 1.二叉排序树介绍 二叉排序树:BST: (Binary Sort(Search) Tree), 对于...

  • 数据结构学习第四弹 二叉排序树

    二叉排序树又称为二叉搜索树或二叉查找树,这是一种插入、删除和检索记录效率都很高的树结构 二叉排序树概念 二叉排序树...

  • 数据结构与算法——基础篇(五)

    二叉排序树——BST——Binary Sort(Search) Tree 二叉排序树的出现是为了解决数组的查询快,...

  • 看图说话之平衡二叉排序树

    本文在看图说话之二叉排序树的基础上介绍了平衡二叉排序树,结构性较好的二叉排序树其插入和删除操作的时间复杂度接近Lo...

网友评论

      本文标题:二叉排序树

      本文链接:https://www.haomeiwen.com/subject/hzbtohtx.html