C++--二叉搜索树初阶

       前言：二叉搜索树是一种常用的数据结构，支持快速的查找、插入、删除操作，C++中map和set的特性也是以二叉搜索树作为铺垫来实现的，而二叉搜索树也是一种树形结构，所以，在学习map和set之前，我们先来学习这种新的树形结构--二叉搜索树。

目录

1.二叉搜索树

二叉搜索树的功能及其实现

二叉搜索树的插入和查找

二叉搜索树的删除

查找函数递归实现

插入函数递归实现

删除函数递归实现

拷贝构造和赋值运算符重载

搜索二叉树的相关性质及其应用

二叉搜索树的查找

key-value模型

---

1.二叉搜索树

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

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

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

     它的左右子树也分别为二叉搜索树，同样的，我们可以发现，二叉搜索树的中序遍历是升序排序的

二叉搜索树的功能及其实现

        我们先定义基础的节点的数据结构，明显是一个二叉树类型的节点，有左右节点，运用模板知识，我们可以描述出以下的节点结构体和搜索树的类的描述：

template<class T>
struct BSTreeNdoe {
	BSTreeNdoe(const T& data = T())
		: _left(nullptr), _right(nullptr), data(data)
	{}
	BSTreeNdoe* _left;
	BSTreeNdoe* _right;
	T data;
 
};
template<class T>
class BSTree {
 
	typedef BSTreeNdoe Node;
public:
     //成员函数
 
private:
	Node* root = nullptr;
 
};

下面的功能函数将从上面给出的结构来进行扩充功能和优化改写：

二叉搜索树的插入和查找

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点，从树的根节点依次寻找：如果待插入的值比当前节点大，那直接插入当前节点的右边，反之，插入当前节点的左边，这里注意，一般的，在二叉搜索树中不会存在相同的值，需要注意的是，为了保证新节点能够和树连接起来，需要记录好父节点。

//插入操作
	bool insert(const T& key)
	{
		if (root == nullptr)//如果当前树为空，那么直接建树
		{
			root = new Node(key);
			return true;
		}
		//如果不为空，直接寻找合适的位置插入即可
		Node* cur = root;
		Node* parent = nullptr;//记录父亲节点用来连接
		while (cur)
		{
			parent = cur;
			if (cur->data > key)//比当前节点小，往当前节点左边走
				cur = cur->_left;
			else if (cur->data < key)//比当前节点大，往当前节点右边走
				cur = cur->_right;
			//一般来说，搜索二叉树不会存在相同的两个值
			else
				return false;
		}
		cur = new Node(key);
		if (parent->data > key)
			parent->_left = cur;
		else if (parent->data < key)
			parent->_right = cur;
		return true;
	}

二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

bool find(const T& key)
	{
		Node* cur = root;
		while (cur)
		{
			if (cur->data > key)
				cur = cur->_left;
			else if (cur->data < key)
				cur = cur->_right;
			else
				return true;
		}
		return false;
	}

二叉搜索树的删除

        首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

       实际上，这四种情况中，a情况可以算作b或者c情况中，因为删除叶子结点，本质上可以看做要删除的节点只有为nullptr的右孩子或者左孩子节点，我们来分别对这三种情况进行分析，

       对于替换法，我们需要注意特殊的情况，从上面的图可以看出，左子树中的最右节点，本质上就是第一次往待删除节点的左孩子节点走，之后的每一步，都开始往其右孩子方向走，右子树的最左节点是第一次往待删除节点的右孩子节点走，之后一直往其左孩子方向走，此时，我们的替换法是建立在待删除节点的左右孩子都存在的前提下，所以，左树最右节点和右树最左节点，左树和右树一定都具备，但是不一定有最右和最左节点，下面我们就以左树最右节点为例，来进行讨论分析：

