模拟实现二叉搜索树超详解（C++）

 各位小伙伴，大家好啊！我是bug.今天我们的内容比较简单，就讲讲二叉搜索树的性质和模拟实现：
（代码可能会有一点问题，请各位老铁指正   ）

• 一、  二叉搜索树
• 二、  二叉搜索树的模拟实现

✏️ ✏️ 二叉搜索树（Binary Search Tree）：又名二叉排序树，二叉查找树。空树也是二叉排序树。

性质 ：如果左子树不为空，那么左子树的结点数据均小于根结点的数据。
如果右子树不为空，那么右子树的结点数据均大于根结点的数据。
同时，它的左右子树也是二叉排序树。

 优点：既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。
它的中序遍历可以完成排序的操作。
当其接近于完全二叉树时，其增删查改的时间复杂度为O（logN）。
因为接近完全二叉树时，它的每次操作就相当于二分情况。（如下图）

 缺点：插入数据接近有序时，就会出现极为不平衡的情况，这时候它的增删查改就会退化成O（N）。（如下图）

 延伸：对于二叉排序树，它的结构无疑十分优秀的。但是它的缺点也十分致命，一旦退化，其效率会大幅度降低。所以对此引出了AVL树（高度平衡二叉搜索树）和红黑树，它们都通过各自的规则来对树的平衡进行控制，达到接近完全二叉树，当然它们增删查改的时间复杂度都是O（logN），后面我们会进行模拟实现的。

☀️ ☀️二叉树的查找、插入、删除都可以使用递归和非递归的版本，下面我们会实现。
 二叉搜索树的模拟实现⬇️ ⬇️：

#pragma once

#include
using std::cin;
using std::cout;
using std::endl;

namespace lz
{
	//创建二叉搜索树的结点
	template
	class BSTreeNode
	{
	public:
		BSTreeNode(const T& data = T())
			:_left(nullptr)
			, _right(nullptr)
			, _data(data)
		{}

		BSTreeNode* _left;
		BSTreeNode* _right;
		T _data;
	};

	//二叉搜索树
	template
	class BSTree
	{	
	public:
		//构造
		typedef BSTreeNode Node;

		BSTree(const T& data = T())
			:_root(new Node)
		{
			_root->_data = data;
		}


		//拷贝构造
		BSTree(const BSTree& t)
		{
			_root = copy(t._root);
		}

		//赋值运算符重载
		BSTree& operator=(const BSTree& t)
		{
			BSTree tmp(t);
			std::swap(tmp._root, _root);
			return *this;
		}

		//非递归插入
		bool insert(const T& data)
		{
			Node* cur = _root;
			Node* parent = _root;

			while (cur)
			{
				if (cur->_data > data)//往左边去找
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data < data)//往右边去找
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			Node* newNode = new Node;
			newNode->_data = data;
			//如果root为空
			if (_root == nullptr)
			{
				_root = newNode;
				return true;
			}

			if (data < parent->_data)
			{
				parent->_data = newNode;
				return true;

			}
			else
			{
				parent->_right = newNode;
				return true;

			}

		}

		//递归插入
		bool insertR(const T& data)
		{
			return _insertR(_root, data);
		}

		//非递归查找
		Node* find(const T& data)
		{
			if (_root)
			{
				Node* cur = _root;
				while (cur)
				{
					if (cur->_data > data)
					{
						cur = cur->_left;
					}
					else if (cur->_data < data)
					{
						cur = cur->_right;
					}
					else
					{
						return cur;
					}
				}
			}
		return nullptr;
		}

		//递归查找
		Node* findR(const T& data)
		{
			return _findR(_root, data);
		}

		//非递归删除
		bool erase(const T& data)
		{
			if (_root == nullptr)//root空结点直接返回
			{
				return false;
			}

			Node* cur = _root;
			Node* parent = _root;

			while (cur)
			{
				if (cur->_data > data)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data < data)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					break;
				}
			}

			if (nullptr == cur)//找不到
			{
				return false;
			}

			//cur为_root时
			if (cur == _root)
			{
				//左子树为空
				if (cur->_left == nullptr)
				{
					_root = cur->_right;
					delete cur;
					return true;
				}
				//右子树为空时
				else if (cur->_right == nullptr)
				{
					parent = cur->_left;
					delete cur;
					return true;
				}
				//左右子树都不为空时,到下面进行处理
			}

