排序二叉树节点的删除

要点：

1.查找到被删除的节点

2.分析要删除的节点

　　1.叶子结点

　　2.有一个孩子

　　3.有两个孩子（根节点和其他节点）

代码实现：

void SearchNode(Tree** pDel,Tree** pFather,int num)
{
    while(*pDel)
    {
        if((*pDel)->val == num)
            return;
        else if((*pDel)->val > num)
        {
            *pFather = *pDel;
            *pDel = (*pDel)->pleft;
        }
        else
        {
            *pFather = *pDel;
            *pDel = (*pDel)->pright;
        }
    }
    *pDel = NULL;
}
void DelNode(Tree** pRoot,int num)
{
    Tree* pDel = *pRoot;
    Tree* pFather = NULL;
    SearchNode(&pDel,&pFather,num);
    if(pDel == NULL)//没找到
        return;
    Tree* pMark = NULL;
    //有两个孩子
    if(pDel->pleft != NULL && pDel->pright != NULL)
    {
        pMark = pDel;
        pFather = pDel;
        pDel = pDel->pleft;
        while(pDel)
        {
            pFather = pDel;
            pDel = pDel->pright;
        }
        pMark->val = pDel->val;
    }
    //只有一个孩子或者没有孩子
    if(pDel == *pRoot)
    {//根只有一个孩子或者没有孩子
        *pRoot = pDel->pleft ? pDel->pleft : pDel->pright;
    }
    if(pDel == pFather->pleft)
        pFather->pleft = pDel->pleft ? pDel->pleft : pDel->pright;
    if(pDel == pFather->pright)
        pFather->pright = pDel->pleft ? pDel->pleft : pDel->pright;
    free(pDel);
    pDel = NULL;
}

其中查找函数Search可以传入多一个参数：

void FindNode(BinaryTree *pTree,int nNum,BinaryTree **pDel,BinaryTree **pFather)
{
    while(pTree)
    {
        if(pTree->nValue == nNum)
        {
            *pDel = pTree;
            return;
        }
        else if(pTree->nValue > nNum)
        {
            *pFather = pTree;
            pTree = pTree->pLeft;
        }
        else
        {
            *pFather = pTree;
            pTree = pTree->pRight;
        }
    }
    
    *pFather = NULL;
}

void DelNode(BinaryTree **pTree,int nNum)
{
    if(*pTree == NULL)return;

    //查找
    BinaryTree *pDel = NULL;
    BinaryTree *pFather = NULL;

    FindNode(*pTree,nNum,&pDel,&pFather);

    //分析被删除节点情况
    if(pDel == NULL)return;

    //两个孩子
    BinaryTree *pMark = NULL;
    if(pDel->pLeft != NULL && pDel->pRight != NULL)
    {
        pMark = pDel;

        //左的最右
        pFather = pDel;
        pDel = pDel->pLeft;

        while(pDel->pRight != NULL)
        {
            pFather = pDel;
            pDel = pDel->pRight;
        }

        //值覆盖
        pMark->nValue = pDel->nValue;
    }

    //删除有一个孩子或者0个孩子
    if(pFather == NULL)
    {
        //根
        *pTree = pDel->pLeft?pDel->pLeft:pDel->pRight;

        free(pDel);
        pDel = NULL;
        return;
    }
    

    if(pDel == pFather->pLeft)
    {
        pFather->pLeft = pDel->pLeft?pDel->pLeft:pDel->pRight;
    }
    else
    {
        pFather->pRight = pDel->pLeft?pDel->pLeft:pDel->pRight;
    }

    free(pDel);
    pDel = NULL;
}