下面是一颗普通的二叉树：

        因为此时待删除节点需要满足存在左右节点，所以，此时符合要求的节点只有8,3，其中8是正常的情况，因为其左子树有右孩子，通过8到3之后可以直接找到7，所以8可以直接和7进行交换，因为此时已经遍历到了左子树的最右节点，也就是说，该节点不可能再存在右孩子，但是不能保证没有左孩子，比如说没有7这个节点，要删除8,8就只能和6交换，此时我们需要将4，也就是被交换节点的左子树放在3的右孩子上，这样就能达到删除8的目的；

     此时我们再来看3这个节点，这个节点特殊在其只有一个左孩子节点，并且左孩子节点没有了右子树，导致我们找左树最右节点的时候，只能找到第一步左树的位置而被迫停下来，此时，这个左树就只能当做左树的最右节点来看待，只是此时我们在将1和3交换之后，操作上要发生变化，因为此时没有了右子树，所以被交换后，3成了左子树，也就是说需要删除的是1的左子树而不是像上面的情况一样直接将被交换节点的父节点的右树直接被删除节点的左树。

这里我们给出代码和测试二叉树，方便我们下来模拟运行和理解：

//删除节点
	bool Erase(const T& key)
	{
		Node* parent = nullptr;
		Node* cur = root;
		while (cur)
		{
			if (cur->data < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->data > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找到了，开始删除
				//只有右孩子
				if (cur->_left == nullptr)
				{
					//此时父节点有三种情况
 
					//如果要删除的是根节点,需要特殊处理
					if (cur == root)
						root =cur->_right;
					else if (cur == parent->_left)
						parent->_left = cur->_right;
					else if (cur == parent->_right)
						parent->_right = cur->_right;
					delete cur;
				}
				//只有左孩子
				else if (cur->_right == nullptr)
				{
					//此时父节点有三种情况
 
					//如果要删除的是根节点
					if (cur == root)
						root = cur->_left;
					else if (cur == parent->_left)
						parent->_left = cur->_left;
					else if (cur == parent->_right)
						parent->_right = cur->_left;
					delete cur;
				}
				//有左右两个孩子节点
				else
				{
					//法1：假设默认选择左子树的最大节点
					//Node* pright = cur->_left;//先找到左子树，此时我们能确保待删除节点是有两个孩子的,所以p一定不为空
					//Node* pp = cur;//初始时父节点等于待删除节点
					//while (pright->_right)
					//{
					//	pp = pright;//更新父节点
					//	pright = pright->_right;
					//}
					//std::swap(cur->data, pright->data);
 
					//
					//if (pright == pp->_left)//左子树不存在右孩子，直接将p->_left赋值pp的左孩子即可
					//	pp->_left = pright->_left;
					//else  //左子树存在右孩子
					//	pp->_right = pright->_left; //直接将交换后的节点的左子树放到待删除节点的父节点的右子树上
					//delete pright;
 
					//法2：假设选择右子树的最小节点
					Node* pleft = cur->_right;//选择右子树,但是最终目的是寻找右子树的最左节点
					Node* pp = cur;
					while (pleft->_left)
					{
						pp = pleft;
						pleft = pleft->_left;
					}
					std::swap(cur->data, pleft->data);
 
					if (pleft == pp->_right)//如果待删除节点的右子树没有左孩子
						pp->_right = pleft->_right;
					else //如果是正常情况
						pp->_left = pleft->_right;//最左节点的右孩子需要保留在pp的左子树
					delete pleft;
				}
				return true;
			}
		}
		return false;
	}

查找函数递归实现

protected:
	bool findr(Node* root,const T&key)
	{
		if (root == nullptr)
			return false;
		else if (root->data > key)
			return finr(root->_left, key);
		else if (root->data < key)
			return finr(root->_right, key);
		else
			return true;
	}
public:
	bool FindR(const T&key)
	{
		return findr(root,key);
	}

插入函数递归实现

protected:
	bool insertr(Node* &root, const T& key)//由于要修改原树，所以建议传引用
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->data > key)
			return insertr(root->_left, key);
		else if (root->data < key)
			return insertr(root->_right, key);
		else
			return false;
	}
public:
	bool InsertR(const T& key)
	{
		return insertr(root, key);
	}

删除函数递归实现