			if (cur->_left == nullptr)//找到了，左孩子为nullptr时
			{
				if (parent->_left == cur)
				{
					parent->_left = cur->_right;
					delete cur;
					return true;
				}
				else//parent->_right == cur
				{
					parent->_right = cur->_right;
					delete cur;
					return true;
				}
			}
			else //cur->_right == nullptr 找到了，当右孩子为空时
			{
				if (parent->_left == cur)
				{
					parent->_left = cur->_left;
					delete cur;
					return true;
				}
				else//parent->_right == cur
				{
					parent->_right = cur->_left;
					delete cur;
					return true;
				}
			}

			//要删除结点的左右孩子都存在
			//去找左子树的最右边结点
			cur = parent->_left;
			Node* max_parent = parent;

			while (cur->_right)
			{
				max_parent = cur;
				cur = cur->_right;
			}
			//保存最右结点的数据

			max_parent->_data = cur->_data;
			if (max_parent->_left == cur)
			{
				max_parent->_left = cur->_left;
			}
			else if (max_parent->_right == cur)
			{
				max_parent->_right == cur->_left;
			}
			delete cur;

			return true;
		}

		//递归删除
		bool eraseR(const T& data)
		{
			return _eraseR(_root, data);
		}

		//中序遍历
		void inoder()
		{
			inoder(_root);
		}

		//析构
		~BSTree()
		{
			clear(_root);
			_root = nullptr;
		}

private:

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

	//递归插入
	bool _insertR(Node*& root, const T& data)
	{
		if (root == nullptr)
		{
			root = new Node;
			root->_data = data;
			return true;
		}

		if (root->_data > data)
		{
			return _insertR(root->_left, data);
		}

		if (root->_data < data)
		{
			return _insertR(root->_right, data);
		}

		if (root->_data == data)
		{
			return false;
		}
	}

	//递归删除
	bool _eraseR(Node*& root, const T& data)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_data > data)
		{
			return _eraseR(root->_left, data);
		}
		else if (root->_data < data)
		{
			return _eraseR(root->_right, data);
		}
		else
		{
			if (root->_left == nullptr)//左子树为空
			{
				Node* tmp = root;
				root = root->_right;
				delete tmp;
				return true;
			}
			else if (root->_right == nullptr)//右子树为空
			{
				Node* tmp = root;
				root = root->_left;
				delete tmp;
				return true;
			}
			else//左子树和右子树都不为空
			{
				//方法一：非递归
				
				//方法二递归（建议递归，上面的细节太多了）
				Node* max_parent = root;
				Node* max_left = root->_left;
				while (max_left->_right)
				{
					max_parent = max_left;
					max_left = max_left->_right;
				}

				T min = max_left->_data;
				//转换成在root右子树中删除替代结点
				_eraseR(root, min);

				root->_data = min;
				return true;
			}
		}
	}

	//递归查找
	Node* _findR(Node* root, const T& data)
	{

		if (root == nullptr)
		{
			return nullptr;
		}

		if (root->_data > data)
		{
			return _findR(root->_left, data);
		}
		else if (root->_data < data)
		{
			return _findR(root->_right, data);
		}
		else
		{
			return root;
		}
	}

	void clear(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		clear(root->_left);
		clear(root->_right);
		delete root;
	}

	Node* inoder(const Node* cur)
	{
		if (cur == nullptr)
		{
			return nullptr;
		}

		inoder(cur->_left);
		cout << cur->_data << " ";
		inoder(cur->_right);
	}

	private:
		Node* _root;
	};
}

#include"BinarySearchTree.h"

void Test1()
{
	lz::BSTree t(9);
	t.insertR(4);
	t.insertR(11);
	t.insertR(2);
	t.insertR(7);
	t.inoder();
	cout << endl;

	t.eraseR(t.eraseR(4));
	t.eraseR(t.eraseR(11));
	t.eraseR(t.eraseR(2));
	t.eraseR(t.eraseR(4));
	t.inoder();
}

int main()
{
	Test1();

	return 0;
}

 今天的内容到这里就结束了，希望大家有所收获。嘿嘿，我们下期再见！