【数据结构】二叉查找树(2)

如果删除节点6，也就是根节点，先用其右子树的最小数据节点8代替该节点的数据，然后递归的删除节点8，这样删除节点8就和删除只有右儿子的数据节点操作(第4点)是一样的了。

为什么是用右子树的最小节点来替代呢？因为根据二叉查找树的特性，某节点的右子树的最小数据节点大于该节点的所有左子树节点，小于该节点的右子树节点当中除了最小节点的所有节点，这样用这个右子树最小数据节点代替该节点，那么操作之后的还是二叉查找树。

3）删除节点只有左儿子：

1. 该左儿子是叶子节点。删除节点4，由于节点(2)的右子树的所有节点键值均大于该节点键值，所以删除节点4后，直接用该节点的左儿子3取代节点4，这里的取代是将节点4的键值替换为3，这样该树中就有两个键值为3的节点，然后删除其左儿子节点3。过程如下图所示

/*
*              6                             6                       6
*             / \                           / \                     / \ 
*            2   8                         3   8                   3   8
*           / \   \        -->            / \   \        -->      / \   \
*          1   4   10                    1   3   10              1   3   10
*             /                             /
*            3                             3
*/

2. 该左儿子不是叶子节点，考虑下面这种情况：删除节点6，那么就需要先查找该节点6左子树的最大数据节点替代该节点，然后递归的删除该左子树的最大数据节点，过程如下所示，至于为什么是左子树的最大数据节点，原因和上面分析的一样。

/*
*             6                             4                       4                 4
*            /                             /                       /                 /
*           2                             2                       2                 2
*          / \            -->            / \            -->      / \     -->       / \
*         1   4                         1   4                   1   3             1   3
*            /                             /                       /
*           3                             3                       3
*/

4）删除节点只有右儿子：

1. 该右儿子是叶子节点，删除节点8，这个和删除只有左儿子的节点操作一样，过程如下所示

/*
*              6                             6                       6
*             / \                           / \                     / \ 
*            2   8                         3   10                  3   10
*           / \   \        -->            / \   \        -->      / \   
*          1   4   10                    1   4   10              1   4   
*             /                             /
*            3                             3
*/

/*
*              6                             6                       6                 
*             /                             /                       /                 
*            2                             3                       3                  
*             \            -->              \            -->        \     
*              4                             4                       4            
*             /                             /                        
*            3                             3                        
*/

从上面分析可以看出，删除操作是用树中的某个数据代替删除节点键值，实际上删除的都是叶子节点。有了上面的分析，程序就水到渠成了，如下所示

/*
*删除操作需要修改节点指针，故采用二级指针传递
*删除操作就是不断的转移目标节点，直到目标节点为叶子节点了，就删除
*/
bool deleteNode(BinaryTree **pBinaryNode,int key)
{
	BinaryTree *pTempNode = NULL;

	if ((NULL == pBinaryNode) || (NULL == *pBinaryNode))  //树为空或未找到目标节点
		return false;

	/*查找目标节点*/
	else if (key < (*pBinaryNode)->value)
		return deleteNode(&(*pBinaryNode)->left_child,key);
	else if (key >(*pBinaryNode)->value)
		return deleteNode(&(*pBinaryNode)->right_child,key);

	/*已找到目标节点pBinaryNode*/
	/*目标节点有两个儿子*/
	else if ((*pBinaryNode)->left_child && (*pBinaryNode)->right_child)
	{
		pTempNode = findMin((*pBinaryNode)->right_child);  //找到右子树的最小节点
		(*pBinaryNode)->value = pTempNode->value;
		return deleteNode(&(*pBinaryNode)->right_child,(*pBinaryNode)->value);  //递归地删除该节点
	}/*此处参数以及后面的递归删除参数均不能用pDelNode替代，必须用现在这个，否则打印时出现乱码*/
	else
	{    /*目标节点只有左儿子*/
		if ((*pBinaryNode)->left_child && (NULL == (*pBinaryNode)->right_child))
		{
			pTempNode = findMax((*pBinaryNode)->left_child);  //找到左子树的最大节点
			(*pBinaryNode)->value = pTempNode->value;
			return deleteNode(&(*pBinaryNode)->left_child,(*pBinaryNode)->value);
		}
		/*目标节点只有右儿子*/
		else if ((*pBinaryNode)->right_child && (NULL == (*pBinaryNode)->left_child))
		{
			pTempNode = findMin((*pBinaryNode)->right_child); //找到右子树的最小节点
			(*pBinaryNode)->value = pTempNode->value;
			return deleteNode(&(*pBinaryNode)->right_child,(*pBinaryNode)->value);
		}
	/*目标节点没有儿子，含叶子节点和没有儿子的根节点情况*/
	/*实际上几乎所有删除节点操作都会执行下面这步，也就是递归地删除节点最终会递归到删除某叶子节点*/
		else
		{
			free(*pBinaryNode);       //已经递归到叶子节点
			(*pBinaryNode) = NULL;   
		}
	}

	return true;
}

上述情况均逐一测试通过，测试环境：Visual Studio 2013

8、树的遍历

（编辑：ASP站长网）