一步一步寫算法（之排序二叉樹刪除

 

【 聲明：版權所有，歡迎轉載，請勿用於商業用途。  聯系信箱：feixiaoxing @163.com】

 

    3 普通節點的刪除

 

    3.1 刪除的節點沒有左子樹，也沒有右子樹

 

     測試用例1： 刪除節點6

 

 

/*

*               

*         10          ======>     10

*        /  \                      \

*      6     15                     15

*                                                          

*/ 

 

static void test8() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 6)); 

    assert(6 == pTreeNode->left_child->data); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 15)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 6)); 

    assert(NULL == pTreeNode->left_child); 

    free(pTreeNode->right_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>     10

*        /  \                      \

*      6     15                     15

*                                                        

*/

 

static void test8()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 6));

       assert(6 == pTreeNode->left_child->data);

       assert(TRUE == insert_node_into_tree(&pTreeNode, 15));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 6));

       assert(NULL == pTreeNode->left_child);

       free(pTreeNode->right_child);

       free(pTreeNode);

}    測試用例2： 刪除節點15

 

 

/*

*               

*         10          ======>     10

*        /  \                    / 

*      6     15                 6   

*                                                         

*/ 

 

static void test9() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 6)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 15)); 

    assert(15 == pTreeNode->right_child->data); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 15)); 

    assert(NULL == pTreeNode->right_child); 

    free(pTreeNode->right_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>     10

*        /  \                    /

*      6     15                 6  

*                                                         

*/

 

static void test9()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 6));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 15));

       assert(15 == pTreeNode->right_child->data);

       assert(TRUE == delete_node_from_tree(&pTreeNode, 15));

       assert(NULL == pTreeNode->right_child);

       free(pTreeNode->right_child);

       free(pTreeNode);

}    那麼代碼應該怎麼編寫呢？

 

 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode) 

{ 

    TREE_NODE* pLeftMax; 

     

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){ 

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = NULL; 

        else 

            pTreeNode->parent->right_child = NULL; 

    } 

     

    free(pTreeNode); 

    return TRUE; 

} 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)

{

       TREE_NODE* pLeftMax;

      

       if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = NULL;

              else

                     pTreeNode->parent->right_child = NULL;

       }

      

       free(pTreeNode);

       return TRUE;

}

    3.2 刪除的節點有左子樹，沒有右子樹

 

    測試用例1： 測試節點6

 

 

/*

*               

*         10          ======>     10

*        /                      / 

*      6                      3   

*     /

*    3                                                        

*/ 

 

static void test10() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 6)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 3)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 6)); 

    assert(3 == pTreeNode->left_child->data); 

    assert(pTreeNode = pTreeNode->left_child->parent); 

    free(pTreeNode->left_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>     10

*        /                      /

*      6                      3  

*     /

*    3                                                       

*/

 

static void test10()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 6));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 3));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 6));

       assert(3 == pTreeNode->left_child->data);

       assert(pTreeNode = pTreeNode->left_child->parent);

       free(pTreeNode->left_child);

       free(pTreeNode);

}    測試用例2： 刪除節點15

 

 

/*

*               

*         10          ======>     10

*           \                       \

*           15                       12

*            /                    

*           12                                                 

*/ 

 

static void test11() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 15)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 12)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 15)); 

    assert(12 == pTreeNode->right_child->data); 

    assert(pTreeNode = pTreeNode->right_child->parent); 

    free(pTreeNode->right_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>     10

*           \                       \

*           15                       12

*            /                   

*           12                                                 

*/

 

static void test11()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 15));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 12));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 15));

       assert(12 == pTreeNode->right_child->data);

       assert(pTreeNode = pTreeNode->right_child->parent);

       free(pTreeNode->right_child);

       free(pTreeNode);

}    添加左子樹不為空，右子樹為空的處理代碼，如下所示：

 

 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode) 

{ 

    TREE_NODE* pLeftMax; 

     

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){ 

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = NULL;  

        else 

            pTreeNode->parent->right_child = NULL; 

    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){ 

        pTreeNode->left_child->parent = pTreeNode->parent; 

         

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->left_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->left_child; 

    } 

     

    free(pTreeNode); 

    return TRUE; 

} 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)

