二叉搜索树的实现

注意:本篇文章采用c++,在vs2022底下调试

目录

二叉搜索树概念

二叉搜索树节点实现

二叉搜索树的属性设置

二叉搜索树的插入

二叉搜索树的删除

二叉搜索树的Find函数

二叉搜索树的中序遍历

 整体代码

---

二叉搜索树概念

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

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

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

它的左右子树也分别为二叉搜索树

说白了,就是它是一棵排序树,它的左子树都比它小,右子树都比它大,所以它中序遍历以后正好是一个有序的序列

二叉搜索树节点实现

这里采用的是模板的方法实现的节点,节点的每个值都是一个键值对

template<class K, class V>
struct BSTreeNode {
	BSTreeNode(const K& key = K(), const V& value = V())
		:_val(key, value)
		,_left(nullptr)
		,_right(nullptr)
	{}
	BSTreeNode* _left;
	BSTreeNode* _right;
	pair<K, V> _val;
};

二叉搜索树的属性设置

typedef BSTreeNode<K, V> Node;
Node* _root = nullptr;

二叉搜索树的插入

   bool Insert(const K& key, const V& value) {
	Node* cur = new Node(key, value);
		//空树
		if (_root == nullptr) {
			_root = cur;
			return true;
		}
		//非空
		//找cur插入的位置
		Node* prev = cur;  //保存一下cur的值
		cur = _root;
		Node* parent = _root;
		while (cur) {
			if (key > parent->_val.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (key < parent->_val.first) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return false;
			}
		}
        //找到了双亲节点的位置,插入
		cur = prev;
		if (cur->_val.first > parent->_val.first) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		return true;
	}

二叉搜索树的删除

二叉搜索树的删除分为四种情况,待删除节点是叶子节点,只有左孩子,只有右孩子,左右孩子都有,

其中,待删除节点是叶子结点的情况可以和只有左孩子或只有右孩子合并,那就只有三中情况了,

只有左孩子和只有右孩子都好说,直接把它的孩子过继给父母就行了,难的就是左右孩子都有,那就只能找一个替代节点,这个替代节点一般是它的左子树中最大(最右)的那个节点或者是右子树中最小(最左)的那个节点,把那个节点的值放在待删除节点里面,然后删除那个节点

bool Erase(const K& key) {
		if (_root == nullptr) {
			return false;
		}
		//找节点
		Node* delnode = _root;
		Node* parent = nullptr;
		while (delnode) {
			if (delnode->_val.first == key) {
				break;
			}
			else if (delnode->_val.first > key) {
				parent = delnode;
				delnode = delnode->_left;
			}
			else {
				parent = delnode;
				delnode = delnode->_right;
			}
		}
		//没找着
		if (delnode == nullptr) {
			return false;
		}
		//只有右子树或者是叶子节点
		if (delnode->_left == nullptr) {
			if (parent == nullptr) {
				_root = delnode->_right;
				delete delnode;
			}
			else {
				if (delnode == parent->_left) {
					parent->_left = delnode->_right;
					delete delnode;
				}
				else {
					parent->_right = delnode->_right;
					delete delnode;
				}
			}
		}
		//只有左子树
		else if (delnode->_right == nullptr) {
    	//如果delnode是_root节点	
        if (parent == nullptr) {
				_root = delnode->_left;
				delete delnode;
			}
			else {
				if (delnode == parent->_left) {
					parent->_left = delnode->_left;
					delete delnode;
				}
				else {
					parent->_right = delnode->_left;
					delete delnode;
				}
			}
		}
		//左右子树都有
		else {
			Node* firstinorder = delnode->_right;
			parent = delnode;
			//直接删除不好删除,找替代节点
			while (firstinorder->_left) {
				parent = firstinorder;
				firstinorder = firstinorder->_left;
			}
			//把替代节点的val赋值给delnode,然后删除替代节点
			delnode->_val = firstinorder->_val;
			if (firstinorder == parent->_left) {
				parent->_left = firstinorder->_right;
			}
			else {
				parent->_right = firstinorder->_right;
			}
			delete firstinorder;
			return true;
		}
	}

