数据结构——二叉搜索树

一、二叉搜索树概念

二叉搜索树又叫二叉排序树，它或是空树，或是具有以下性质的二叉树：

（1）若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值；

（2）若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值；

（3）它的左右子树也分别为二叉搜索树。

二、二叉搜索树操作

1.二叉搜索树的查找

（1）若根节点为空，则直接返回false，否则进行后续操作；

（2）如果根节点key==查找key，返回ture，否则进行后续操作；

（3）若根节点key>查找key，则在其左子树内进行查找，否则在其右子树内进行查找；

（4）递归上述过程。

2.二叉搜索树的插入

（1）若树为空，则直接插入；

（2）若树不为空，则按二叉搜索树性质查找插入位置，然后插入。

3.二叉搜索树的删除

首先查找待删除元素是否在二叉搜索树中，没有则直接返回，否则要删除的节点可分为以下四种情况：

（1）待删除节点无孩子节点；

（2）待删除节点只有左孩子；

（3）待删除节点只有右孩子；

（4）待删除节点左右孩子都有。

删除方法：

情况（1）：删除方法与情况（2）和（3）相同；

情况（2）：删除该节点，并使被删除节点的双亲节点指向被删除节点的左孩子节点；

情况（3）：删除该节点，并使被删除节点的双亲节点指向被删除节点的右孩子；

情况（4）：在它的右子树中寻找中序下的第一个节点（值最小的节点），用它的值覆盖掉被删除节点，在处理该节点的删除问题。或找它左子树中最大的节点。

三、二叉搜索的实现

1.代码实现

template<class T>
struct BSTNode {
	BSTNode(const T& value = T())
		: _left(nullptr)
		, _right(nullptr)
		, _value(value)
	{}

	BSTNode<T>* _left;
	BSTNode<T>* _right;
	T _value;
};

//约定value唯一
template<class T>
class BinarySearchTree {
	typedef BSTNode<T> Node;
public:
	BinarySearchTree()
		: _root(nullptr)
	{}

	~BinarySearchTree() {
		Destroy(_root);
	}

	//插入
	bool Insert(const T& value) {
		//空树
		if (_root == nullptr) {
			_root = new Node(value);
			return true;
		}
		//非空
		Node* cur = _root;
		Node* parent = nullptr;//保存cur双亲节点
		//查找插入位置
		while (cur) {
			parent = cur;
			if (value < cur->_value) {
				cur = cur->_left;
			}
			else if (value > cur->_value) {
				cur = cur->_right;
			}
			else {//待插入节点已存在
				return false;
			}
		}
		//插入新节点
		cur = new Node(value);
		if (value > parent->_value) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		return true;
	}

	//查找
	Node* Find(const T& value) {
		Node* cur = _root;
		while (cur) {
			if (value == cur->_value) {
				return cur;
			}
			else if (value < cur->_value) {
				cur = cur->_left;
			}
			else {
				cur = cur->_right;
			}
		}
		return cur;
	}

	//删除
	bool Erase(const T& value) {
		if (_root == nullptr) return false;
		Node* cur = _root;
		Node* parent = nullptr;
		//查找待删除节点
		while (cur) {
			//parent = cur;不能在这里记录双亲节点，因为有可能cur已经是待删除节点，会直接break
			if (value == cur->_value) {
				break;
			}
			else if (value < cur->_value) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				parent = cur;
				cur = cur->_right;
			}
		}
		if (cur == nullptr) return false;//没有待删除节点
		//删除节点
		if (cur->_left == nullptr) {//情况1和2
			if (parent == nullptr) {//是根节点且左孩子为空
				_root = cur->_right;
			}
			else {//不是根节点
				if (cur == parent->_left) parent->_left = cur->_right;
				else parent->_right = cur->_right;
			}
			delete cur;
		}
		else if (cur->_right == nullptr) {//情况1和3
			if (parent == nullptr) {//是根节点且右孩子为空
				_root = cur->_left;
			}
			else {//不是根节点
				if (cur == parent->_left) parent->_left = cur->_left;
				else parent->_right = cur->_left;
			}
			delete cur;
		}
		else {//情况4
			//查找该节点右子树最小值(或左子树的最大值)
			Node* prev = cur;
			Node* node = cur->_right;
			while (node->_left) {
				prev = node;
				node = node->_left;
			}
			//覆盖节点值
			cur->_value = node->_value;
			//删除节点，该节点的左孩子肯定为空
			if (node == prev->_left) prev->_left = node->_right;
			else prev->_right = node->_right;
			delete node;
		}
		return true;
	}


	//中序遍历
	void InOrder() {
		_InOrder(_root);
		std::cout << std::endl;
	}


private:
	//中序遍历
	void _InOrder(Node* root) {
		if (root == nullptr) return;
		_InOrder(root->_left);
		std::cout << root->_value << " ";
		_InOrder(root->_right);
	}
	//销毁
	void Destroy(Node*& root) {
		//利用后续遍历销毁
		if (root == nullptr) return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

private:
	Node* _root;
};