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

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

拿节点的添加来说，我们可能需要添加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_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;
}

总结：
（1）排序二叉树的序列化关键就是在二叉树节点添加前向指针和后继指针
（2）排序二叉树是空间换时间的典型案例
（3）排序二叉树是很多结构的基础，写多少遍都不为多，有机会朋友们应该多加练习
（4）测试用例的编写是代码编写的关键，编写程序的目的就是为了消除bug，特别是低级bug