数据结构——二叉排序树

二叉排序树（binary search tree简称BST）就是左子树的所有结点小于根节点，右子树的所有结点大于根节点，且结点保存的数据不同的二叉树。

如下图：

如果查找的值小于当前结点的值，就到该节点的左子树去找。

如果大于，就到当前节点的右子树去找。如果等于则返回。

template
typename BsTree::node* BsTree::search1(const T& obj)
{
	node* p = root;
	while (p && p->data != obj)
	{
		if (obj < p->data)
			p = p->left;
		if (obj > p->data)
			p = p->right;
	}
	return p;
}
template
typename BsTree::node* BsTree::search2(const T& obj,node* current)
{
	if (!current)
		return current;
	if (obj < current->data)
		return search2(current->left);
	else if (obj > current->data)
		return search2(current->right);
	else return current;
}

递归的函数更好，因为不需要递归所需的栈空间。

如果插入值小于当前结点的值，就到结点的左子树去插入。

如果插入值大于当前结点的值，就到结点的右子树去插入。

直到当前指针指是空指针，开始插入。

template
void BsTree::insert1(const T& temp)
{
	node* p = root;
	while (p)
	{
		if (temp < p->data)
			p = p->left;
		else if (temp > p->data)
			p = p->right;
		else throw("error");
	}
	p = new node(temp);
}
template
void BsTree::insert2(const T& temp, node* current)
{
	if (!current)
	{
		current = new node(temp);
	}
	if (temp < current->data)
		insert2(temp, current->left);
	else if (temp > current->data)
		insert2(temp, current->right);
	else throw("error");
}

删除当前结点，我们需要对删除后的树进行整合，保持二叉排序树的结构。

因此，我们需要原来结点下的一个结点来代替原来结点。

那么我们怎么选择结点才能保持二叉搜索树的结构呢？

1.选择左子树最大的结点来代替删除的结点。

2.选择右子树最小的结点来代替删除的结点。

3.如果左右子树没有结点则不做处理，直接删除。

但要注意两点：

1.我们要修改我们选择的结点的父节点指针。

2.要修改删除结点的父节点指针。

另外一个知识点是查找长度，即我们查找一个值需要比较的次数。

其实二叉排序树查找时间复杂度要最小，那就需要平衡二叉树的知识了。