{

       TREE_NODE* pLeftMax;

      

       if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = NULL;

              else

                     pTreeNode->parent->right_child = NULL;

       }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){

              pTreeNode->left_child->parent = pTreeNode->parent;

             

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = pTreeNode->left_child;

              else

                     pTreeNode->parent->right_child = pTreeNode->left_child;

       }

      

       free(pTreeNode);

       return TRUE;

}

    3.3 刪除的節點左子樹為空，右子樹節點不為空

 

    測試用例1： 刪除數據6

 

 

/*

*               

*         10          ======>    10

*        /                     / 

*      6                      8   

*       \

*        8                                                    

*/ 

 

static void test12() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 6)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 8)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 6)); 

    assert(8 == pTreeNode->left_child->data); 

    assert(pTreeNode = pTreeNode->left_child->parent); 

    free(pTreeNode->left_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>    10

*        /                     /

*      6                      8  

*       \

*        8                                                   

*/

 

static void test12()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 6));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 8));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 6));

       assert(8 == pTreeNode->left_child->data);

       assert(pTreeNode = pTreeNode->left_child->parent);

       free(pTreeNode->left_child);

       free(pTreeNode);

}    測試用例2： 刪除數據15

 

 

/*

*               

*        10          ======>    10

*          \                      \ 

*           15                     20 

*             \

*             20                                             

*/ 

 

static void test13() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 15)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 20)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 15)); 

    assert(20 == pTreeNode->right_child->data); 

    assert(pTreeNode = pTreeNode->right_child->parent); 

    free(pTreeNode->right_child); 

    free(pTreeNode); 

} 

/*

*              

*        10          ======>    10

*          \                      \

*           15                     20

*             \

*             20                                            

*/

 

static void test13()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 15));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 20));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 15));

       assert(20 == pTreeNode->right_child->data);

       assert(pTreeNode = pTreeNode->right_child->parent);

       free(pTreeNode->right_child);

       free(pTreeNode);

}    添加左子樹為空，右子樹不為空的處理情形。代碼如下：

 

 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode) 

{ 

    TREE_NODE* pLeftMax; 

     

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){ 

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = NULL; 

        else 

            pTreeNode->parent->right_child = NULL; 

    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){ 

        pTreeNode->left_child->parent = pTreeNode->parent; 

         

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->left_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->left_child; 

    }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){ 

        pTreeNode->right_child->parent = pTreeNode->parent; 

          

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->right_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->right_child; 

    } 

     

    free(pTreeNode); 

    return TRUE; 

} 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)

{

       TREE_NODE* pLeftMax;

      

       if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = NULL;

              else

                     pTreeNode->parent->right_child = NULL;

       }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){

              pTreeNode->left_child->parent = pTreeNode->parent;

             

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = pTreeNode->left_child;

              else

                     pTreeNode->parent->right_child = pTreeNode->left_child;

       }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){

              pTreeNode->right_child->parent = pTreeNode->parent;

             

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = pTreeNode->right_child;

              else

                     pTreeNode->parent->right_child = pTreeNode->right_child;

       }

      

       free(pTreeNode);

       return TRUE;

}

    3.4 刪除的節點左右子樹均不為空，不過又要分為兩種情形：

 

    1） 左節點是刪除節點左側的最大節點 （刪除節點6）

 

 

 

/*

*               

*         10          ======>    10

*        /                     / 

*      6                      5    

*    /  \                      \

*   5    8                      8                              

*/ 

 

