【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面我們談到了排序二叉樹，還沒有熟悉的同學可以看一下這個，二叉樹基本操作、二叉樹插入、二叉樹刪除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;
typedef struct _TREE_NODE
{
int data;
struct _TREE_NODE* prev;
struct _TREE_NODE* next;
struct _TREE_NODE* left;
struct _TREE_NODE* right;
}TREE_NODE; 拿節點的添加來說，我們可能需要添加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;
}
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;
} 添加節點如此，刪除節點的工作也不能馬虎。
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;
}
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;
}
其中，尋找最大值節點和尋找父節點的代碼如下所示：
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;
}
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;
}
總結：
（1）排序二叉樹的序列化關鍵就是在二叉樹節點添加前向指針和後繼指針
（2）排序二叉樹是空間換時間的典型案例
（3）排序二叉樹是很多結構的基礎，寫多少遍都不為多，有機會朋友們應該多加練習
（4）測試用例的編寫是代碼編寫的關鍵，編寫程序的目的就是為了消除bug，特別是低級bug
