二叉搜索数

二叉搜索数概念

**二叉搜索数（BST Binary Search Tree)😗*一颗二叉树，可以为空或者不为空，满足以下性质：

1. 若左子树不为空，则左子树上的所有节点的值小于根节点的值。
2. 若右子树不为空，则右子树上所有节点的值大于根节点的值。
3. 左右子树均为二叉搜索树

模拟实现

基本结构

节点的结构体TreeNode

template<class T>
struct TreeNode
{

	TreeNode(const T& data = T())
		: _pLeft(nullptr), _pRight(nullptr), _data(data)
	{}
	TreeNode<T>* _pLeft;
	TreeNode<T>* _pRight;
	T _data;
};

二叉搜索树的类

template<class T>
class BSTree
{
	typedef TreeNode<T>* pNode;
	typedef TreeNode<T> Node;
public:
	pNode _pRoot;
    

2.构造与析构

BSTree() : _pRoot(nullptr)
	{}
	~BSTree()
	{
		BSTreeDestroy(_pRoot);
	}
	void BSTreeDestroy(pNode obj)
	{
		
		if (!obj)
		{
			return;
	}
		BSTreeDestroy(obj->_pLeft);
		BSTreeDestroy(obj->_pRight);
		delete obj;
	}

析构通过递归的方式实现

增删查

二叉搜索树的查找：

• 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
• 最多查找高度次，走到到空，还没找到，这个值不存在。

pNode find(const T& data)
	{
		pNode cur = _pRoot;
		while (data <= (cur->_data)&&cur!=nullptr)
		{
			if (T == cur->_data)
			{
				return cur;
		}
			cur = cur->_pLeft;
		}
		while (cur)
		{
			if (data == cur->_data)
			{
				return cur;
			}
			cur = cur->_pRight;
		}
		return nullptr;
			
	}

二叉搜索树的插入

插入的具体过程如下：
树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点

bool Insert(const T& data)
	{
		// 如果树为空，直接插入
		if (nullptr == _pRoot)
		{
			_pRoot = new Node(data);
			return true;
		}
		// 按照二叉搜索树的性质查找data在树中的插入位置
		pNode pCur = _pRoot;
		// 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置
		pNode pParent = nullptr;
		while (pCur)
		{
			pParent = pCur;
			if (data < pCur->_data)
				pCur = pCur->_pLeft;
			else if (data > pCur->_data)
				pCur = pCur->_pRight; // 元素已经在树中存在
			else
				return false;
		}
		// 插入元素
		pCur = new Node(data);
		if (data < pParent->_data)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;
		return true;
	}

二叉搜索树的删除

分几种情况

• 如果被删除节点只有左孩子节点或者没有左右孩子节点则直接删除
• 如果被删除节点只有右孩子节点或者没有左右孩子节点直接删除
• 如果被删除节点同时拥有左右孩子节点则，从左子树中找到最大值或者从右子树中找到最小值替换被删除节点后，再删除。因为左子树的最大值也一定小于右子树的所有值的同时也大于左子树所有值。同理，右子树的最小值一定大于左子树所有的值并且小于右子树所有的值这样替换之后仍然是一个二叉搜索树。

bool Erase(const T& data)
	{
		// 如果树为空，删除失败
		if (nullptr == _pRoot)
			return false;
		// 查找在data在树中的位置
		pNode pCur = _pRoot;
		pNode pParent = nullptr;
		while (pCur)
		{
			if (data == pCur->_data)
				break;
			else if (data < pCur->_data)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
		}
		// data不在二叉搜索树中，无法删除
		if (nullptr == pCur)
			return false;
		
		if (nullptr == pCur->_pRight)
		{
			// 当前节点只有左孩子或者左孩子为空---可直接删除
			pParent->_pLeft = pCur->_pLeft;
			delete pCur;
			
		}
		else if (nullptr == pCur->_pLeft)
		{
			pParent->_pRight = pCur->_pRight;
			// 当前节点只有右孩子---可直接删除
			delete pCur;
			
		}
		else
		{
			pNode pdel = pCur;

			while (pCur->_pLeft)
			{
				pCur = pCur->_pLeft->_pRight;
			}
			std::swap(*pCur, *pdel);
			delete pdel;
		}
		return true;
	}

3.中序遍历二叉搜索树

中序遍历一个二叉搜索树一定是有序的

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

		_InOrder(root->_pLeft);
		cout << ":" << root->_data << endl;
		_InOrder(root->_pRight);
	}
}