【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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 =