前面我們談到了排序二叉樹，還沒(méi)有熟悉的同學(xué)可以看一下這個(gè)，二叉樹基本操作、二叉樹插入、二叉樹刪除1、刪除2、刪除3。但是排序二叉樹也不是沒(méi)有缺點(diǎn)，比如說(shuō)，如果我們想在排序二叉樹中刪除一段數(shù)據(jù)的節(jié)點(diǎn)怎么辦呢？按照現(xiàn)在的結(jié)構(gòu)，我們只能一個(gè)一個(gè)數(shù)據(jù)查找驗(yàn)證，首先看看在不在排序二叉樹中，如果在那么刪除；如果沒(méi)有這個(gè)數(shù)據(jù)，那么繼續(xù)查找。那么有沒(méi)有方法，可以保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是什么呢？這樣就不再需要進(jìn)行無(wú)謂的查找了。其實(shí)這樣的方法是存在的，那就是在排序二叉樹中添加向前向后雙向節(jié)點(diǎn)。

現(xiàn)在數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct _TREE_NODE
{
    int data;
    struct _TREE_NODE* prev;
    struct _TREE_NODE* next;
    struct _TREE_NODE* left;
    struct _TREE_NODE* right;
}TREE_NODE;

拿節(jié)點(diǎn)的添加來(lái)說(shuō)，我們可能需要添加prev、next的處理步驟。

void set_link_for_insert(TREE_NODE* pParent, TREE_NODE* pNode)
{
    if(NULL == pParent || NULL == pNode)
        return;

    if(pNode = pParent->left){
        pNode->prev = pParent->prev;
        if(pParent->prev)
            pParent->prev->next = pNode;
        pNode->next = pParent;
        pParent->prev = pNode;
    }else{
        pNode->next = pParent->next;
        if(pParent->next)
            pParent->next->prev = pNode;
        pNode->prev = pParent;
        pParent->next = pNode;
    }

    return;
}

STATUS add_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
    TREE_NODE* pHead;
    TREE_NODE* pNode;

    if(NULL == ppTreeNode)
        return FALSE;

    if(NULL == *ppTreeNode){
        *ppTreeNode = create_new_node(data);
        return TRUE;
    }

    if(NULL != find_data_in_tree(*ppTreeNode, data))
        return FALSE;

    pHead = *ppTreeNode;
    while(1){
        if(data < pHead->data){
            if(pHead->left){
                pHead = pHead->left;
            }else{
                pNode = create_new_node(data);
                pHead->left = pNode;
                break;
            }
        }else{
            if(pHead->right){
                pHead = pHead->right;
            }else{
                pNode = create_new_node(data);
                pHead->right = pNode;
                break;
            }
        }
    }

    set_link_for_insert(pHead, pNode);
    return TRUE;
}

添加節(jié)點(diǎn)如此，刪除節(jié)點(diǎn)的工作也不能馬虎。

void set_link_for_delete(TREE_NODE* pNode)
{
    if(pNode->prev){
        if(pNode->next){
            pNode->prev->next = pNode->next;
            pNode->next->prev = pNode->prev;
        }else
            pNode->prev->next = NULL;
    }else{
        if(pNode->next)
            pNode->next->prev = NULL;
    }
}

TREE_NODE* _delete_node_from_tree(TREE_NODE* root, TREE_NODE* pNode)
{
    TREE_NODE* pLeftMax;
    TREE_NODE* pLeftMaxParent;
    TREE_NODE* pParent = get_parent_of_one(root, pNode);

    if(NULL == pNode->left && NULL == pNode->right){
        if(pNode == pParent->left)
            pParent->left = NULL;
        else
            pParent->right = NULL;
    }else if(NULL != pNode->left && NULL == pNode->right){
        if (pNode == pParent->left)
            pParent->left = pNode->left;
        else
            pParent->right = pNode->left;
    }else if(NULL == pNode->left && NULL != pNode->right){
        if(pNode == pParent->left)
            pParent->left = pNode->right;
        else
            pParent->right = pNode->right;
    }else{
        pLeftMax = get_max_node_of_one(pNode->left);
        if(pLeftMax == pNode->left){
            pNode->left->right = pNode->right;
            if(pNode == pParent->left)
                pParent->left = pNode->left;
            else
                pParent->right = pNode->left;
        }else{
            pLeftMaxParent = get_parent_of_one(root, pLeftMax);
            pNode->data = pLeftMax->data;
            pLeftMaxParent->right = NULL;
            pNode = pLeftMax;
        }
    }

    return pNode;
}

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
    TREE_NODE* pNode;
    TREE_NODE* pLeftMax;
    TREE_NODE* pLeftMaxParent;

    if(NULL == ppTreeNode || NULL == *ppTreeNode)
        return FALSE;

    if(NULL == (pNode = find_data_in_tree(*ppTreeNode, data)))
        return FALSE;

    if(pNode == *ppTreeNode){
        if(NULL == pNode->left && NULL == pNode->right)
            *ppTreeNode = NULL;
        else if(NULL != pNode->left && NULL == pNode->right)
            *ppTreeNode = pNode->left;
        else if(NULL == pNode->left && NULL != pNode->right)
            *ppTreeNode = pNode->right;
        else {
            pLeftMax =  get_max_node_of_one(pNode->left);
            if(pNode->left == pLeftMax){
                pNode->left->right = pNode->right;
                *ppTreeNode = pNode->left;
            }else{
                pLeftMaxParent = get_parent_of_one(*ppTreeNode, pLeftMax);
                pNode->data = pLeftMax->data;
                pLeftMaxParent->right = NULL;
                pNode = pLeftMax;
            }
        }

        goto final;
    }

    pNode = _delete_node_from_tree(*ppTreeNode, pNode);

final:
    set_link_for_delete(pNode);

    free(pNode);
    return TRUE;
}

其中，尋找最大值節(jié)點(diǎn)和尋找父節(jié)點(diǎn)的代碼如下所示：

TREE_NODE* get_max_node_of_one(TREE_NODE* pNode)
{
    if(NULL == pNode)
        return NULL;

    while(pNode->right)
        pNode = pNode->right;

    return pNode;
}

TREE_NODE* get_parent_of_one(TREE_NODE* root, TREE_NODE* pNode)
{
    if(NULL == root || NULL == pNode)
        return NULL;

    while(root){
        if(pNode == root->left || pNode == root->right)
            return root;
        else if(pNode->data < root->data)
            root = root->left;
        else
            root = root->right;
    }

    return NULL;
}

總結(jié)：
（1）排序二叉樹的序列化關(guān)鍵就是在二叉樹節(jié)點(diǎn)添加前向指針和后繼指針
（2）排序二叉樹是空間換時(shí)間的典型案例
（3）排序二叉樹是很多結(jié)構(gòu)的基礎(chǔ)，寫多少遍都不為多，有機(jī)會(huì)朋友們應(yīng)該多加練習(xí)
（4）測(cè)試用例的編寫是代碼編寫的關(guān)鍵，編寫程序的目的就是為了消除bug，特別是低級(jí)bug

上一篇：字符串查找中篇下一篇：克魯斯卡爾算法下

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

排序二叉樹線索化