在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

鍍金池/ 教程/ 數(shù)據(jù)分析&挖掘/ 排序二叉樹刪除-3
hash表
單詞統(tǒng)計(jì)
鏈表排序
查找
可變參數(shù)
爬樓梯
內(nèi)存
prim算法 中
線性結(jié)構(gòu)的處理
數(shù)據(jù)選擇
prim算法 上
循環(huán)單向鏈表
基數(shù)排序
堆排序
鏈表重合
排序二叉樹的保存和加載
圖添加和刪除
排序二叉樹線索化
非遞歸排序
字符串查找 下篇
鏈表逆轉(zhuǎn)
函數(shù)堆棧顯示
遞歸和堆棧
二叉樹深度遍歷
線性隊(duì)列
循環(huán)和遞歸
快速排序
尋找丟失的數(shù)
A*算法
克魯斯卡爾算法 下
排序二叉樹
大數(shù)計(jì)算
二叉樹廣度遍歷
prim算法 下
洗牌算法
圖結(jié)構(gòu)
最大公約數(shù)、最小公倍數(shù)
圖創(chuàng)建
雙向鏈表
字符串查找 上篇
尋路
通用算法的編寫
哈夫曼樹 下
線性堆棧
八皇后
排序二叉樹刪除-1
挑選最大的n個(gè)數(shù)
字符串查找 中篇
哈夫曼樹 上
合并排序
回?cái)?shù)
選擇排序
哈希二叉樹
通用數(shù)據(jù)結(jié)構(gòu)
“數(shù)星星”
單向鏈表
排序二叉樹插入
圖的保存
排序二叉樹刪除-2
排序二叉樹刪除-3
n！中末尾零的個(gè)數(shù)統(tǒng)計(jì)

排序二叉樹刪除-3

3 普通節(jié)點(diǎn)的刪除

3.1 刪除的節(jié)點(diǎn)沒有左子樹，也沒有右子樹

測試用例1： 刪除節(jié)點(diǎn)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);  
}

測試用例2： 刪除節(jié)點(diǎn)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);  
}

那么代碼應(yīng)該怎么編寫呢？

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 刪除的節(jié)點(diǎn)有左子樹，沒有右子樹

測試用例1： 測試節(jié)點(diǎn)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);  
}

測試用例2： 刪除節(jié)點(diǎn)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);  
}

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

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 刪除的節(jié)點(diǎn)左子樹為空，右子樹節(jié)點(diǎn)不為空

測試用例1： 刪除數(shù)據(jù)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);  
}

測試用例2： 刪除數(shù)據(jù)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);  
}

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

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 刪除的節(jié)點(diǎn)左右子樹均不為空，不過又要分為兩種情形：

1） 左節(jié)點(diǎn)是刪除節(jié)點(diǎn)左側(cè)的最大節(jié)點(diǎn) （刪除節(jié)點(diǎn)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);  
}

2） 左節(jié)點(diǎn)不是刪除節(jié)點(diǎn)左側(cè)的最大節(jié)點(diǎn)（刪除節(jié)點(diǎn)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);  
}

那么針對(duì)這兩種類型，我們的代碼究竟應(yīng)該怎么處理呢？

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 = pLeftMax->left_child;  
            pLeftMax->left_child->parent = pLeftMax->parent;  
            pTreeNode = pLeftMax;  
        }  
    }  

    free(pTreeNode);  
    return TRUE;  
}

結(jié)束總結(jié)：

上面的過程記錄了我們的代碼是怎么一步一步走過來的。最后我們給出一份完整的節(jié)點(diǎn)刪除代碼：

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 = pLeftMax->left_child;  
            pLeftMax->left_child->parent = pLeftMax->parent;             
            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 = pLeftMax->left_child;  
                pLeftMax->left_child->parent = pLeftMax->parent;  
                pTreeNode = pLeftMax;  
            }  
        }  

        free(pTreeNode);  
        return TRUE;  
    }  

    return _delete_node_from_tree(pTreeNode);  
}