static void test14() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 6)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 5)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 8)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 6)); 

    assert(5 == pTreeNode->left_child->data); 

    assert(pTreeNode = pTreeNode->left_child->parent); 

    assert( 8 == pTreeNode->left_child->right_child->data); 

    assert(pTreeNode->left_child = pTreeNode->left_child->right_child->parent); 

    free(pTreeNode->left_child->right_child); 

    free(pTreeNode->left_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>    10

*        /                     /

*      6                      5   

*    /  \                      \

*   5    8                      8                             

*/

 

static void test14()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 6));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 5));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 8));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 6));

       assert(5 == pTreeNode->left_child->data);

       assert(pTreeNode = pTreeNode->left_child->parent);

       assert( 8 == pTreeNode->left_child->right_child->data);

       assert(pTreeNode->left_child = pTreeNode->left_child->right_child->parent);

       free(pTreeNode->left_child->right_child);

       free(pTreeNode->left_child);

       free(pTreeNode);

}    2） 左節點不是刪除節點左側的最大節點（刪除節點5）

 

 

/*

*               

*         10          ======>    10

*        /                     / 

*       5                      4    

*      / \                    / \

*     2   6                  2   6

*      \                               

*       4

*/ 

 

static void test15() 

{ 

    TREE_NODE* pTreeNode = NULL; 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 10)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 5)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 2)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 4)); 

    assert(TRUE == insert_node_into_tree(&pTreeNode, 6)); 

    assert(TRUE == delete_node_from_tree(&pTreeNode, 5)); 

    assert(4 == pTreeNode->left_child->data); 

    assert(NULL == pTreeNode->left_child->left_child->right_child); 

    free(pTreeNode->left_child->left_child); 

    free(pTreeNode->left_child->right_child); 

    free(pTreeNode->left_child); 

    free(pTreeNode); 

} 

/*

*              

*         10          ======>    10

*        /                     /

*       5                      4   

*      / \                    / \

*     2   6                  2   6

*      \                              

*       4

*/

 

static void test15()

{

       TREE_NODE* pTreeNode = NULL;

       assert(TRUE == insert_node_into_tree(&pTreeNode, 10));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 5));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 2));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 4));

       assert(TRUE == insert_node_into_tree(&pTreeNode, 6));

       assert(TRUE == delete_node_from_tree(&pTreeNode, 5));

       assert(4 == pTreeNode->left_child->data);

       assert(NULL == pTreeNode->left_child->left_child->right_child);

       free(pTreeNode->left_child->left_child);

       free(pTreeNode->left_child->right_child);

       free(pTreeNode->left_child);

       free(pTreeNode);

}    那麼針對這兩種類型，我們的代碼究竟應該怎麼處理呢？

 

 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode) 

{ 

    TREE_NODE* pLeftMax; 

     

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){ 

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = NULL; 

        else 

            pTreeNode->parent->right_child = NULL; 

    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){  

        pTreeNode->left_child->parent = pTreeNode->parent; 

         

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->left_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->left_child; 

    }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){ 

        pTreeNode->right_child->parent = pTreeNode->parent; 

         

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->right_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->right_child; 

    }else{ 

        pLeftMax = find_max_node(pTreeNode->left_child); 

        if(pLeftMax == pTreeNode->left_child){ 

             

            if(pTreeNode == pTreeNode->parent->left_child) 

                pTreeNode->parent->left_child = pTreeNode->left_child; 

            else 

                pTreeNode->parent->right_child = pTreeNode->left_child; 

             

            pTreeNode->left_child->parent = pTreeNode->parent; 

            pTreeNode->left_child->right_child = pTreeNode->right_child; 

            pTreeNode->right_child->parent = pTreeNode-> left_child; 

             

        }else{  

            pTreeNode->data = pLeftMax->data; 

            pLeftMax->parent->right_child = NULL; 

            pTreeNode = pLeftMax; 

        } 

    } 

     

    free(pTreeNode); 

    return TRUE; 

} 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)

