当前位置: 首页> 科技> IT业 > 【数据结构】二叉搜索树

【数据结构】二叉搜索树

时间:2025/7/11 1:00:06来源:https://blog.csdn.net/2301_80277275/article/details/140385368 浏览次数:0次

目录

1、二叉搜索树的概念

2、二叉搜索树的实现

2.1 二叉搜索树的查找

2.2 二叉搜索树的插入

2.3 二叉搜索树的中序遍历

2.4 二叉搜索树的删除

3、二叉搜索树的应用

3.1 K模型

3.2 KV模型

4、二叉搜索树的性能分析


1、二叉搜索树的概念

2、二叉搜索树的实现

2.1 二叉搜索树的查找

查找规则是:1. 从根开始比较,比根大则取根的右子树查找,比根小则去根的左子树查找

                      2.做多查找高度次,走到空,还没找到,则这个值不存在

首先,创建一个结点

template<class K>
struct BSTNode // 二叉搜索树的结点
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};
bool Find(const K& key)
{Node* cur = _root;while (cur) // 不为空时就继续找{if (cur->_key < key) cur = cur->_right;else if (cur->_key > key) cur = cur->_left;else return true; // 找到了返回true}return false; // 没找到返回false
}

2.2 二叉搜索树的插入

首先,需要先判断一下这颗二叉搜索树是否为空,若是空,则直接创建一个结点,结点的值赋值为要插入的值,并将_root指向这个结点

若不为空,则按二叉搜索树的性质往下查找,从根节点开始往下查找,当前遍历到的结点的值小于插入的值,则到当前节点的右子树查找,当前遍历到的结点的值大于插入的值,则到当前节点的左子树查找,直到遍历到的结点为空,那么这个位置就是插入的位置

注意,一定要记录当前遍历到的结点的父节点,因为当遍历到的结点为空,要插入时,需要知道遍历到的结点的父节点才能插入

然后,遍历到的结点为空时,这时候只知道其父节点,但并不知道遍历到的位置是其父节点的左孩子还是右孩子,所以还需要用插入的那个值与父节点的值比较一下,以判断是父节点的左孩子还是右孩子

bool Insert(const K& key)
{// 判断根节点是否为空if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}Node* newNode = new Node(key);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;
}

注意,二叉搜索树是不允许有重复的元素的,所以会设计一个bool返回值,当遍历二叉树时,若是找到了与要插入的值相同的值,则不进行插入,并返回false 

2.3 二叉搜索树的中序遍历

二叉搜索树也叫二叉排序树,正是因为二叉搜索树按照中序遍历打印出来后吗,是有序的

中序遍历是使用递归实现的,但是根节点是private的成员变量,外部没办法直接获取。此时有两种解决方法,第一种是在类中写一个函数GetRoot,第二种是写一个子函数,这里采用写子函数的方法

template<class K>
class BSTree
{typedef BSTNode<K> Node;
public:bool Find(const K& key){Node* cur = _root;while (cur) // 不为空时就继续找{if (cur->_key < key) cur = cur->_right;else if (cur->_key > key) cur = cur->_left;else return true; // 找到了返回true}return false; // 没找到返回false}bool Insert(const K& key){// 判断根节点是否为空if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}Node* newNode = new Node(key);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}Node* _root = nullptr;
};

2.4 二叉搜索树的删除

首先,需要先找到需要删除的这个结点,所以函数需要有一个bool返回值,当找到了就进行删除操作,若没找到,则返回false。并且需要记录遍历到的位置的父亲结点

找到需要删除的结点后,会有3种情况:1. 要删除的结点没有孩子

                                                               2. 要删除的结点有1个孩子

                                                               3. 要删除的结点有2个孩子 

此时我们会发现,这两种是可以合成为一种的。因为当我们找到要删除的结点后,如果这个结点有一个孩子是空,那么我们就是用另一个孩子去替换掉这个结点

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else // 此时已经找到了要删除的结点{// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点if (cur->_left == nullptr){// 判断cur是父亲的左孩子还是右孩子if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;delete cur;return true;}// 要删除的结点有两个孩子else{// 先去右子树中寻找值最小的结点,也就是右子树最左边的那个结点Node* rightMin = cur->_right;Node* rightMinP = nullptr;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;rightMinP->_left = rightMin->_right;delete rightMin;return true;}}}return false;
}

此时容易写出这样的代码,但是这是有问题的,问题在于处理要删除的结点有两个孩子时

问题1:我们将rightMinP初始化为空,如果我们要删除的结点是6,那么rightMin初始化就是7,不会进入循环,rightMinP仍然是空,后面还有解引用就会出错,也很容易发现,实际上要删除的结点激素rightMin的父节点,也就是rightMinP直接初始化为cur即可

