由 dawei 副标题#e#
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,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 */
#p#副标题#e##p#分页标题#e#
如果删除节点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 */
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、树的遍历
#p#副标题#e##p#分页标题#e#
树的遍历有三种：先序、中序和后序。每次遍历子树时，也要相应的按序遍历该子树。
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语言描述》(维斯)