Binary Search Tree

#pragma once
#include<assert.h>
#include<malloc.h>
#include<stdio.h>
typedef int DataType;

typedef struct BSTreeNode
{
    struct BSTreeNode* _pLeft;
    struct BSTreeNode* _pRight;
    DataType _data;
}BSTNode,*BSTreeNode;

void BSTreeNodeInit(BSTreeNode* pRoot)
{
    *pRoot = NULL;
}

BSTreeNode BuyBSTreeNode(DataType data)
{
    BSTreeNode pNewNode = (BSTreeNode)malloc(sizeof(BSTNode));//malloc函数开辟的空间一定要判空
    if (NULL == pNewNode)
    {
        assert(0);
        return NULL;
    }
    pNewNode->_data = data;
    pNewNode->_pLeft = NULL;
    pNewNode->_pRight = NULL;
    return pNewNode;
}

void BSTreeNodeInsertNor(BSTreeNode* pRoot, DataType data)//插入（非递归）
{
    //树为空，直接插入
    if (NULL == *pRoot)
    {
        *pRoot = BuyBSTreeNode(data);
        return;
    }
    //树不为空
    //找插入位置
    else
    {
        BSTreeNode pCur = NULL;
        BSTreeNode pParent = NULL;
        assert(pRoot);
        pCur = *pRoot;
        while (pCur)
        {
            if (data == pCur->_data)
            {
                return;
            }
            else if (data < pCur->_data)
            {
                pParent = pCur;
                pCur = pCur->_pLeft;
            }
            else if (data > pCur->_data)
            {
                pParent = pCur;
                pCur = pCur->_pRight;
            }
            else
            {
                return;
            }
        }
        if (pParent->_data<data)
            pParent->_pRight = BuyBSTreeNode(data);
        else if (pParent->_data>data)
            pParent->_pLeft = BuyBSTreeNode(data);
    }
}



int BSTreeNodeFindNor(BSTreeNode pRoot,DataType data)//查找（非递归）
{
    if (NULL == pRoot)
    {
        printf("树为空\n");
    }
    while (pRoot)
    {
        if (pRoot->_data == data)
        {
            return 1;
        }
        else if (pRoot->_data > data)
        {
            pRoot = pRoot->_pLeft;
        }
        else if (pRoot->_data < data)
        {
            pRoot = pRoot->_pRight;
        }
        else
        {
            return 0;
        }
    }
    return 0;
}



void DeleteBSTreeNodeNor(BSTreeNode* pRoot, DataType data)//删除（非递归）
{
    assert(pRoot);
    //查找值为data的节点
    BSTreeNode pCur = NULL;//要删除的的节点
    BSTreeNode pParent = NULL;
    pCur = *pRoot;
    while (pCur)
    {
        if (data == pCur->_data)
        {
            //pParent = pCur;
            break;
        }
        else if (data < pCur->_data)
        {
            pParent = pCur;
            pCur = pCur->_pLeft;
        }
        else
        {
            pParent = pCur;
            pCur = pCur->_pRight;
        }
    }
    //没找到，直接返回
    if (NULL == pCur)
    {
        printf("待删除节点不在二叉树中\n");
        return;
    }
    //找到了，分情况讨论
    //1.要删除的节点没有左孩子，即只有右孩子或左右孩子都没有
    if (pCur->_pLeft == NULL)
    {
        if (pCur == *pRoot)
            *pRoot = pCur->_pRight;
        else
        {
            if (pCur == pParent->_pLeft)
            {
                pParent->_pLeft = pCur->_pRight;
            }
            else
            {
                pParent->_pRight = pCur->_pRight;
            }
        }
    }
    //2.要删除的节点没有右孩子，即只有左孩子或左右孩子都没有
    else if (pCur->_pRight == NULL)
    {
        if (pCur == *pRoot)
        {
            *pRoot = pCur->_pLeft;
        }
        else
        {
            if (pCur == pParent->_pLeft)
            {
                pParent->_pLeft = pCur->_pLeft;
            }
            else
            {
                pParent->_pRight = pCur->_pLeft;
            }
        }
    }
    //3.要删除的节点左右孩子都存在，在其右子树中找一个最小的节点，替代待删除节点
    else
    {
        BSTreeNode pDel = pCur->_pRight;
        pParent = pCur;
        while (pDel->_pLeft)
        {
            pParent = pDel;
            pDel = pDel->_pLeft;
        }
        pCur->_data = pDel->_data;
        if (pDel == pParent->_pLeft)
        {
            pParent->_pLeft = pDel->_pRight;
        }
        else
        {
            pParent->_pRight = pDel->_pRight;
        }
        pCur = pDel;
        free(pDel);
    }
}



void CreatBSTree(BSTreeNode* pRoot, DataType a[], int size)
{
    int i = 0;
    for (; i < size; ++i)
    {
        BSTreeNodeInsert(&(*pRoot), a[i]);
    }
}


void TestBSTreeNode()
{
    BSTreeNode pRoot=NULL;
    BSTreeNodeInit(&pRoot);
    int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    CreatBSTree(&pRoot, a, sizeof(a) / sizeof(a[0]));
    InpRoot(pRoot);
    printf("\n");

    if (!BSTreeNodeFindNor(pRoot, 4))
        printf("Not Found\n");
    else
        printf("Found\n");

    printf("\n");

    if (!BSTreeNodeFind(pRoot, 4))
        printf("Not Found\n");
    else
        printf("Found\n");

    DeleteBSTreeNodeNor(&pRoot, 10);
    InpRoot(pRoot);
    printf("\n");

    DeleteBSTreeNode(&pRoot, 10);
    InpRoot(pRoot);
    printf("\n");
}