【数据结构】二叉查找树

/*
*              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、树的遍历

（编辑：网站开发网_盐城站长网 ）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!