# 一步一步写算法（之排序二叉树线索化）

2011-11-02

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】 前面我们谈到了排序二叉树，还没有熟悉的同学可以看一下这个，二叉树基本操作、二叉树插入、二叉树删除1、删除2、删除3...

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

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的处理步骤。

{

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;

}

{

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;

while(1){

}else{

pNode = create_new_node(data);

break;

}

}else{

}else{

pNode = create_new_node(data);

break;

}

}

}

return TRUE;

}

{

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;

}

{

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;

while(1){

}else{

pNode = create_new_node(data);

break;

}

}else{

}else{

pNode = create_new_node(data);

break;

}

}

}

return TRUE;

} 添加节点如此，删除节点的工作也不能马虎。

{

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:

free(pNode);

return TRUE;

}

{

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:

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