二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

template <class K>
struct BSTnode//搜索二叉树不支持修改  中序遍历是有序的
{

	K _key;
	BSTnode<K>* _left;
	BSTnode<K>* _right;
};
	template<class K>
	class BSTree
	{

		typedef BSTnode<K> node;
	public:

    private:
		node* _root = nullptr;
	};

这是一个简单的框架

首先我们先写一个find查找函数

	bool find(const K& key)
	{

    }

逻辑是按照搜索二叉树的规律右孩子比节点大 左孩子比节点小   这样我们在遍历的过程中

不断的与遍历节点比较大小 如果比当前节点大 就向右走 如果比节点小  就向左走  

		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;
		}

接下来我们写一个插入insert函数

bool insert(const K& key)
{

}

这里的返回bool类型是插入函数除了有插入的功能还有查找的功能 因为一个搜索二叉树中 一个值只能存在一个节点 不能重复存储 所以当插入的值在遍历时如果遇到与自己大小相同的节点时 就会返回false  如果没有遇到相同节点 且到达null位置 则在这个位置创建节点 并存值 返回true 

而在创建节点之后还要与父节点进行连接  所以还要知道父节点位置   

如果比父节点值大 就插在右边 如果比节点值小 就插在左边  

bool insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new node(key);
		return true;
	}

	node* parent = nullptr;
	node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

这里之前节点类并没有写构造函数 所以先要补上

template <class K>
struct BSTnode//搜索二叉树不支持修改  中序遍历是有序的
{

	K _key;
	BSTnode<K>* _left;
	BSTnode<K>* _right;

	BSTnode(const K& key)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

接下来写遍历函数 中序遍历时有序的

void inorder(node* root)
{
	if (root == nullptr)
	{
		return;
	}
	inorder(root->_left);
	cout << root->_key << " ";
	inorder(root->_right);
}

这里会由一个问题 由于我们的根节点指针是私有成员变量 无法外部访问 所以无法传参   解决方法将inorder函数写成私有成员函数 在公有中在套一层inorder函数

	void	inorder()//方法二
	{
		inorder(_root);
		cout << endl;
	}


private:
	void inorder(node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		inorder(root->_left);
		cout << root->_key << " ";
		inorder(root->_right);
	}


	node* _root = nullptr;
};

        

int main()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	bit::BSTree<int> t;
	for (auto e :a)
	{
		t.insert(e);
	}
	 
	
	t.inorder();

	return 0;
}

可以看到搜索二叉树不仅可以查找 去重  还可以排序

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$log_2 N$

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$  

后续学习的AVL树和红黑树就可以解决问题

接下来讲解搜索二叉树的删除

对于节点的删除 可以分三种情况

1.叶子节点  没有孩子

2.有一个孩子的节点

3.有两个孩子的节点

没有孩子节点 和有一个孩子的节点 都可以直接交给父节点链接 

而两个孩子的节点删除 就需要找一个节点进行替代  分别是左子树的最大节点 和右子树的最小节点

bool erase(const K& key)
{
	node* parent = nullptr;
	node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
           //这里进行删除
        }
    }
return false;
}

 将没有孩子 和有一个孩子节点删除归为一种情况   首先判断留有的是左孩子还是有孩子   没有孩子自动归为没有左孩子一类   之后判断是否有父节点  如果没有父节点 删除的是跟节点 则直接让其孩子作为跟节点  如果有父节点  则判断当前节点时父节点的左孩子还是右孩子  如果左孩子 则让当前节点的孩子链接父节点的左边 如果是右孩子 则令当前节点的孩子链接父节点的右边  最后删除当前节点 返回true

if (cur->_left == nullptr)
{
				if (parent == nullptr)
					_root = cur->_right;

				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}

				delete cur;
				return true;

}
else if (cur->_right == nullptr)
{

				if (parent == nullptr)
					_root = cur->_left;
				else
				{
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}

				delete cur;
				return true;

}

如果是有两个孩子的结点  则要找右子树的最小节点 来替换当前节点

rightmin就是要找的右子树的最小节点  而frm则是它的父节点   这里会有一种特殊情况 那就是 右子树的最小节点时cur->right  而frm就是cur  对这种情况要单独判断并处理一下

else
{
				node* frm = cur;
				node* rightmin = cur->_right;
				while (rightmin->_left)
				{
					frm = rightmin;
					rightmin = rightmin->_left;
				}
				cur->_key = rightmin->_key;
				if (frm == cur)
				{

					frm->_right = rightmin->_right;

				}
				else
				{

					frm->_left = rightmin->_right;

				}
				delete rightmin;
				return true;
}

测试一下 

int main()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	bit::BSTree<int> t;
	for (auto e :a)
	{
		t.insert(e);
	}
	for (auto E : a)
{
	t.erase(E);
	t.inorder();
}

	return 0;
}