【二叉搜索树】

一、认识二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它具有以下特征：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

如图：

二、二叉搜索树实现

在实现各种操作之前，我们先创建节点，使用结构体+类模板来创建，因为结构体默认访问权限是共有的（即public），里面需要写到左子树、右子树、结点的值，再写个构造函数赋初值。

template<class K>
struct  BStreeNode
{
	BStreeNode<K>* _left;
	BStreeNode<K>* _right;
	K _key;
	
	BStreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};

2.1插入

插入操作步骤：

• 树为空，则直接新增节点，赋值给root指针
• 树不空，按二叉搜索树性质查找插入位置，插入新节点

解析：

• 首先while循环进行遍历,若该key值比cur值小，则向cur左树找，反之，右树找，直到叶子节点为止。如果与cur值相同，返回false（因为二叉搜索树不允许有相同的数出现）。

• 插入过程需要连接，创建个parent节点跟着我们需要遍历的节点（cur）完成连接过程。

• 跟父节点比较，比父节点大，插入到他的右边，反之，就是左边。

代码：

bool insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new node(key);
		return true;
	}
	node* parent = nullptr;
	node* cur = _root;//
	//cur每次要向下走，parent也跟着走
	while (cur)
	{
		if (key< cur->_key )
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key> cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;

		}
	}
	cur = new node(key);
	if (parent->_key < key)
	{
		//如果插入的值比目标值大，就连接在右边；
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

2.2查找

若key大于cur->_key就从右树找
key小于cur->_key就从左子树找。
如果相等 返回true；

bool Find(const K& key)
{
	node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else {
			return true;
		}
	}
	return false; 
}

2.3删除

1、首先定义个父节点parent和节点cur（指向根节点）
2、再循环遍历cur，先找要删除的节点。

• 若删除的节点左数为空，且删除的是根节点，让根结点指向原根结点的右子树。删除的不是根节点，让他的子树托孤给他的父节点。
• 如果右节点空，删除的是根节点，让他的根节点只想原根结点的左子树，不是根节点，就托孤给父节点
• 左右都不为空的情况下。父节点指向cur，leftnode（被删节点的左子树）指向cur的左子树，循环遍历leftnode右子树，交换cur与leftnode值，如果leftnode在父节点的左子树，那就将leftnode的左子树给父节点的左子树，否则就给父节点的右子树。最后将leftnode传给cur，再删除cur.

bool Erase(const K& key)
{
	node* parent = nullptr;
	node* cur = _root;
	//没有节点

	while (cur)
	{
		//找
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else
		{
			//找到了  左空
			if (cur->_left == nullptr)
			{
				if (cur == _root)//如果cur没有parent，他就是根节点
				{
					_root = cur->_right;
				}
				else {
					if (parent->_right == cur)//如果cur右为空，并且是父亲的右节
					{//节点指向cur
							parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
				}
			}
			//
			else if (cur->_right == nullptr)//如果cur右为空。
			{ 
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
				
			}
			else {
				node* parent = cur;
				node* leftnode = cur->_left;
				//右边不为空的情况，一直找下去
				while (leftnode->_right)
				{
					parent = leftnode;//每次走之前给parent
					leftnode = leftnode->_right;
				}
				swap(cur->_key, leftnode->_key);
				if (parent->_left == leftnode)
				{
					parent->_left = leftnode->_left;
				}
				else
				{
					parent->_right = leftnode->_left;
				}

				cur = leftnode; 
			}
			delete cur;
			return true;
		}
	}
}

总结

以上就是本期内容，以后会多多更新