二叉搜索树的Find函数

Node* Find(const K& key) {
		return _Find(_root, key);
}
Node* _Find(const Node* root, const K& key) {
		if (key == root->_val.first) {
			return root;
		}
		Node* cur = _Find(root->_left, key);
		if (cur) {
			return cur;
		}
		cur = _Find(root->_right, key);
		if (cur) {
			return cur;
		}
		return nullptr;
}

二叉搜索树的中序遍历

void InOrder() {
		_InOrder(_root);
}
void _InOrder(Node* root) {
		if (root == nullptr) {
			return;
		}
		cout << root->_val.first << ":" << root->_val.second << endl;
		_InOrder(root->_left);
		_InOrder(root->_right);
}

 整体代码

#include <utility>
using namespace std;

template<class K, class V>
struct BSTreeNode {
	BSTreeNode(const K& key = K(), const V& value = V())
		:_val(key, value)
		,_left(nullptr)
		,_right(nullptr)
	{}
	BSTreeNode* _left;
	BSTreeNode* _right;
	pair<K, V> _val;
};
//约定,value没有一样的
template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value) {
		Node* cur = new Node(key, value);
		//空树
		if (_root == nullptr) {
			_root = cur;
			return true;
		}
		//非空
		//找cur改插入的位置
		Node* prev = cur;
		cur = _root;
		Node* parent = _root;
		while (cur) {
			if (key > parent->_val.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (key < parent->_val.first) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return false;
			}
		}
		cur = prev;
		if (cur->_val.first > parent->_val.first) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		return true;
	}
	Node* Find(const K& key) {
		return _Find(_root, key);
	}
	bool Erase(const K& key) {
		if (_root == nullptr) {
			return false;
		}
		//找节点
		Node* delnode = _root;
		Node* parent = nullptr;
		while (delnode) {
			if (delnode->_val.first == key) {
				break;
			}
			else if (delnode->_val.first > key) {
				parent = delnode;
				delnode = delnode->_left;
			}
			else {
				parent = delnode;
				delnode = delnode->_right;
			}
		}
		//没找着
		if (delnode == nullptr) {
			return false;
		}
		//只有右子树或者是叶子节点
		if (delnode->_left == nullptr) {
			if (parent == nullptr) {
				_root = delnode->_right;
				delete delnode;
			}
			else {
				if (delnode == parent->_left) {
					parent->_left = delnode->_right;
					delete delnode;
				}
				else {
					parent->_right = delnode->_right;
					delete delnode;
				}
			}
		}
		//只有左子树
		else if (delnode->_right == nullptr) {
			if (parent == nullptr) {
				_root = delnode->_left;
				delete delnode;
			}
			else {
				if (delnode == parent->_left) {
					parent->_left = delnode->_left;
					delete delnode;
				}
				else {
					parent->_right = delnode->_left;
					delete delnode;
				}
			}
		}
		//左右子树都有
		else {
			Node* firstinorder = delnode->_right;
			parent = delnode;
			//直接删除不好删除,找替代节点
			while (firstinorder->_left) {
				parent = firstinorder;
				firstinorder = firstinorder->_left;
			}
			//把替代节点的val赋值给delnode,然后删除替代节点
			delnode->_val = firstinorder->_val;
			if (firstinorder == parent->_left) {
				parent->_left = firstinorder->_right;
			}
			else {
				parent->_right = firstinorder->_right;
			}
			delete firstinorder;
			return true;
		}
	}
	
	void InOrder() {
		_InOrder(_root);
	}
private:
	void _InOrder(Node* root) {
		if (root == nullptr) {
			return;
		}
		cout << root->_val.first << ":" << root->_val.second << endl;
		_InOrder(root->_left);
		_InOrder(root->_right);
	}
	Node* _Find(const Node* root, const K& key) {
		if (key == root->_val.first) {
			return root;
		}
		Node* cur = _Find(root->_left, key);
		if (cur) {
			return cur;
		}
		cur = _Find(root->_right, key);
		if (cur) {
			return cur;
		}
		return nullptr;
	}
	Node* _root = nullptr;
};