二叉搜索树

二叉搜索树

二叉搜索树概念

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

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

由于二叉搜索树中，每个结点左子树上所有结点的值都小于该结点的值，右子树上所有结点的值都大于该结点的值，因此对二叉搜索树进行中序遍历后，得到的是升序序列。

二叉搜索树的实现

节点类的实现

在实现二叉搜索树前我们需要先实现二叉搜索树的节点：

• 包含三个成员变量，节点值，右节点指针，左节点指针。
• 构造函数给节点进行初始化。

template<class K>
struct BSTreeeNode
{
	typedef BSTreeNode<K> Node;
	K _data;// 值
	Node* _left;// 左节点
	Node* _right;// 右节点

	BSTreeeNode<K>(const K& data=K())
		:_data(data),_left(nullptr),_right(nullptr)
	{}
};

二叉搜索树函数接口

//二叉搜索树
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//构造函数
	BSTree();

	//析构函数
	~BSTree();

	//拷贝构造函数
	BSTree(const BSTree<K>& tree);

	//赋值运算符重载函数
	BSTree<K>& operator=(BSTree<K> tree);

	//插入函数
	bool Insert(const K& data);

	//查找函数
	Node* Find(const K& data);

	//删除函数
	bool Erase(const K& data);

	//中序遍历
	void InOrder();
private:
	Node* _root; //指向二叉搜索树的根结点
};

中序遍历

为了方便检查其他接口，当我们调用中序遍历接口时，如果遍历的结果是升序的，那么初步判断是接口正确。

	//中序遍历的子函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left); //遍历左子树
		cout << root->_data" "; //遍历根结点
		_InOrder(root->_right); //遍历右子树
	}
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

构造函数

构造函数用于初始化，二叉索搜树建立时为空树。

• 头节点指向空即可

//构造函数
BSTree()
	:_root(nullptr)
{}

拷贝构造函数

拷贝构造函数把另一颗数树的节点进行初始化。

• 实现深拷贝

	Node* _Copy(Node* root)
	{
		if (root == nullptr) //空树直接返回
			return nullptr;

		Node* copyNode = new Node(root->_data); //拷贝根结点
		copyNode->_left = _Copy(root->_left); //拷贝左子树
		copyNode->_right = _Copy(root->_right); //拷贝右子树
		return copyNode; //返回拷贝的树的节点
	}
	//拷贝构造函数
	BSTree(const BSTree<K>& tree)
	{
		_root = _Copy(tree._root); 
	}

赋值运算符重载函数

现代写法，利用传参时调用用拷贝构造函数初始化tree，swap函数交换两个根节点的指针，tree调用析构函数时释放交换后根节点指针的资源，原理就是更好的复用。

	//赋值运算符重载函数
	//现代写法
	BSTree<K>& operator=(BSTree<K> tree) //编译器接收右值的时候自动调用拷贝构造函数
	{
		swap(_root, tree._root); //交换这两个对象的二叉搜索树
		return *this; //支持连续赋值
	}

析构函数

析构函数释放树的所有结点资源。

• 后序遍历的方式释放节点

	void Destory(Node* root)
	{
		if (root == nullptr) //空树无需释放
			return;

		Destory(root->_left); //释放左子树中的结点
		Destory(root->_right); //释放右子树中的结点
		delete root; //释放根结点
	}
	//析构函数
	~BSTree()
	{
		Destory(_root); //释放二叉搜索树中的结点
		_root = nullptr; //及时置空
	}

插入函数

在二叉树搜索里插入一个节点：

1. 如果是空树，插入节点作为根节点。

2. 树不空，按二叉搜索树性质查找插入位置，插入新节点

插入规则：
1.若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中。
2. 若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中。
3. 若待插入结点的值等于根结点的值，则插入结点失败。

