C++算法之二叉樹線索化

前面我們談到了排序二叉樹，還沒有熟悉的同學可以看一下這個，二叉樹基本操作、二叉樹插入、二叉樹刪除1、刪除2、刪除3。但是排序二叉樹也不是沒有缺 點，比如說，如果我們想在排序二叉樹中刪除一段數據的節點怎么辦呢？按照現在的結構，我們只能一個一個數據查找驗證，首先看看在不在排序二叉樹中，如果在 那么刪除；如果沒有這個數據，那么繼續查找。那么有沒有方法，可以保存當前節點的下一個節點是什么呢？這樣就不再需要進行無謂的查找了。其實這樣的方法是 存在的，那就是在排序二叉樹中添加向前向后雙向節點。  現在數據結構定義如下：

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

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;  

}
</pre>     添加節點如此，刪除節點的工作也不能馬虎。
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;  

}

</pre>     其中，尋找最大值節點和尋找父節點的代碼如下所示：
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;  

}
</pre> 總結：

     （1）排序二叉樹的序列化關鍵就是在二叉樹節點添加前向指針和后繼指針

     （2）排序二叉樹是空間換時間的典型案例

     （3）排序二叉樹是很多結構的基礎，寫多少遍都不為多，有機會朋友們應該多加練習

     （4）測試用例的編寫是代碼編寫的關鍵，編寫程序的目的就是為了消除bug，特別是低級bug