基于中序有序的二叉搜索树

什么是二叉搜索树

二叉搜索树是普通二叉树的升级，普通二叉树除了存储数据以外好像没有别的优势了，但是二叉搜索树不同，如果对搜索树采用中序遍历得到的结果是一串有序的数字。

二叉搜索树又称为二叉排序树，它要么是一棵空树，要么是一棵具有以下特点的树：

1.如果它的左子树不为空，那么它左子树上所有节点的值都小于根节点的值 2.如果它的右子树不为空，那么它右子树上所有节点的值都小于根节点的值 3.它的左右子树也是一棵二叉搜索树

它的结构如下：

代码语言：javascript复制

template<class K>
struct  BSTreeNode
{
	 
	//树的节点包含它的左子树和右子树指针以及这个节点中的值
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	//来个构造函数高一下子
	BSTreeNode(int key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
class BSTree
{
public:
    typedef BSTreeNode<K> Node;
private:  
    Node*_root；
};

二叉搜索树的中序遍历

因为中序遍历得到的结果是一串有序的数字列，所以对于二叉搜索树而言中序遍历才是王道。但是因为中序遍历要从根节点开始，也就说要给函数传根节点，但是根节点作为成员变量是私有的，所以这里采用了嵌套的方式(将真正的中序遍历函数私有化，放出一个公有的调用接口）：

代码语言：javascript复制

void  Inorder()
		{
			//中序遍历
			_Inorder(_root);
			cout << endl;
		}

	private:
		//因为中序遍历需要根作为参数，为了保持封装，在这里嵌套一下
		void _Inorder(Node *root)
		{
			if (root == nullptr)
				return;

			_Inorder(root->_left);
			cout << root->_key << " ";
			_Inorder(root->_right);
		}

二叉搜索树的查找

在一棵二叉搜索树中搜索一个元素，最坏的结果也就是O(N)，但如果这个搜索树一个接近完全二叉树的情况，则只需要查找高度次。

如果是一棵接近完全二叉，查找复杂度为O(logN)，目前我学过的查找中只有二分能达到这样的效率，但是二分有诸多限制，反而不如搜索二叉树来的强大。 所以后面还有平衡二叉树等对结果做进一步的限制，能大大的提升查找的效率

查找的非递归写法

在搜索树中查找某一个值，如果这个值比根节点的值要小，就往根的左子树中找；如果比根节点的值要大，就往右子树中找。

代码语言：javascript复制

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

查找的递归写法

代码语言：javascript复制

//为了不破坏封装，这个函数要被设置成私有的	
Node* _FindR(Node* root, const K& val)
{
	//递归式查找
	if (root == nullptr)
		return nullptr;
	if (root->_key > val)
	{
		return _FindR(root->_left, val);
	}
	else if (root->_key < val)
	{
		return _FindR(root->_right, val);
	}
	return root;
}

//这个是暴露在外面的公有接口
bool FindR(const K& val)
{
	return _FindR(_root, val) == nullptr ? false : true;
}

二叉搜索树的插入

向搜索树中插入不能破坏搜索树的结构，所以不能插入和树种元素相同的值

非递归

代码语言：javascript复制

		//二叉搜索树中序遍历结果是有序的数列，不允许往其中插入相同的值，插入删除不允许破坏结构
		//它左孩子的值比根小，右孩子比根大
		bool Insert(const K& key)
		{
			//插入，分为空树插入和非空树插入
			if (_root == nullptr)
			{
				_root = new  Node(key);
				return true;
			}
			else
			{
				//如果要插入的这个值比当前值要大就往右边走，否则就往左边走
				Node* cur = _root;
				Node* parent = cur;

				while (cur)
				{
					if (cur->_key > key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else if (cur->_key < key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else
					{
						return false;//不允许插入相同的值
					}
					
				}
				//找到要插入的位置了，将值插入进去
				cur = new Node(key);
				//还要判断一下把这个节点链接在parent的左边还是右边
				if (parent->_key > key)
					parent->_left = cur;
				else if (parent->_key < key)
					parent->_right = cur;
			}
			return true;
		}

1.如果是向空树中插入，就直接new一个新节点作为根节点 2.如果是向非空树种插入，首先要找到插入位置，如果在寻找位置的时候发现相同值，直接返回false 3.找到合适位置以后，要将该节点与树链接起来，所以要提前准备一个父节点指针标记插入位置的父节点

递归

递归写法的唯一难处就是在于任何标记插入位置的父节点，这里我们可以采用引用的方式，这个引用用到这里真是妙绝

代码语言：javascript复制

//递归插入的公共接口
bool InsertR(const K&val)
{
	return _InsertR(_root, val);
}

//递归插入的私有函数
bool _InsertR(Node*& root, const K& val)//这里这个引用巨tm牛逼
{
	if (root == nullptr)
	{
		//空就直接插入
		root = new Node(val);
		return true;
	}

	Node* cur = root;
	while (cur)
	{
		if (cur->_key > val)
			return _InsertR(cur->_left, val);
		else if (cur->_key < val)
			return _InsertR(cur->_right, val);
		else
			return false;//不允许相同的元素插入
	}
}

这里为什么给一个引用就能直接链接上呢？主要还是因为这一层的root是上一层root->left或者root->right的别名

二叉搜索树的删除

删除操作是二叉搜索树种最难的一个，因为它涉及到的情况相对比较多

1.如果这个要被删除的节点有一个子树是空树，那么只要将不为空的子树交给被删除节点的父节点即可（这种方法又叫托孤），当然也不能排除这个要被删除的节点是根节点 2.如果这个被删除的节点的左右子树都不为空，那么就不能直接删除，我采用的是替换法删除，找该节点左子树中的最大值或者右子树的最小值作为替换值，然后将替换值的那个节点删除

非递归

代码语言：javascript复制

bool Erase(const K& val)
{
	//要删除这个节点，首先要找到这个节点
	Node* cur = _root;
	Node* parent =cur;
	while (cur)
	{

		if (cur->_key > val)
		{
			parent = cur;
			cur = cur->_left;

		}
		else if (cur->_key < val)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			//这是找到节点了,开始删除，删除大概可以分为两种情况：1.它有一个空节点：托孤 2.它没有空节点：替换法删除
			//有一个节点为空，判断是这个节点的哪个节点是空
			if (cur->_left == nullptr)
			{
				//不排除cur是根节点
				if (cur == _root)
                {
					_root = cur->_right;
				}
				else if (parent->_left == cur)//不是根节点，判读一下它是父节点的左孩子还是右孩子
				{
					parent->_left = cur->_right;
				}
				else
				{
					parent->_right = cur->_right;
				}
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else if (parent->_left == cur)
				{
					parent->_left = cur->_left;
				}
				else
				{
					parent->_right = cur->_left;
				}
				delete cur;//要把节点释放掉
			}
			else
			{
				//这是最后一种情况，要删除的节点两边都不为空，要找该节点左子树的最大节点或者右子树的最小节点来替换
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					parent = minRight;
					minRight = minRight->_left;
				}

				//将值替换
				cur->_key = minRight->_key;

				//最左节点可能有右孩子，所以不能直接将最左节点删除
				if (parent->_left == minRight)
					parent->_left = minRight->_right;
				else
					parent->_right = minRight->_right;

				delete minRight;
			}
			return true;
		}
	}
	return false;
}

递归

代码语言：javascript复制

//递归删除的公共接口
bool EraseR(const K& val)
{
	return _EraseR(_root, val);
}

bool _EraseR(Node*& root, const K& val)
{
	if (root == nullptr)
		return false;
	Node* cur = root;
	Node* parent = cur;
    
	if (cur->_key > val)
		return _EraseR(root->_left, val);
	else if (cur->_key < val)
		return _EraseR(root->_right, val);
	else
	{
		//找到节点，删除
		Node* del = root;//因为这里用的是引用的原因，不用再去记录父节点
		if (root->_left == nullptr)
			root = root->_right;
		else if (root->_right == nullptr)
			root = root->_left;
		else
		{
			Node* rightMin = root->_right;
			while (rightMin->_left != nullptr)//找到被删除节点的右树最小节点 
			{
				rightMin = rightMin->_left;
			}
			root->_key = rightMin->_key;//找到了交换key
			//对子树进行递归删除
			return _EraseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归

				
		}
		delete del;
		return true;
	}
}

二叉搜索树的使用场景

k模型

k模型就是以key作为关键码，结构中只需要存储key值即可。key模型的应用场景有很多，比如查找一本书中的错别字（将词库导入树种，再将书种的每个词去树中搜索一遍，找不到是错别字），比如鉴定一个车牌是否是该停车场的用户（只要将登记的车牌导入搜索树中，当有车来的时候将该车的车牌作为key值去树中检索以下即可）等。二叉搜索树就是一种key模型。

代码语言：javascript复制

#pragma once
#include<iostream>
using namespace std;

//写一个二叉搜索树
namespace wbm
{
	template<class K>
	struct  BSTreeNode
	{
	 
		//树的节点包含它的左子树和右子树指针以及这个节点中的值
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		//来个构造函数高一下子
		BSTreeNode(int key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	};

	//有了单个节点，再来搞一下子结构
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:

		~BSTree()
		{
			//循环遍历释放节点，因为要传根节点，这里也考虑使用嵌套
			Destory(_root);
			_root = nullptr;
		}
		 
		
		//二叉搜索树中序遍历结果是有序的数列，不允许往其中插入相同的值，插入删除不允许破坏结构
		//它左孩子的值比根小，右孩子比根大
		bool Insert(const K& key)
		{
			//插入，分为空树插入和非空树插入
			if (_root == nullptr)
			{
				_root = new  Node(key);
				return true;
			}
			else
			{
				//如果要插入的这个值比当前值要大就往右边走，否则就往左边走
				Node* cur = _root;
				Node* parent = cur;

				while (cur)
				{
					if (cur->_key > key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else if (cur->_key < key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else
					{
						return false;//不允许插入相同的值
					}
					
				}
				//找到要插入的位置了，将值插入进去
				cur = new Node(key);
				//还要判断一下把这个节点链接在parent的左边还是右边
				if (parent->_key > key)
					parent->_left = cur;
				else if (parent->_key < key)
					parent->_right = cur;
			}
			return true;
		}

		//递归插入
		bool InsertR(const K&val)
		{
			return _InsertR(_root, val);
		}

		//查找,找到返回节点，找不到返回空
		bool Find(const K& key)
		{
			if (_root == nullptr)
				return false;
			else
			{
				Node* cur = _root;
				while (cur)
				{
					if (cur->_key > key)
						cur = cur->_left;
					else if (cur->_key < key)
						cur = cur->_right;
					else
					{
						return true;
					}
				}
				
				
			}
			return false;
		}

		bool FindR(const K& val)
		{
			return _FindR(_root, val) == nullptr ? false : true;
		}

		bool Erase(const K& val)
		{
			//要删除这个节点，首先要找到这个节点
			Node* cur = _root;
			Node* parent =cur;
			while (cur)
			{

				if (cur->_key > val)
				{
					parent = cur;
					cur = cur->_left;

				}
				else if (cur->_key < val)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					//这是找到节点了,开始删除，删除大概可以分为两种情况：1.它有一个空节点：托孤 2.它没有空节点：替换法删除

					//有一个节点为空，判断是这个节点的哪个节点是空
					if (cur->_left == nullptr)
					{
						//不排除cur是根节点
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else if (parent->_left == cur)//不是根节点，判读一下它是父节点的左孩子还是右孩子
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
						delete cur;//要把节点释放掉
					}
					else
					{
						//这是最后一种情况，要删除的节点两边都不为空，要找该节点左子树的最大节点或者右子树的最小节点来替换
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							parent = minRight;
							minRight = minRight->_left;
						}

						//将值替换
						cur->_key = minRight->_key;

						//最左节点可能有右孩子，所以不能直接将最左节点删除
						if (parent->_left == minRight)
							parent->_left = minRight->_right;
						else
							parent->_right = minRight->_right;

						delete minRight;
					}
					return true;
				}
			}
			return false;
		}

		//删除的递归
		bool EraseR(const K& val)
		{
			return _EraseR(_root, val);
		}

		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* _FindR(Node* root, const K& val)
		{
			//递归式查找
			if (root == nullptr)
				return nullptr;
			if (root->_key > val)
			{
				return _FindR(root->_left, val);
			}
			else if (root->_key < val)
			{
				return _FindR(root->_right, val);
			}
			return root;
		}

		bool _InsertR(Node*& root, const K& val)//这里这个引用巨tm牛逼
		{
			if (root == nullptr)
			{
				//空就直接插入
				root = new Node(val);
				return true;
			}

			Node* cur = root;
			while (cur)
			{
				if (cur->_key > val)
					return _InsertR(cur->_left, val);
				else if (cur->_key < val)
					return _InsertR(cur->_right, val);
				else
					return false;//不允许相同的元素插入
			}
		}

		bool _EraseR(Node*& root, const K& val)
		{
			if (root == nullptr)
				return false;
			Node* cur = root;
			Node* parent = cur;

			if (cur->_key > val)
				return _EraseR(root->_left, val);
			else if (cur->_key < val)
				return _EraseR(root->_right, val);
			else
			{
				//找到节点，删除
				Node* del = root;//因为这里用的是引用的原因，不用再去记录父节点
				if (root->_left == nullptr)
					root = root->_right;
				else if (root->_right == nullptr)
					root = root->_left;
				else
				{
					Node* rightMin = root->_right;
					while (rightMin->_left != nullptr)//找到被删除节点的右树最小节点 
					{
						rightMin = rightMin->_left;
					}
					root->_key = rightMin->_key;//找到了交换key
					//对子树进行递归删除
					return _EraseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归

				
				}
				delete del;
				return true;
			}
		}

		void Destory(Node* root)
		{
			if (root == nullptr)
				return;
			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}
	private:
		Node* _root=nullptr; //不写构造，直接给缺省值
	};

}

kv模型

kv模型其实是一种Key/Value模型，也就是指根据key值去查找value，单这种模型的一个节点中不但要存储key值还需要村粗value。这种模型的使用场景也常见，比如检索一个学生在图书馆借了多少本书（将学号作为key值检索，因为key值和value存储在一起，所以只要搜索到key就可以获取到value）。二叉搜索树不但可以作为key模型，还可以添加一个模板参数作为key/value模型。

代码语言：javascript复制

namespace KV
{
	template <class K,class V>
	struct BSTreeNode
	{
		BSTreeNode(const K& key,const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			,_value(value)
		{}
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
	};
	template <class K,class V>
	struct BSTree
	{
		typedef BSTreeNode<K,V> Node;
		BSTree()
			:_root(nullptr)
		{}
		//插入节点
		bool Insert(const K& key,const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);//BSTreeNode对象中存放key值 
			}
			else
			{
				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);
				//判断插入节点放在parent节点的左子树还是右子树
				if (parent->_key < key)
				{
					parent->_right = cur;
				}
				else
				{
					parent->_left = cur;
				}
			}
			return true;
		}
		bool InsertR(const K& key,const V& value)
		{
			return _InsertR(_root, key, value);
		}
		//中序遍历
		void InOrder()//因为外部取不到_root,所以这里套了一层调用函数
		{
			_InOrder(_root);
			std::cout << std::endl;
		}
		//查找
		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;
		}
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}
		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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了
						{
							_root = _root->_right;
						}
						else
						{
							if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤”
								parent->_left = cur->_right;
							else
								parent->_right = cur->_right;
						}
						delete cur;
					}
					else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空
					{
						if (cur == _root)
						{
							_root = _root->_left;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_left;
							else
								parent->_right = cur->_left;
						}
						delete cur;
					}
					else//被删除节点左右孩子均不为空
					{
						//左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根
						Node* rightMin = cur->_right;//这里选用右树的最小值进行更换
						Node* rightMinParent = cur;
						while (rightMin->_left != nullptr)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}
						//std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢
						cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载
						cur->_value = rightMin->_value;
						if (rightMinParent->_left == rightMin)//两种情况，第一种如图删除8，实际干掉9位置，需要将10的左连至9的右
							rightMinParent->_left = rightMin->_right;
						else if (rightMinParent->_right == rightMin)//第二种如图删除10，实际干掉14，需要将10的右连至14的右
							rightMinParent->_right = rightMin->_right;
						delete rightMin;
					}
					return true;
				}
			}
			return false;
		}
		bool EraseR(const K& key)
		{
			return _EarseR(_root, key);
		}
	private:
		Node* _root;
		void _InOrder(Node* _root)
		{
			if (_root == nullptr)
			{
				return;
			}
			_InOrder(_root->_left);
			std::cout << _root->_key << " "<<_root->_value;
			_InOrder(_root->_right);
		}
		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
				return root;
		}
		bool _InsertR(Node*& root, const K& key, const V& value)//形参是root的引用
		{
			if (root == nullptr)
			{
				root = new Node(key,value);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系
				return true;
			}
			if (root->_key < key)
				return _InsertR(root->_right, key，value);
			else if (root->_key > key)
				return _InsertR(root->_left, key，value);
			else
				return false;
		}
		bool _EarseR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			if (root->_key < key)
				return _EarseR(root->_right, key);
			else if (root->_key > key)
				return _EarseR(root->_left, key);
			else//说明找到了要删除的节点,无需考虑root的父亲为空
			{
				Node* del = root;
				if (root->_left == nullptr)
					root = root->_right;
				else if (root->_right == nullptr)
					root = root->_left;
				else//root左右子树均不为空
				{
					Node* rightMin = root->_right;
					while (rightMin->_left != nullptr)//找到右树最小节点 
					{
						rightMin = rightMin->_left;
					}
					root->_key = rightMin->_key;
					root->_value = rightMin->_value;
					return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归
				}
				delete del;
				return true;
			}
		}
	};
}
void testKV1()//中英互译
{
	KV::BSTree<std::string, std::string> dic;
	dic.Insert("data", "数据");
	dic.Insert("algorithm", "算法");
	dic.Insert("map", "地图、映射");
	dic.Insert("Linux", "一款开源免费的操作系统");
	std::string str;
	while (std::cin >> str)
	{
		KV::BSTreeNode<std::string, std::string>* ret = dic.Find(str);
		if (ret != nullptr)
		{
			std::cout << "中文翻译：" << ret->_value << std::endl;
		}
		else
			std::cout << "查找失败！" << std::endl;
	}
}
void testKV2()//用于统计次数
{
	std::string arr[] = { "数学", "语文", "数学", "语文", "数学", 
		"数学", "英语","数学", "英语", "数学", "英语" };
	KV::BSTree<std::string, int> count;
	for (auto& e : arr)
	{
		KV::BSTreeNode<std::string, int>* ret = count.Find(e);
		if (ret != nullptr)
		{
			ret->_value  ;
		}
		else
		{
			count.Insert(e,1);
		}
	}
	count.InOrder();
}

当然在现实中如果涉及到大量的数据，我想一般都是通过数据来存储的，毕竟如果不是强制定时将数据刷新到磁盘中的话，程序的数据都是在内存中的，一旦断电，就容易发生数据丢失。

key root 遍历 递归 搜索

0 人点赞