//节点的删除递归实现
protected:
	bool eraser(Node* &root, const T& key)
	{
		if (root == nullptr)
			return false;
 
		if (root->data < key)
		{
			return eraser(root->_right, key);
		}
		else if (root->data > key)
		{
			return eraser(root->_left, key);
		}
		else
		{
			// 删除
			if (root->_left == nullptr)
			{
				Node* del = root;
				root = root->_right;
				delete del;
 
				return true;
 
			}
			else if (root->_right == nullptr)
			{
				Node* del = root;
				root = root->_left;
				delete del;
 
				return true;
			}
			else
			{
				//以删除右子树的最小节点为例
				Node* pleft = root->_right;
				while (pleft->_left)
				{
					pleft = pleft->_left;
				}
 
				std::swap(root->data, pleft->data);
 
				// 转换成在子树递归删除
				return eraser(root->_right, key);
			}
		}
	}
public:
	bool EraseR(const T& key)
	{
		return eraser(root, key);
	}

拷贝构造和赋值运算符重载

	//拷贝构造函数
protected:
	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newroot = new Node(root->data);
		newroot->_left = copy(root->_left);
		newroot->_right = copy(root->_right);
 
		return newroot;
	}
public:
	BSTree(const BSTree& b)
	{
		root = copy(b.root);
	}
	BSTree(){}//构造函数
	//赋值运算符重载
	BSTree& operator=(BSTree& b)
	{
		std::swap(root, b.root);
		return *this;
	}

搜索二叉树的相关性质及其应用

二叉搜索树的查找

       我们不难发现，搜索二叉树的中序遍历是对应的升序排列，当我们在二叉搜索树中查找某个值的时候，我们却不能简单的认为其查找效率是logn级别的，因为查找效率需要考虑最坏的情况，而我们的logn的效率实际上是理想化的情况，比某个数大和比某个数小的数各占一半，分别在这个数的左右两侧子树上，才有logn级别的效率，但是，若是在最坏的情况下，搜索树变成了类似于单链表式的链状结构，则查找效率就会变成 o(n) 级别的，因此，我们需要对二叉搜索树进行优化才能符合我们的要求，就叫做所谓的平衡搜索二叉树（AVL树，红黑树等），具体我们后面再做讲解。

key-value模型

        实际上，在C++中，key-value模型的例子有很多，比如map，pair等数据结构，它们通常是一个键值，一个值的方式组成，其中，键值作为功能函数的主要参数，相当于数组的下标，有了下标，我们就可以按下标访问任何一个存在的元素，相当于查找等操作，现在，我们想在二叉搜索树中实现key-value模型，此时，我们只需要将本来一个节点存储的一个数据，修改为一个节点可以存储两个数据即可，具体细节见下面的实现：

namespace key_value{
 
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode* _left;
		BSTreeNode* _right;
		K _key;
		V _value;
 
		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};
 
	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}
 
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				parent = cur;
 
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
 
			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
 
			return true;
		}
 
		Node* 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 cur;
				}
			}
 
			return nullptr;
		}
 
		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
				{
					// 准备删除  
					if (cur->_left == nullptr)
					{//左为空
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
					}
					else if (cur->_right == nullptr)
					{//右为空
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
					}
					else
					{//左右都不为空
 
						// 右树的最小节点(最左节点)
						Node* parent = cur;
						Node* subLeft = cur->_right;
						while (subLeft->_left)
						{
							parent = subLeft;
							subLeft = subLeft->_left;
						}
 
						swap(cur->_key, subLeft->_key);
 
						if (subLeft == parent->_left)
							parent->_left = subLeft->_right;
						else
							parent->_right = subLeft->_right;
					}
 
					return true;
				}
			}
 
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			std::cout << std::endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
 
			_InOrder(root->_left);
			std::cout << root->_key << ":" << root->_value << std::endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}

       以上就是二叉搜索树的初阶内容了，我们后续在学习map和set时还会使用二叉搜索树来实现，具体我们后面再来分析，下一篇，我们将讲解一些二叉树的相关例题，敬请期待~

       要做一个情绪稳定的成年人，。烦躁的时候千万不要讲话，也不要做任何决定，就安静的待一会。当你内心足够坚定的时候，谁都没有办法影响你的情绪。经历的越多，反而明白的更多，把期待降低，把依赖变少，努力把生活变成自己想要的样子。