二叉搜索树（递归&非递归）

完整源代码在此

1、二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树。

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有的节点的值都大于根节点的值
3. 它的左右子树也分为二叉搜索树
   
   此二叉树的中序遍历结果为： 0，1，2，3，4，5，6，7，8，9；

2、二叉搜索树的基本操作

1.初始化二叉搜索树

• 令二叉树的根节点指向NUL

void InitBSTree(BSTNode** pRoot)
{
    assert(pRoot);
    *pRoot = NULL;
}

2. 插入

非递归

• 如果树为空，直接插入
• 如果树不为空，根据二叉搜索树的性质，我们想让data和根节点比较，如果大于根节点，则在和右子树比较，如果小于，则和左子树比较，直到找到插入位置，将新节点插入
• 如果该元素在树中已存在，则直接返回

void InsertBSTree(BSTNode** pRoot, DataType data)
{
    BSTNode * pCur = NULL;
    BSTNode * pParent = NULL;

    //如果根结点为空，直接插入
    if (NULL == (*pRoot))
        *pRoot = BuyBSTNode(data);

    pCur = *pRoot;
    while (pCur)
    {
        if (pCur->_data > data)
        {
            pParent = pCur;
            pCur = pCur->pLeft;
        }
        else if (pCur->_data < data)
        {
            pParent = pCur;
            pCur = pCur->pRight;
        }
        //如果有结点和data相等，直接返回 
        else
        {
            return;
        }
    }

    pCur = BuyBSTNode(data);

    //如果双亲的值大于它，则让双亲的左指针域指向它
    if (pParent->_data > pCur->_data)
    {
        pParent->pLeft = pCur;
    }
    else
    {
        pParent->pRight = pCur;
    }

}

递归

• 如果树为空，直接插入
• 比较根节点的值和data的大小，如果data大，继续比较根节点和它的右孩子的大小，反之，比较左孩子。如果找到插入位置，插入新结点

int  InseretBSTreeD(BSTNode** pRoot, DataType data)
{
    //如果根结点为空，直接插入
    if (NULL == (*pRoot))
    {
        *pRoot = BuyBSTNode(data);
        return 1;
    }

    if ((*pRoot)->_data > data)
        return InseretBSTreeD(&(*pRoot)->pLeft, data);
    else if ((*pRoot)->_data < data)
        return InseretBSTreeD(&(*pRoot)->pRight, data);
    else
        return 0;
}

3、删除值为data的结点

• 首先判断data是否在二叉搜索树中，如果不存在，则返回，

• 如果存在，则要删除的结点有以三种情况：

  • 要删除的结点无孩子,要删除的结点只有左孩子

    删除该结点，并且让被删除节点的双亲指向被删除节点的左孩子节点

  • 要删除的结点只有右孩子

    删除该节点，并且让被删除节点的双亲指向被删除节点的右孩子节点

  • 要删除的孩子有左右孩子

    在它的右子树找到最左边的节点，即最小值的节点，然后用它的值补到被删除节点中，然后删除这个节点，并且让找到的这个节点的双亲指向这个节点的右孩子节点

非递归

void DeleteBSTree(BSTNode** pRoot, DataType data)
{
    BSTNode *pCur = NULL;
    BSTNode *pParent = NULL;
    BSTNode *pDel = NULL;

    assert(pRoot);
    if (NULL == (*pRoot))
        return;

    pCur = *pRoot;

    while (pCur)
    {
        if (pCur->_data > data)
        {
            pParent = pCur;
            pCur = pCur->pLeft;
        }
        else if (pCur->_data < data)
        {
            pParent = pCur;
            pCur = pCur->pRight;
        }
        else
        {
            break;
        }
    }

    if (pCur)
    {
        pDel = pCur;
        //如果只有左孩子或者无左孩子
        if (NULL == pCur->pRight)
        {
            //如果是根结点的左孩子
            if ((*pRoot)->pLeft == pCur)
                (*pRoot)->pLeft = pCur->pLeft;
            else
            {
                if (pParent->pLeft == pCur)
                    pParent->pLeft = pCur->pLeft;
                else
                    pParent->pRight = pCur->pLeft;
            }
        }
        //如果只有右孩子
        else if (pCur->pRight)
        {
            if ((*pRoot)->pRight == pCur)
                (*pRoot)->pRight = pCur->pRight;
            else
            {
                if (pParent->pRight == pCur)
                    pParent->pRight = pCur->pRight;
                else
                    pParent->pLeft = pCur->pRight;
            }
        }
        //如果有两个孩子
        else
        {
            pParent = pCur;
            pDel = pCur->pRight;

            //查找右子树里最左边的结点
            while (pDel->pLeft)
            {
                pParent = pDel;
                pDel = pDel->pLeft;
            }
            //找到了，替换
            pCur->_data = pDel->_data;

            if (pParent->pLeft == pDel)
                pParent->pLeft = pDel->pRight;
            else
                pParent->pRight = pDel->pRight;
        }
        free(pDel);
        pDel = NULL;
    }

}

递归

void DeleteBSTreeD(BSTNode** pRoot, DataType data)
{
    BSTNode *pDel = NULL;
    assert(pRoot);
    if (NULL == (*pRoot))
        return;
    else if ((*pRoot)->_data > data)
        DeleteBSTreeD(&(*pRoot)->pLeft, data);
    else if ((*pRoot)->_data < data)
        DeleteBSTreeD(&(*pRoot)->pRight, data);
    else
    {
        pDel = *pRoot;
        //只有左孩子或者无孩子
        if (NULL == (*pRoot)->pRight)
        {
            (*pRoot) = (*pRoot)->pLeft;
            free(pDel);
            pDel = NULL;
        }
        //只有右孩子
        else if ((*pRoot)->pLeft)
        {
            (*pRoot) = (*pRoot)->pRight;
            free(pDel);
            pDel = NULL;
        }
        else
        {
            pDel = (*pRoot)->pRight;
            while (pDel->pLeft)
            {
                pDel = pDel->pLeft;
            }
            (*pRoot)->_data = pDel->_data;
            DeleteBSTreeD(&pDel->pRight, data);
        }
    }
}

在二叉搜索树中查找值为data的结点

• 如果树为空，返回
• 如果根节点的值等于data，返回
• 如果根节点的值大于data，在其左子树查找
• 如果根节点的值小于data，在其右子树查找
• 没找到，返回NULL

非递归

BSTNode* FindBSTree(BSTNode* pRoot, DataType data)
{
    BSTNode * pCur = NULL;
    if (NULL == pRoot)
        return NULL;

    pCur = pRoot;
    while (pCur)
    {
        if (pCur->_data > data)
        {
            pCur = pCur->pLeft;
        }
        else if (pCur->_data < data)
        {
            pCur = pCur->pRight;
        }
        else if (pCur->_data == data)
        {
            return pCur;
        }
    }

    return NULL;

}

递归

BSTNode* FindBSTreeD(BSTNode* pRoot, DataType data)
{   if (NULL == pRoot)
        return NULL;

    if (pRoot->_data > data)
        return FindBSTreeD(pRoot->pLeft, data);
    else if (pRoot->_data < data)
        return FindBSTreeD(pRoot->pRight, data);
    else
        return pRoot;
}

3、二叉树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能
对于同一个二叉树，由于插入次序不同，会得到不同的二叉树

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：lgN
最差情况下，二叉搜素树退化为单支树，请平均比较次数为：N/2