数据结构: 二叉搜索树

编程入门行业动态更新时间:2024-10-27 20:25:06

数据结构: 二叉搜索树

1.二叉搜索树概念

2.二叉搜索树的操作

3.二叉搜索树的实现

3.1定义BST

3.2功能实现

1.默认成员函数

2.非递归

插入

查找

删除

3.递归

插入

查找

删除

4.二叉搜索树的应用

1.二叉搜索树概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

2.二叉搜索树的操作

1.查找

从根开始查找:

--若查找的值比根节点的值大, 向右查找.

--若比根节点的值小向左查找.

--循环下去,若到nullptr都没找到,返回false

2.插入

a.空树

1.直接将其设为根节点

b.非空树

1.根据二叉搜索树的性质,找到插入的位置

2.在该位置上新生成一个节点,并与父节点链接

(可能是左,也可能是右) 根据这个节点的key与parent的key值判断在那边链接

3.删除

1.找到要删除的节点

2.对该节点进行讨论:

a.该节点没有节点或只有1子个节点

--可以直接删除, 并将它的子节点给它的父点

b.该节点有2个子节点

--找到它左子树最大节点/右子树最小节点来代替它, 并将其删除

3.细节处理

当删除到root->left/right为空的时候, 需要更新头节点

3.二叉搜索树的实现

3.1定义BST

节点

template<class K >
struct BSTreeNode 
{BSTreeNode* _left;BSTreeNode* _right;K _key;//构造函数BSTreeNode(const K& k) :_left(nullptr),_right(nullptr),_key(k){}
};

BSTree

template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public://功能bool Insert(const K& key, const V& value);Node* Find(const K& key);bool Erase(const K& key);void _InOrder(Node* root);void InOrder();private:Node* _root = nullptr;
};

3.2功能实现

1.默认成员函数

构造函数

	//构造函数BSTree():_root(nullptr){}

拷贝构造

	//拷贝构造BSTree(const BSTree<K>& t) {Copy(t._root);}Node* Copy(Node* root){if (root == nullptr)return nullptr;//前序遍历拷贝Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}

赋值运算符

	//赋值运算符BSTree<K>& operator=(BSTree<K> t){swap(_root,t._root);return *this;}

析构函数

	//析构函数~BSTree() {Destory(_root);}void Destory(Node*& root) {if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}

2.非递归

插入

a.空树

--插入的节点直接变为根节点

b.非空树

--根据二叉搜索树性质找到插入的位置

--与父节点链接(讨论parent的key与插入节点的key值来决定链接在parent的那边)
	bool Insert(const K& key){//a.空树(直接将该节点设为根节点)if (_root == nullptr){_root = new Node(key);return true;}//b.非空树//1.找到插入的位置Node* cur = _root;Node* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{return false;}}//2.链接节点cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}

查找

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

删除

找到删除节点的位置

1.删除的节点只有1个节点或者没有节点(直接删除,将cur的子节点给parent)

--没有节点也可以这么操作,相当于把空的子节点给父亲

--若有1个子节点,把该子节点给父亲 (讨论cur的位置,可能是p的左也可能是p的右)

2.删除的节点有2个节点: 找到它左子树最大的节点/ 右子树最小的节点代替它, 并删除

--找到删除的节点

--找到左子树最大节点/右子树最小节点来代替它(把cur存的key变为leftMax/rightMin的key)

--找该节点的过程, cur是在leftMax/rightMin的位置,删除cur节点

(当然要处理它的子节点,讨论一下leftMax是pleftMax左边还是右边)

3.处理空指针: 当删除的节点为cur, 并且cur只有左子树或者只有右子树,更新头节点
	bool Erase(const K& key) {//找到要删除的节点Node* parent = nullptr;Node* cur = _root;while (cur) {if (cur->_key > key) {parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else {//删除//1.左为空if (cur->_left == nullptr) {//处理删除到根节点只有左子树/右子树if (cur == _root) {_root = cur->_right;}else {//将子节点给父节点if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}//2.右为空else if (cur->_right == nullptr) {if (cur = _root) {_root = cur->_left;}else {if (parent->_left == cur) {parent->_left = cur->_left;}else {parent->_right = cur->_left;}}}//3.左右不为空(找左子树最大节点/右子树最小节点)else {Node* pmaxLeft = cur;Node* maxLeft = cur->_left;while (maxLeft->_right) {pmaxLeft = maxLeft;maxLeft = maxLeft->_right;}cur->_key = maxLeft->_key;//把maxLeft的子节点交给其parent,然后删除maxLeftif (pmaxLeft->_left == maxLeft) {pmaxLeft->_left = maxLeft->_left;}else {pmaxLeft->_right = maxLeft->_left;}delete maxLeft;}return true;}}return false;}

3.递归

插入

	//1.插入bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){return _InsertR(root->_left, key);}else if (root->_key < key){return _InsertR(root->_right, key);}}

查找

根据二叉搜索树的性质查找:

	//2.查找bool _FindR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key == key)return true;if (root->_key > key)return _FindR(root->_left, key);elsereturn _FindR(root->_right, key);}

删除

	//3.删除bool _EraseR(Node*& root, const K& key) {if (root == nullptr)return false;//找到要删除的节点if (root->_key > key) {return _EraseR(root->_left, key);}else if (root->_key < key) {return _EraseR(root->_right, key);}else {//删除Node* del = root;//1.左为空if (root->_left == nullptr) {root = root->_right;}//2.右为空else if (root->_right == nullptr) {root = root->_left;}//3.左右不为空else {Node* minRight = root->_right;while (minRight->_left) {minRight = minRight->_left;}swap(root->_key,minRight->_key );//转换为在它的右子树去删除return _EraseR(root->_right,key);}delete del;return true;}}

效果:

4.二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

示例

英汉词典

统计次数