问题2:我们将rightMin的值与cur替换后,此时需要将rightMin的孩子给其父节点,前面分析过了rightMin的孩子最多只有一个(因为左孩子一定为空),上面的代码是直接将rightMin的右孩子给其父节点的左孩子,因为是找的cur的右子树最左边的结点,所以很容易就写成上面那样,这样是符合删除3的,但是对于删除6是不满足的,因为删除6并没有进去cur的右子树中一直往左边找,所以应该修改成判断一下rightMin在rightMinP的左边还是右边,然后将rightMin的右孩子替换到rightMin的位置

template<class K>
struct BSTNode // 二叉搜索树的结点
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};
template<class K>
class BSTree
{typedef BSTNode<K> Node;
public:bool Find(const K& key){Node* cur = _root;while (cur) // 不为空时就继续找{if (cur->_key < key) cur = cur->_right;else if (cur->_key > key) cur = cur->_left;else return true; // 找到了返回true}return false; // 没找到返回false}bool Insert(const K& key){// 判断根节点是否为空if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}Node* newNode = new Node(key);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;}void InOrder(){_InOrder(_root);}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else // 此时已经找到了要删除的结点{// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点if (cur->_left == nullptr){// 判断cur是父亲的左孩子还是右孩子if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;delete cur;return true;}// 要删除的结点有两个孩子else{// 先去右子树中寻找值最小的结点,也就是右子树最左边的那个结点Node* rightMin = cur->_right;Node* rightMinP = cur;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if(rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}
private:void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}Node* _root = nullptr;
};

3、二叉搜索树的应用

3.1 K模型

K模型就是二叉搜索树的结点中只存放一个有效值

上面实现的就是K模型的二叉搜索树

K模型主要用来处理在不在的问题。如门禁系统,只需要判断一个人在不在门禁系统中。又如检查英文小说中是否有错误单词,只需要判断一个英文单词是否在词库中

3.2 KV模型

KV模型就是二叉搜索树的结点中存放两个有效值。每一个关键码key,都有与之对应的值value,即<key,value>的键值对

KV模型主要用来处理通过一个值(key)找另一个值(value)的问题。如简单词典、车库收费系统、统计单词出现的次数

对我们上面的二叉搜索树稍作修改,就能得到KV模型的二叉搜索树

1. 结点模板和类模板都增加一个模板参数

2. 插入结点时参数多一个value,不过比较时仍然用key比较

3. 查找时也只给key即可,不过现在需要返回的是结点的指针,因为找到了需要获取里面的值

4. 其余没有变化

KV模型的二叉搜索树仍然是不能有重复的key值的

template<class K,class V>
struct BSTNode_V // 二叉搜索树的结点
{K _key;V _value;BSTNode_V<K,V>* _left;BSTNode_V<K,V>* _right;BSTNode_V(const K& key,const V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}
};
template<class K,class V>
class BSTree_V
{typedef BSTNode_V<K,V> Node;
public:Node* Find(const K& key){Node* cur = _root;while (cur) // 不为空时就继续找{if (cur->_key < key) cur = cur->_right;else if (cur->_key > key) cur = cur->_left;else return cur; // 找到了返回该结点的指针}return nullptr; // 没找到返回空}bool Insert(const K& key,const V& value){// 判断根节点是否为空if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;}Node* newNode = new Node(key, value);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;}void InOrder(){_InOrder(_root);}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else // 此时已经找到了要删除的结点{// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点if (cur->_left == nullptr){// 判断cur是父亲的左孩子还是右孩子if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;delete cur;return true;}// 要删除的结点有两个孩子else{// 先去右子树中寻找值最小的结点,也就是右子树最左边的那个结点Node* rightMin = cur->_right;Node* rightMinP = cur;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}
private:void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << "--" << _root->_value << " ";_InOrder(_root->_right);}Node* _root = nullptr;
};

利用KV模型实现一个简易的词典

void dictionary()
{BSTree_V<string, string> dict;dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("insert", "插入");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret) cout << "->" << ret->_value << endl;else cout << "无此单词,请重新输入" << endl;}
}

利用KV模型来记录每种水果的个数

4、二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。

但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:

最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:O(logN)

最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:O(N)

所以二叉搜索树并不是完美的,当其变成接近与单支树的情况时,时间复杂度是比较高的,所以引入的平衡二叉搜索树(AVL树和红黑树)。在内存中AVL树和红黑树已经够用了,但是在磁盘上仍然是不够的,所以又引入了B树家族

关键字:【数据结构】二叉搜索树

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: