从零开始的C++（十六）

二叉搜索树：

特点：

1.左子树的值小于根的值

2.右子树的值大于根的值

3.左右子树均是二叉搜索树。

用处：

中序遍历可以得到有序排列。

二叉搜索树的模拟实现：

主要包括插入、删除、查找、遍历。

1.二叉树的结点

template<class K, class V>
	class BSTreeNode
	{   
	public:
		BSTreeNode()
		{
 
		}
 
		BSTreeNode(const K& key, const V& value)
			:_key(key)
			, _value(value)
		{
 
		}
 
		K _key;
		V _value;
		BSTreeNode* _left;
		BSTreeNode* _right;
	};
 
 
 

结点包括两个结点指针，一个K类型的变量，一个V类型的变量。此处K类型一般用于结点之间的大小比较，V类型用于存放某些相关信息。一般可以通过K查找V。

2.搜索二叉树的实现

1.插入：

bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}
			else
			{
				Node* parent = nullptr;
				Node* cur = _root;
				while (cur != nullptr)
				{
					if (cur->_key < key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else if (cur->_key > key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else
					{
						return false;
					}
				}
 
				//判断左右
				if (parent->_key < key)
				{
					parent->_right = new Node(key, value);
				}
				else
				{
					parent->_left = new Node(key, value);
 
				}
				return true;
			}
		}

对于插入，需要判断当前是否是空树，若是空树则只需要给_root开辟一个空间，并赋值即可。

若是非空树，则需要确定插入的位置。由于搜索二叉树具有左结点值小于根结点，右节点值大于根节点的特性，因此可以快速确定插入位置。而parent指向插入位置的父节点，通过判断插入parent指向结点的左右即可完成插入。

2.删除

bool _Erase(Node*root,const K& key)
		{
 
			//先找结点
			Node* cur = root;
			Node* parent = nullptr;
			while (cur != nullptr)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//找到的情况
					//1.左子树为空
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							parent = cur;
							_root = _root->_right;
							delete parent;
							parent = nullptr;
							return true;
						}
						else
						{
							if (parent->_key < cur->_key)
							{
								parent->_right = cur->_right;
 
							}
							else
							{
								parent->_left = cur->_right;
							}
							delete cur;
							cur = nullptr;
							return true;
						}
					}
					//2.右子树为空
					if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							parent = _root;
							_root = _root->_left;
							delete parent;
						    parent = nullptr;
							return true;
						}
						else
						{
							if (parent->_key < cur->_key)
							{
								parent->_right = cur->_left;
 
							}
							else
							{
								parent->_left = cur->_left;
							}
							delete cur;
							cur = nullptr;
							return true;
						}
					}
					//3.左右子树均不为空
					//找cur右侧最小结点,保存在min中
					Node* min = cur->_right;
					Node* minparent = cur;
					while (min->_left != nullptr)
					{   
						minparent = min;
						min = min->_left;
					}
					swap(cur->_key, min->_key);
					swap(cur->_value, min->_value);
					
					if (minparent == cur)
					{
						minparent->_right = min->_right;
					}
					else
					{
						minparent->_left = min->_right;
 
					}
					delete min;
					return true;
				    
 
 
				}
			}
			return false;
		}
 
		bool Erase(const K& key)
		{  
			return _Erase(_root, key);
		}

删除首先需要找到要删除的结点，对于要删除的结点，分三种情况讨论：1.左子树为空。2.右子树为空。3左右子树均不为空。对于前两种情况，需要注意要删除结点是否是根结点，若是根结点，则直接修改根节点的值即可。若不是，则只需要单纯改变要删除结点的父节点的指向即可。对于第三种情况，需要找其右子树的最小结点与其交换（或者也可以找左子树的最大结点与之交换），交换的仅有K和V，对于指针指向不能修改。此处交换完值后，对于要删除的结点那个位置仍符合左子树值小于其，右子树值大于其。然后删除原本右子树的最小结点即可。

3.查找：

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

利用搜索二叉树的特性可以快速完成查找。

4.遍历：

	void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			else
			{
				_InOrder(root->_left);
				cout << root->_key << ":" << root->_value << endl;
				
				_InOrder(root->_right);
 
			}
		}
		void InOrder()
		{   
			//中序遍历
			_InOrder(_root);
			cout << endl;
		}