二叉搜索树操作详解

深藏阁楼爱情的钟 2022-05-30 00:50 358阅读 0赞

**二叉搜索树(二叉排序树）是一种搜索结构，它通常具有一下特点：**

*  若他的左子树不为空，则**左子树上的所有节点的值都小于根节点的值**
 *  若它的右子树不为空，则**右子树上所有节点的值都大于根节点的值**
 *  **它的左右子树也分别为二叉搜索树**
 *  **中序遍历的结果是升序序列**  
    ![二叉搜索树][70]  
    **下面，我讲一下二叉搜索树的基本操作方法**
    
     *  查找  
        若根节点不为空：  
        如果根节点key == 目标key,返回true  
        如果根节点key > 目标key，在左子树中查找  
        如果根节点key < 目标key，在右子树中查找  
        否则返回false
     *  插入  
        1.如果树为空树，则直接插入  
        2.树不为空，则按照二叉搜索树的性质查找插入的位置，找到后插入  
        ![Insert][]
     *  删除  
        **首先查找元素是否在二叉搜索树中，如果不存在，则返回**，否则要分为下面四种情况来讨论删除的位置：  
        **1>要删除的节点无孩子节点**  
        **2>要删除的节点只有左孩子节点**  
        **3>要删除的节点只有右孩子节点**  
        **4>要删除的节点有左和右孩子节点**  
        根据上面的几种情况，相应的删除方法如下（具体的实现附在代码中详细讲解）：  
        **1>直接删除该节点**  
        **2>删除该节点且考虑被删除节点的双亲节点的指向，避免二叉搜索树断掉**  
        **3>用右子树中的最小数据填补到目标位置，然后分以上两种情况讨论，删掉右子树中找出的装有最小数据的这个节点**  
        **Code:**

//定义数据类型，方便以后更改
    typedef int DataType;
    
    //封装一个二叉搜索树的节点结构
    typedef struct BSTree
    {
        struct BSTree *_left;
        struct BSTree *_right;
        DataType _data;
    }Node,*PNode;
    //初始化根节点
    void InitBSTree(PNode *root)
    {
        assert(root);
        *root = NULL;
    }
    
    //申请新节点
    PNode BuyNewNode(DataType data)
    {
        PNode new_node = (PNode)malloc(sizeof(Node));
        new_node->_left = NULL;
        new_node->_right = NULL;
        new_node->_data = data;
        return new_node;
    }
    //向树中插入新数据
    int InsertBTTree(PNode *root, DataType data)
    {
        assert(root);
        PNode pCur = *root;
        PNode parent = NULL;
        if (pCur == NULL)//如果根节点为空，则将新节点直接插入到根节点位置
        {
            *root= BuyNewNode(data);
            return 1;
        }
        while (pCur)//pCur只要不为空，说明还没有找到目标位置
        {
            //如果目标数据比当前节点数据大，则到右子树中查找
            if (data > pCur->_data)
            {
                parent = pCur;
                pCur = pCur->_right;
            }
            //如果目标数据比当前节点数据小，则到左子树中查找
            else if (data < pCur->_data)
            {
                parent = pCur;
                pCur = pCur->_left;
            }
            else
                return 0;//如果在树中找到了相同的数据说明不能插入该数据
        }
        //判断当前位置是其双亲节点的左子树还是右子树（这步决定树是否能连起来）
        if (data > parent->_data)
        {
            pCur = BuyNewNode(data);
            parent->_right = pCur;
        }
        else
        {
            pCur = BuyNewNode(data);
            parent->_left = pCur;
        }
        return 1;
    }
    PNode FindBSTree(PNode root,DataType data)
    {
        assert(root);
        PNode pCur = root;
        if (pCur->_data == data)//如果目标数据为根节点中的数据，则直接返回
            return pCur;
        while (pCur)//只要不为空，就说明没有走完整棵树
        {
            //如果当前数据比目标数据小，则在其右子树中查找
            if (pCur->_data < data)
            {
                pCur = pCur->_right;
            }
            //如果当前数据比目标数据大，则在其左子树中查找
            else if (pCur->_data > data)
            {
                pCur = pCur->_left;
            }
            else
            {
                return pCur;
            }
        }
        return NULL;//出了循环还没有返回说明没有找到
    }
    
    int DeleteBSTree(PNode *root, DataType data)
    {
        assert(root);
        PNode pCur = *root;
        if (NULL == pCur)//如果树为空，则删除失败
        {
            return 0;
        }
        PNode pParent = NULL;
        //待删除节点，定义这个变量是处理待删除数据为根节点的情况
        PNode pDel = *root;
        while (pCur)//先找到要删除的目标节点
        {
            pParent = pCur;
            if (pCur->_data == data)
            {
                break;
            }
            else if (pCur->_data > data)
            {
                pCur = pCur->_left;
            }
            else
            {
                pCur = pCur->_right;
            }
        }
        //这里要判断一下出循环的前提
        if (!pCur)//如果pCur为空，说明没有找到目标节点，直接返回失败信号
        {
            return 0;
        }
        //然后分情况来讨论目标节点的位置关系
        if (pCur->_right == NULL)
        {
            pDel = pCur;//更新待删除节点信息
            if (pDel == *root)//如果目标节点是根节点，则将根节点指向左子树
            {
              //令根节点指向其左孩子，一会儿直接删除上面用pDel标记的位置即可
                *root = pCur->_left;
            }
             //如果目标节点为其双亲结点的左孩子
            else if (pParent->_left == pCur)
            {
                pParent->_left = pCur->_left;
            }
            else if (pParent->_right == pCur)
            {
                pParent->_right = pCur->_left;
            }
        }
        else if (pCur->_left == NULL)//和上面同理
        {
            pDel = pCur;
            if (pCur == *root)
            {
                *root = pCur->_right;
            }
            else if (pParent->_left == pCur)
            {
                pParent->_left = pCur->_right;
            }
            else if (pParent->_right == pCur)
            {
                pParent->_right = pCur->_right;
            }
        }
        else
        {
            pParent = pCur;//更新双亲结点信息
            pDel = pCur->_right;
            while (pDel->_left)//直接找到目标节点的右子树的最小节点
            {
                pParent = pDel;
                pDel = pDel->_left;
            }
            //交换数据,将右子树中找到的数据（pDel)赋给目标数据
            pCur->_data = pDel->_data;
            //然后分情况讨论右子树中找到的节点的位置信息
            if (pParent->_left == pDel)
            {
                /*由于上一步找到的节点已经是右子树中最左边节点，所以找到 的节点不再可能有左子树,所以是右子树*/
                pParent->_left = pDel->_right;
            }
            else
            {
                pParent->_right = pDel->_right;
            }
        }
    
        free(pDel);
        return 1;
    }

> PS：老铁(- . -)，如果有什么问题可以在评论区指出

[70]: /images/20220530/74702214d4fe414ab4019a48465ddd5c.png
[Insert]: /images/20220530/dfc878f65ecb40d68448bf2bba3d18aa.png