【数据结构】二叉查找树

1、概念：

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

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

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

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

typedef struct _BinaryTree
{
?? ?int value;
?? ?struct _BinaryTree *left_child;???? //左儿子
?? ?struct _BinaryTree *right_child;
}BinaryTree;

/*创建一个树节点*/
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;
	}
}

由二叉查找树的特性可知，二叉查找树在查找和插入方面相对于其余数据结构有很好的优势

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、删除指定元素节点

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

还需清楚的是节点的左子树的所有节点键值均小于该节点键值，其右子树的所有节点键值均大于该节点键值，清楚这点可以更好的理解删除节点之后的处理情况，以下列二叉查找树为例进行说明：

/*
*              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
*/

（编辑：PHP编程网 - 黄冈站长网）

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