数据结构的二叉查找树

1、概念：

二叉查找树，也称排序二叉树，是指一棵空树或者具备下列性质的二叉树(每个节点都不能有多于两个儿子的树)：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树
4. 没有键值相等的节点

从其性质可知，定义排序二叉树树的一种自然的方式是递归的方法，其算法的核心为递归过程，由于它的平均深度为O(logN)，所以递归的操作树，一般不必担心栈空间被耗尽。

树的深度：对于任意节点Ni，Ni的深度为从根到Ni的惟一路径的长。

2、二叉查找树的数据节点

typedef struct _BinaryTree
{
    int value;
    struct _BinaryTree *left_child;     //左儿子
    struct _BinaryTree *right_child;
}BinaryTree;
3、创建二叉查找树节点
/*创建一个树节点*/
BinaryTree* createTreeNode(int value)
{
	BinaryTree* pBinaryTree = NULL;
	pBinaryTree = (BinaryTree *)malloc(sizeof(BinaryTree));

	memset(pBinaryTree, 0, sizeof(BinaryTree));
	pBinaryTree->value = value;
	 
	return pBinaryTree;

}
4、插入节点

鉴于二叉查找树的性质1234，用递归可以很方便的对二叉查找树插入节点

/*这里可能会修改根节点指针，所以采用二级指针传递
任意左右子树也是二叉查找树，也有相应的“根节点”*/
bool insertNode(BinaryTree **ppBinaryTree, int value)
{
	if (NULL == ppBinaryTree)
		return false;

	if (NULL == *ppBinaryTree)    //空树及递归终止条件
	{
		*ppBinaryTree = createTreeNode(value);  //创建树节点插入
		assert(NULL != *ppBinaryTree);
		return true;
	}
	else
	{   //插入值小于其根节点键值，遍历左子树
		if (value < (*ppBinaryTree)->value)
			return insertNode(&(*ppBinaryTree)->left_child, value);
	 
		//插入值大于其根节点键值，遍历右子树
		else if (value > (*ppBinaryTree)->value)
			return insertNode(&(*ppBinaryTree)->right_child, value);
	 
		//重复元插入，直接返回
		else
			return false;
	}

}
5、查找指定键值树节点
由二叉查找树的特性可知，二叉查找树在查找和插入方面相对于其余数据结构有很好的优势

BinaryTree* findTreeNode(BinaryTree *pBinaryTree, int key)
{
	if (NULL == pBinaryTree)        //二叉树不存在或递归终止条件(键值未找到)
		return NULL;

	if (key == pBinaryTree->value)  //根节点为键值或递归终止条件(找到对应键值)
		return pBinaryTree;
	 
	else if (key < pBinaryTree->value)
		return findTreeNode(pBinaryTree->left_child, key);
	 
	else
		return findTreeNode(pBinaryTree->right_child, key);

}
6、查找最小、最大键值节点

/*二叉查找树的性质让我们可以很方便的查找最小最大键值*/
/*查找最小键值节点：直接递归遍历左子树叶子节点*/
BinaryTree* findMin(BinaryTree *pBinaryTree)
{
	if (NULL == pBinaryTree)
		return NULL;

	else if (NULL == pBinaryTree->left_child)
		return pBinaryTree;
	 
	else
		return findMin(pBinaryTree->left_child);

}

/*非递归实现查找最大键值节点*/
BinaryTree* findMax(BinaryTree *pBinaryTree)
{
	if (pBinaryTree != NULL)
	{
		while (pBinaryTree->right_child)
			pBinaryTree = pBinaryTree->right_child;
	}

	return pBinaryTree;

}
7、删除指定元素节点

每种数据结构有利有弊，二叉查找树的删除操作不比链表操作那样方便，它必须保证每次删除操作之后，还是二叉查找树。所以需要考虑下列这样几种情况：

1. 删除节点为叶子节点即没有左右儿子，存在特殊情况就是该叶子节点也为根节点
2. 删除节点有两个儿子
3. 删除节点只有左儿子(左儿子是叶子节点和非叶子节点情况)，没有右儿子
4. 删除节点只有右儿子(右儿子是叶子节点和非叶子节点情况)，没有左儿子
   还需清楚的是节点的左子树的所有节点键值均小于该节点键值，其右子树的所有节点键值均大于该节点键值，清楚这点可以更好的理解删除节点之后的处理情况，以下列二叉查找树为例进行说明：

/*

*              6
*              / \  
*              2   8
*              / \   \ 
*              1   4   10
*              /
*              3
               */
               2）删除节点有两个儿子：一般的删除策略是用其右子树的最小的数据代替该节点的数据，并递归地删除那个右子树的最小节点。如果删除节点2，那么先用其右子树的最小数据节点3代替该节点的数据，然后再递归地删除节点3。数据结构的各个数据节点仅数值不同，修改数据其实就是修改数据节点。如下所示

/*

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

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



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

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

/*

*              6                             6                       6
*              / \                           / \                     / \ 
*              2   8                         2   8                   2   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
               */

2. 该右儿子不是叶子节点 ：删除节点2，先找到该节点右子树的最小数据节点并用最小节点数据代替该节点，然后递归的删除最小节点，其实此时的最小节点就是右子树的左叶子节点，可以直接删除。过程如下所示
   /*

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

树的遍历有三种：先序、中序和后序。每次遍历子树时，也要相应的按序遍历该子树。

1. 先序遍历：[首先访问根节点]  先访问根节点，再遍历左子树，最后遍历右子树
2. 中序遍历：[中间访问根节点]  先遍历左子树，再访问根节点，最后遍历右子树
3. 后序遍历：[最后访问根节点]  先遍历左子树，再遍历右子树，最后访问根节点 
   如下所示：

/*

*              6             先序遍历： 6 2 1 4 3 8 10
*              / \                      
*              2   8           中序遍历： 1 2 3 4 6 8 10
*              / \   \       
*              1   4   10        后序遍历： 1 3 4 2 10 8 6
*              /                           
*              3                           
               */
               从上得知，中序遍历二叉查找树时正好是排序好的数据。
               /*先序遍历*/
               void printPreorder(BinaryTree *pBinaryTree)
               {
               if (NULL != pBinaryTree)
               {
               	printf("%d\n", pBinaryTree->value);
               	printPreorder(pBinaryTree->left_child);
               	printPreorder(pBinaryTree->right_child);
               }
               }

/*中序遍历*/
void printInorder(BinaryTree *pBinaryTree)
{
	if (NULL != pBinaryTree)
	{
		printInorder(pBinaryTree->left_child);
		printf("%d\n", pBinaryTree->value);
		printInorder(pBinaryTree->right_child);
	}
}

/*后序遍历*/
void printPostorder(BinaryTree *pBinaryTree)
{
	if (NULL != pBinaryTree)
	{
		printPostorder(pBinaryTree->left_child);
		printPostorder(pBinaryTree->right_child);
		printf("%d\n", pBinaryTree->value);
	}
}

参考资料：《数据结构与算法分析：C语言描述》(维斯)