{

       TREE_NODE* pLeftMax;

      

       if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = NULL;

              else

                     pTreeNode->parent->right_child = NULL;

       }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){

              pTreeNode->left_child->parent = pTreeNode->parent;

             

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = pTreeNode->left_child;

              else

                     pTreeNode->parent->right_child = pTreeNode->left_child;

       }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){

              pTreeNode->right_child->parent = pTreeNode->parent;

             

              if(pTreeNode == pTreeNode->parent->left_child)

                     pTreeNode->parent->left_child = pTreeNode->right_child;

              else

                     pTreeNode->parent->right_child = pTreeNode->right_child;

       }else{

              pLeftMax = find_max_node(pTreeNode->left_child);

              if(pLeftMax == pTreeNode->left_child){

                    

                     if(pTreeNode == pTreeNode->parent->left_child)

                            pTreeNode->parent->left_child = pTreeNode->left_child;

                     else

                            pTreeNode->parent->right_child = pTreeNode->left_child;

                    

                     pTreeNode->left_child->parent = pTreeNode->parent;

                     pTreeNode->left_child->right_child = pTreeNode->right_child;

                     pTreeNode->right_child->parent = pTreeNode-> left_child;

                    

              }else{

                     pTreeNode->data = pLeftMax->data;

                     pLeftMax->parent->right_child = NULL;

                     pTreeNode = pLeftMax;

              }

       }

      

       free(pTreeNode);

       return TRUE;

}

結束總結：

 

    上面的過程記錄了我們的代碼是怎麼一步一步走過來的。最後我們給出一份完整的節點刪除代碼：

 

 

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode) 

{ 

    TREE_NODE* pLeftMax; 

     

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){ 

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = NULL; 

        else 

            pTreeNode->parent->right_child = NULL; 

    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){ 

        pTreeNode->left_child->parent = pTreeNode->parent; 

         

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->left_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->left_child; 

    }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){ 

        pTreeNode->right_child->parent = pTreeNode->parent; 

         

        if(pTreeNode == pTreeNode->parent->left_child) 

            pTreeNode->parent->left_child = pTreeNode->right_child; 

        else 

            pTreeNode->parent->right_child = pTreeNode->right_child; 

    }else{ 

        pLeftMax = find_max_node(pTreeNode->left_child); 

        if(pLeftMax == pTreeNode->left_child){ 

             

            if(pTreeNode == pTreeNode->parent->left_child) 

                pTreeNode->parent->left_child = pTreeNode->left_child; 

            else 

                pTreeNode->parent->right_child = pTreeNode->left_child; 

             

            pTreeNode->left_child->parent = pTreeNode->parent; 

            pTreeNode->left_child->right_child = pTreeNode->right_child; 

            pTreeNode->right_child->parent = pTreeNode-> left_child; 

             

        }else{ 

            pTreeNode->data = pLeftMax->data; 

            pLeftMax->parent->right_child = NULL; 

            pTreeNode = pLeftMax; 

        } 

    } 

     

    free(pTreeNode); 

    return TRUE; 

} 

 

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data) 

{ 

    TREE_NODE* pTreeNode; 

    TREE_NODE* pLeftMax; 

     

    if(NULL == ppTreeNode || NULL == *ppTreeNode) 

        return FALSE; 

     

    pTreeNode = find_data_in_tree_node(*ppTreeNode, data); 

    if(NULL == pTreeNode) 

        return FALSE; 

     

    if(*ppTreeNode == pTreeNode){ 

         

        if(NULL == pTreeNode->left_child && NULL == pTreeNode->right_child){ 

            *ppTreeNode = NULL; 

        }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){ 

            *ppTreeNode = pTreeNode->left_child; 

            pTreeNode->left_child->parent = NULL; 

        }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){ 

            *ppTreeNode = pTreeNode->right_child; 

            pTreeNode->right_child->parent = NULL; 

        }else{ 

            pLeftMax = find_max_node(pTreeNode->left_child); 

            if(pLeftMax == pTreeNode->left_child){ 

                *ppTreeNode = pTreeNode->left_child; 

                (*ppTreeNode)->right_child = pTreeNode->right_child; 

                (*ppTreeNode)->right_child->parent = *ppTreeNode; 

                (*ppTreeNode)->parent = NULL; 

            }else{ 

                pTreeNode->data = pLeftMax->data; 

                pLeftMax->parent->right_child = NULL; 

                pTreeNode = pLeftMax; 

            } 

        } 

         

        free(pTreeNode); 

        return TRUE; 

    } 

     

    return _delete_node_from_tree(pTreeNode); 

}