非递归实现

	//插入函数
	bool Insert(const K& data)
	{
		if (_root == nullptr) //如果是空树
		{
			_root = new Node(data); //新增节点作为二叉搜索树的根节点
			return true; //插入成功，返回true
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (data < cur->_data) //data值小于当前结点的值
			{
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else if (data > cur->_data) //data值大于当前结点的值
			{
				//往该结点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else //data值等于当前结点的值
			{
				return false; //插入失败，返回false
			}
		}
		// 走到这里说明找到插入位置了

		cur = new Node(data); //申请值为key的结点
		if (data < parent->_data) //key值小于当前parent结点的值
		{
			parent->_left = cur; //将结点连接到parent的左边
		}
		else //key值大于当前parent结点的值
		{
			parent->_right = cur; //将结点连接到parent的右边
		}
		return true; //插入成功，返回true
	}

递归实现

注意：这里的传引用参数，用的非常秀，对root的修改就等于对父节点的右子树指针或者左子树指针的修改。

bool _InsertR(Node*& root, const K& data) 
{
	if (root == nullptr) //空树
	{
		root = new Node(data); //直接申请值为data的结点作为树的根结点
		return true; //插入成功，返回true
	}

	if (data < root->_data) //data值小于根结点的值
	{
		return _InsertR(root->_left, data); //应将结点插入到左子树当中
	}
	else if (data > root->_data) //data值大于根结点的值
	{
		return _InsertR(root->_right, data); //应将结点插入到右子树当中
	}
	else //data值等于根结点的值
	{
		return false; //插入失败，返回false
	}
}
//递归插入函数
bool InsertR(const K& data)
{
	return _InsertR(_root, data); //调用子函数进行插入
}

查找函数

查找的过程与插入的过程类似，插入的过程也需要先查找合适的位置。

非递归实现

//查找函数
Node* Find(const K& data)
{
	Node* cur = _root;
	while (cur)
	{
		if (data < cur->_data) //data值小于该结点的值
		{
			cur = cur->_left; //在该结点的左子树当中查找
		}
		else if (data > cur->_data) //data值大于该结点的值
		{
			cur = cur->_right; //在该结点的右子树当中查找
		}
		else //找到了值为data的结点
		{
			return cur; //查找成功，返回结点地址
		}
	}
	return nullptr; //树为空或查找失败，返回nullptr
}

递归实现

//递归查找函数的子函数
Node* _FindR(Node* root, const K& data)
{
	if (root == nullptr) //树为空
		return nullptr; //查找失败，返回nullptr

	if (data < root->_data) //data值小于根结点的值
	{
		return _FindR(root->_left, data); //在根结点的左子树当中查找
	}
	else if (data > root->_data) //data值大于根结点的值
	{
		return _FindR(root->_right, data); //在根结点的右子树当中查找
	}
	else //data值等于根结点的值
	{
		return root; //查找成功，返回根结点地址
	}
}
//递归查找函数
Node* FindR(const K& data)
{
	return _FindR(_root, data); //在_root当中查找值为data的结点
}

删除函数

非递归实现

若是在二叉树当中没有找到待删除结点，则直接返回false表示删除失败即可，但若是找到了待删除结点，此时就有以下三种情况：

1. 待删除节点的左右子树均为空。
2. 待删除节点的左子树为空或者右子树为空。
3. 待删除节点的左右子树均不为空。

注意：第1种情况待删除的节点为叶子节点，我们可以把叶子节点当成第2种情况去处理。

删除节点前我们需要先找到该节点，然后再按照3种情况分别处理。

//删除函数
	bool Erase(const K& data)
	{
		Node* parent = nullptr; //标记待删除结点的父结点
		Node* cur = _root; //标记待删除结点
		while (cur)
		{
			if (data < cur->_data) //key值小于当前结点的值
			{
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else if (data > cur->_data) //key值大于当前结点的值
			{
				//往该结点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else //找到了待删除结点
			{
				if (cur->_left == nullptr) //1、待删除结点的左子树为空
				{
					// 情况1处理方法
					return true;
				}
				else if (cur->_right == nullptr) //2、待删除结点的右子树为空
				{
				  // 情况2处理方法
					return true;
				}
				else //3、待删除结点的左右子树均不为空
				{
					//情况3处理方法替换法删除
					return true;
				}
			}
		}
		return false; //没有找到待删除结点，删除失败，返回false
	}

下面我们分别对这三种情况进行分析处理：
cur为待删除节点指针，parent为待删除节点父节点指针。
1、待删除结点的左子树为空
a、若parent为空，让根节点指针指向cur的右子树。

b、否则，cur为parent的右子树或者cur为parent的左子树，让parent托管cur的右节点。

if (cur->_left == nullptr) //待删除结点的左子树为空
{
	if (cur == _root) //待删除结点是根结点，此时parent为nullptr
	{
		_root = cur->_right; //二叉搜索树的根结点改为根结点的右孩子即可
	}
	else //待删除结点不是根结点，此时parent不为nullptr
	{
		if (cur == parent->_left) //待删除结点是其父结点的左孩子
		{
			parent->_left = cur->_right; //父结点的左指针指向待删除结点的右子树即可
		}
		else //待删除结点是其父结点的右孩子
		{
			parent->_right = cur->_right; //父结点的右指针指向待删除结点的右子树即可
		}
	}
	delete cur; //释放待删除结点
	return true; //删除成功，返回true
}

2、待删除结点的右子树为空
和情况1类似、

else if (cur->_right == nullptr) //待删除结点的右子树为空
{
	if (cur == _root) //待删除结点是根结点，此时parent为nullptr
	{
		_root = cur->_left; //二叉搜索树的根结点改为根结点的左孩子即可
	}
	else //待删除结点不是根结点，此时parent不为nullptr
	{
		if (cur == parent->_left) //待删除结点是其父结点的左孩子
		{
			parent->_left = cur->_left; //父结点的左指针指向待删除结点的左子树即可
		}
		else //待删除结点是其父结点的右孩子
		{
			parent->_right = cur->_left; //父结点的右指针指向待删除结点的左子树即可
		}
	}
	delete cur; //释放待删除结点
	return true; //删除成功，返回true
}

3、待删除结点的左右子树均不为空
我们使用替换法，找到一个满足大于cur的所有左子树，小于cur的右子树的A节点，cur与A节点替换。
cur的右子树的最小节点和cur的左子树的最大节点都满足。

下面我们演示：cur的右子树的最小节点。
我们把cur的右子树的最小节点定义为minRight，父节点为minParent。找到minRight以后，minRight的左节点一定为空，有节点两种情况，两种情况可以一并处理与情况1和2类似。最后确定minParent是右子树还是左子树托管。

else//待删除结点的左右子树均不为空
{
	//替换法删除
	Node* minParent = cur; //标记待删除结点右子树当中值最小结点的父结点
	Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
	//寻找待删除结点右子树当中值最小的结点
	while (minRight->_left)
	{
		//一直往左走
		minParent = minRight;
		minRight = minRight->_left;
	}
	cur->_data = minRight->_data; //将待删除结点的值改为minRight的值
	//注意一个隐含条件：此时minRight的_left为空
	if (minRight == minParent->_left) //minRight是其父结点的左孩子
	{
		minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可
																		// miRight->_left一定为空
	}
	else //minRight是其父结点的右孩子
	{
		minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可
																		// miRight->_left一定为空
	}
	delete minRight; //释放minRight
	return true; //删除成功，返回true
}

递归实现

bool _EraseR(Node*& root, const K& data)
{
	if (root == nullptr) //空树
		return false; //删除失败，返回false

	if (data < root->_data) //data值小于根结点的值
		return _EraseR(root->_left, data); //待删除结点在根的左子树当中
	else if (data > root->_data) //data值大于根结点的值
		return _EraseR(root->_right, data); //待删除结点在根的右子树当中
	else //找到了待删除结点
	{
		if (root->_left == nullptr) //待删除结点的左子树为空
		{
			Node* del = root; //保存根结点
			root = root->_right; //根的右子树作为二叉树新的根结点
			delete del; //释放根结点
		}
		else if (root->_right == nullptr) //待删除结点的右子树为空
		{
			Node* del = root; //保存根结点
			root = root->_left; //根的左子树作为二叉树新的根结点
			delete del; //释放根结点
		}
		else //待删除结点的左右子树均不为空
		{
			Node* minRight = root->_right; //标记根结点右子树当中值最小的结点
			//寻找根结点右子树当中值最小的结点
			while (minRight->_left)
			{
				//一直往左走
				minRight = minRight->_left;
			}
			K min = minRight->_data; //记录minRight结点的值
			_EraseR(root->_right, min); //删除右子树当中值为min的结点，即删除minRight，
			// 需要从删除结点的右子树查找并删除，是因为minRight在删除结点的右子树的最左子树里。
			root->_data = min; 
			//将根结点的值改为minRight的值，对其进行覆盖相当于删除目标结点了
		}
		return true; //删除成功，返回true
	}
}
//递归删除函数
bool EraseR(const K& data)
{
	return _EraseR(_root, data); //删除_root当中值为data的结点
}

注意：待删除结点的左右子树均不为空的情况处理时我们可以按照非递归的方法写，不过递归的方法更加简洁。

二叉搜索树的应用

1、 K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。K模型解决在不在的场景
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：以单词集合中的每个单词作为key，构建一棵二叉搜索树。在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2、KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。
比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：

• <单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key
• 查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。

样例代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"BSTree.h"
#include
#include
using namespace KV;
void test3()
{
	BSTree<std::string, std::string> tree;
	tree.Insert("苹果", "apple");
	tree.Insert("水", "water");
	for (;;)
	{
		std::string dir;
		std::cout << "请输入查找中：";
		std::cin >> dir;
		BSTreeNode<string, string>* node;
		node = tree.Find(dir);
		if (node != nullptr)
		{
			std::cout << "查找成功" << std::endl;
			std::cout << "查找结果为：" << node->_val << std::endl;
		}
		else
		{
			std::cout << "查找失败，请重新输入" << std::endl;
		}
	}
}
int main()
{
	test3();
	return 0;
}

二叉树搜索树KV模型代码

namespace KV
{
	template<class K,class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K,V> Node;
		K _key;// 键
		V _val;// 值
		Node* _left;// 左节点
		Node* _right;// 右节点

		BSTreeNode<K,V>(const K& key = K(),const V&val=V())
			:_key(key), _left(nullptr), _right(nullptr),_val(val)
		{}
	};

	//二叉搜索树
	template<class K,class V>
	class BSTree
	{
		typedef BSTreeNode<K,V> Node;
	public:
		//构造函数
		BSTree()
			:_root(nullptr)
		{}

		//析构函数
		//释放树中结点
		void Destory(Node* root)
		{
			if (root == nullptr) //空树无需释放
				return;

			Destory(root->_left); //释放左子树中的结点
			Destory(root->_right); //释放右子树中的结点
			delete root; //释放根结点
		}
		//析构函数
		~BSTree()
		{
			Destory(_root); //释放二叉搜索树中的结点
			_root = nullptr; //及时置空
		}

		//拷贝构造函数
		//拷贝树
		Node* _Copy(Node* root)
		{
			if (root == nullptr) //空树直接返回
				return nullptr;

			Node* copyNode = new Node(root->_key,root->_val); //拷贝根结点
			copyNode->_left = _Copy(root->_left); //拷贝左子树
			copyNode->_right = _Copy(root->_right); //拷贝右子树
			return copyNode; //返回拷贝的树
		}
		//拷贝构造函数
		BSTree(const BSTree<K,V>& tree)
		{
			_root = _Copy(tree._root); //拷贝t对象的二叉搜索树
		}


		//赋值运算符重载函数
		//现代写法
		BSTree<K,V>& operator=(BSTree<K,V> tree) //编译器接收右值的时候自动调用拷贝构造函数
		{
			swap(_root, tree._root); //交换这两个对象的二叉搜索树
			return *this; //支持连续赋值
		}

		//插入函数
		bool Insert(const K &key,const V &val)
		{
			if (_root == nullptr) //如果是空树
			{
				_root = new Node(key,val); //新增节点作为二叉搜索树的根节点
				return true; //插入成功，返回true
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key) //key值小于当前结点的值
				{
					//往该结点的左子树走
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key) //key值大于当前结点的值
				{
					//往该结点的右子树走
					parent = cur;
					cur = cur->_right;
				}
				else //key值等于当前结点的值
				{
					return false; //插入失败，返回false
				}
			}
			// 走到这里说明找到插入位置了

			cur = new Node(key,val); //申请值为key的结点
			if (key < parent->_key) //key值小于当前parent结点的值
			{
				parent->_left = cur; //将结点连接到parent的左边
			}
			else //key值大于当前parent结点的值
			{
				parent->_right = cur; //将结点连接到parent的右边
			}
			return true; //插入成功，返回true
		}
	
		//查找函数
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key) //key值小于该结点的值
				{
					cur = cur->_left; //在该结点的左子树当中查找
				}
				else if (key > cur->_key) //key值大于该结点的值
				{
					cur = cur->_right; //在该结点的右子树当中查找
				}
				else //找到了值为key的结点
				{
					return cur; //查找成功，返回结点地址
				}
			}
			return nullptr; //树为空或查找失败，返回nullptr
		}
	
		//删除函数
		bool Erase(const K& key)
		{
			Node* parent = nullptr; //标记待删除结点的父结点
			Node* cur = _root; //标记待删除结点
			while (cur)
			{
				if (key < cur->_key) //key值小于当前结点的值
				{
					//往该结点的左子树走
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key) //key值大于当前结点的值
				{
					//往该结点的右子树走
					parent = cur;
					cur = cur->_right;
				}
				else //找到了待删除结点
				{
					if (cur->_left == nullptr) //待删除结点的左子树为空
					{
						if (cur == _root) //待删除结点是根结点，此时parent为nullptr
						{
							_root = cur->_right; //二叉搜索树的根结点改为根结点的右孩子即可
						}
						else //待删除结点不是根结点，此时parent不为nullptr
						{
							if (cur == parent->_left) //待删除结点是其父结点的左孩子
							{
								parent->_left = cur->_right; //父结点的左指针指向待删除结点的右子树即可
							}
							else //待删除结点是其父结点的右孩子
							{
								parent->_right = cur->_right; //父结点的右指针指向待删除结点的右子树即可
							}
						}
						delete cur; //释放待删除结点
						return true; //删除成功，返回true
					}
					else if (cur->_right == nullptr) //待删除结点的右子树为空
					{
						if (cur == _root) //待删除结点是根结点，此时parent为nullptr
						{
							_root = cur->_left; //二叉搜索树的根结点改为根结点的左孩子即可
						}
						else //待删除结点不是根结点，此时parent不为nullptr
						{
							if (cur == parent->_left) //待删除结点是其父结点的左孩子
							{
								parent->_left = cur->_left; //父结点的左指针指向待删除结点的左子树即可
							}
							else //待删除结点是其父结点的右孩子
							{
								parent->_right = cur->_left; //父结点的右指针指向待删除结点的左子树即可
							}
						}
						delete cur; //释放待删除结点
						return true; //删除成功，返回true
					}
					else //待删除结点的左右子树均不为空
					{
						//替换法删除
						Node* minParent = cur; //标记待删除结点右子树当中值最小结点的父结点
						Node* minRight = cur->_right; //标记待删除结点右子树当中值最小的结点
						//寻找待删除结点右子树当中值最小的结点
						while (minRight->_left)
						{
							//一直往左走
							minParent = minRight;
							minRight = minRight->_left;
						}
						cur->_key = minRight->_key; //将待删除结点的值改为minRight的值
						cur->_val = minRight->_val;
						//注意一个隐含条件：此时minRight的_left为空
						if (minRight == minParent->_left) //minRight是其父结点的左孩子
						{
							minParent->_left = minRight->_right; //父结点的左指针指向minRight的右子树即可
						}
						else //minRight是其父结点的右孩子
						{
							minParent->_right = minRight->_right; //父结点的右指针指向minRight的右子树即可
						}
						delete minRight; //释放minRight
						return true; //删除成功，返回true
					}
				}
			}
			return false; //没有找到待删除结点，删除失败，返回false
		}

		//中序遍历的子函数
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left); //遍历左子树
			cout << root->_key << ":" << root->_val << std::endl; //遍历根结点
			_InOrder(root->_right); //遍历右子树
		}
		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
		}
	private:
		Node* _root; //指向二叉搜索树的根结点
	};
}

二叉搜索树的性能分析

• 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
• 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
• 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

• 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：${\log }_2^N$
• 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：$\frac{N}{2}$

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？后面学习红黑树和AVL树就能优化二叉树的缺陷了。