当前位置：首页 > news >正文

二叉搜索树

news 来源：原创 2025/7/27 18:19:13

概念

代码实现

成员

基本结构

查找

插入

删除

中序遍历

拷贝构造

赋值运算符重载

析构函数

递归实现

递归实现查找

递归实现插入

递归实现删除

概念

关于二叉树的基本结构已经进行过详细剖析，本篇博客将对一种特殊的二叉树进行分析。

二叉树（C语言）_二叉树 csdn-CSDN博客文章浏览阅读1.4k次，点赞22次，收藏21次。帮助读者快速掌握树这一数据结构，了解堆的功能，能够实现堆排序，以及如何再大量数据中快速找到前K个最大元素，如何处理普通二叉树，普通二叉树的遍历等知识。_二叉树 csdnhttps://blog.csdn.net/2401_87944878/article/details/145262931

二叉搜索树在二叉树的基础上，有三个要求。

1）若一个节点的左树不为空，则其左树的所有节点要小于该节点；

2）若一个节点的右树不为空，则其右树的所有节点要大于该节点；

3）一个节点的左右树也是搜索二叉树。

以上就是一个二叉搜索树。

二叉搜索树在对数据进行查找的时候效率很高，对于一个完全二叉树或趋于完全二叉树的结构，其查找的效率可以达到O(logN)，但是如果一个二叉树在使用的时候退化成一个单叉树的时候，其结构就类似于一个链表，查找效率就变成了O(N)。

平衡二叉搜索树会解决搜索二叉树退化的问题。在AVL树中会详细讲解。

关于搜索二叉树的底层在下面的代码实现中会进行详细分析。

代码实现

二叉搜索树有两个模型：1）key模型；2）key_value模型；

key模型主要是对单个数据进行排序的；key_value模型是在对key排完序后，可以通过key查找到另一个value模型。

比如：key模型会用在快速判断一个事物存不存在，比如小区门禁，通过信息进行排序，快速寻找访客是不是户主；key_value 会用在像电子字典上，将单词排序后，在查找key中的英文时，也能读取value中存储的含义。

下面代码会进行key_value模型的实现。

成员

在C++中有一个类是专门用来存储key和value值的，叫做pair；该模型也是专门为map设计的，此处写代码时就直接使用了。

pair - C++ Referencehttps://legacy.cplusplus.com/reference/utility/pair/?kw=pair

关于pair的构造，有两种：1）可以通过一个函数make_pair创建对象来实现构造。

2）在C++11后支持多参数的构造，但是需要{}进行构造。

pair<int, int> p;
pair<string, int> p2(make_pair("make", 1));  //通过函数make_pair进行构造
pair<int, int> p1({ 1,2 });                 //多参数构造

基本结构

与二叉树的主要区别在与：搜索二叉树的成员时pair对象。

template<class K ,class V>
struct BSTreeNode    //二叉树的每一个节点
{//构造函数BSTreeNode(const pair<K,V>& vk):_vk(vk), left(nullptr), right(nullptr){}pair<K, V> _vk;    //储存key和value的容器BSTreeNode* left;   //左节点BSTreeNode* right;   //右节点};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> BSTreeNode;private:BSTreeNode* _root=nullptr;
};

查找

二叉搜索树满足：左树小，右树大的特点，所以只需要将查找的值和当前节点的值进行对比，就能确定是往左树走，还是往右树走。

当前节点小了，往右树找；当前节点大了，往左树找；只当找到或到空节点。

//查找
bool Find(const pair<K, V> vk)
{BSTreeNode* cur = _root;while (cur){if (cur->_vk.first > vk.first){cur = cur->left;     //当前节点大，往左找}else if (cur->_vk.first < vk.first){ cur = cur->right;    //当前节点小,往右找}else{return true;          //相等，返回}}return false;     //没找到，返回
}

插入

关于二叉搜索树的插入，需要考虑要插入到哪一个位置？？？：二叉搜索树是有要求的，在插入数据后还需要满足是二叉搜索树的结构。

二叉搜索树是没有重复数据的，所以不需要考虑找不到位置的情况。那插入的位置必定是空节点。

像查找一样，通过比较来确定节点的位置。当找到位置后，插入即可。

//插入
bool Insert(const pair<K, V>& vk)
{BSTreeNode* newnode = new BSTreeNode(vk);if (_root == nullptr){_root = newnode;return true;}else{BSTreeNode* cur = _root;BSTreeNode* parent = nullptr;   //保存新节点的父节点，保证后续节点的链接while (cur){if (cur->_vk.first > vk.first){parent = cur;cur = cur->left;}else if (cur->_vk.first < vk.first){parent = cur;cur = cur->right;}else{return false;   //相等，说明树中已经有该节点了，不需要再插入}} //循环出来了，说明找到位置了//将新节点插入到指定位置，注意还需要判断其是父节点左子树还是右子树if (parent->_vk.first > vk.first){parent->left = newnode;}else{parent->right = newnode;}return true;}
}

删除

删除的情况，有三种；

1）删除节点没有左节点：将右节点和父节点链接即可；

2）删除节点没有右节点：将左节点和父节点链接即可；

3）有左右节点：找一个位置能满足当前位置节点得到要求，即比左树都大，比右树都小。这个节点可以是左树的最大值(即左树的最右边)，或右树的最小值(即右树的最左边)。

//删除
bool Erase(const pair<K, V> vk)
{BSTreeNode* cur = _root;BSTreeNode* parent = nullptr;while (cur){if (cur->_vk.first > vk.first){parent = cur;cur = cur->left;}else if (cur->_vk.first < vk.first){parent = cur;cur = cur->right;}else{break;   //找到了}}if (cur == nullptr)   //不存在要删除的节点return false;if (cur->left == nullptr)   //左树为空{if (parent == nullptr)  //判断删除节点是否为根节点_root = cur->right;else{if (parent->left == cur)    //是父节点的坐支还是右支parent->left = cur->right;else parent->right = cur->right;}}else if (cur->right == nullptr){if (parent == nullptr) _root = cur->left;else{if (parent->left == cur)   parent->left = cur->left;elseparent->right = cur->left;}}else{//找左树的最大节点BSTreeNode* leftMax = cur->left;BSTreeNode* Maxparent = cur;while (leftMax->right){Maxparent = leftMax;leftMax = leftMax->right;}if (Maxparent->left== leftMax)   //检leftMax是在parent的左还是右{								//如果循环没进去就在左Maxparent->left = leftMax->left;}else{Maxparent->right = leftMax->left;}//将左树的最大节点的vk和要删除节点的vk进行交换即可swap(leftMax->_vk, cur->_vk);//此时leftMax存储的是需要删除的数据cur = leftMax;}delete cur;return true;
}

以上对于左右树都有节点的删除方法是：找左树的最大节点。

下面是找右树的最小节点方法。

else
{//找右树的最小节点BSTreeNode* rightMin = cur->right;BSTreeNode* Maxparent = cur;while (rightMin->left){Maxparent = rightMin;rightMin = rightMin->left;}if (Maxparent->left == rightMin)   //检leftMax是在parent的左还是右{								//如果循环没进去就在左Maxparent->left = rightMin->right;}else{Maxparent->right = rightMin->right;}//将左树的最大节点的vk和要删除节点的vk进行交换即可swap(rightMin->_vk, cur->_vk);//此时leftMax存储的是需要删除的数据cur = rightMin;
}

中序遍历

二叉搜索树通过中序遍历得到的是一个升序数组。

进行中序遍历的时候采用递归的方式进行，所以参数需要传_root才行，但是对于类外是不能访问_root的，所以此处通过函数调用函数来实现。

public://中序遍历void InOrder(){_InOrder(_root);}private:void _InOrder(BSTreeNode* _root){if (_root == nullptr)return;if(_root->left)_InOrder(_root->left);cout << _root->_vk.first << " " << _root->_vk.second << endl;if(_root->right)_InOrder(_root->right);}

拷贝构造

拷贝构造可以直接通过前序遍历即可。

public://拷贝构造BSTree(BSTree<K, V>& tree){_root=_BSTree(tree._root);}private:BSTreeNode* _BSTree(const BSTreeNode* root){if (root == nullptr)return nullptr;BSTreeNode* _root = new BSTreeNode(root->_vk);_root->left = _BSTree(root->left);_root->right = _BSTree(root->right);return _root;}

赋值运算符重载

赋值可以直接运用形参是实参的拷贝来实现。

//赋值运算符重载
BSTree& operator=(BSTree tmp)
{swap(tmp._root, _root);  //形参是实参的拷贝，所以直接将形参和要赋值的树交换即可return *this;
}

析构函数

析构函数需要用后序遍历来实现。

public:~BSTree(){_Destory(_root);}private:void _Destory(BSTreeNode* root){if (root == nullptr)return;_Destory(root->left);_Destory(root->right);free(root);}

以上代码中某些方法的实现其实可以使用递归来实现，但是为了易于理解采用了非递归的思想方法。下面对部分代码用递归的方法实现。

递归实现

递归实现查找

递归查找与非递归一样，只需要对节点的key值进行分类即可。

public:bool _Find(const pair<K, V>& vk){return _FindR(_root, vk);}private:bool _FindR(const BSTreeNode* root, const pair<K, V>& vk){if (root == nullptr)return false;if (root->_vk.first == vk.first)return true;if (root->_vk.first > vk.first){return _FindR(root->left, vk);}else{return _FindR(root->right, vk);}}

递归实现插入

在递归实现插入的时候，形参直接使用引用就可以不用再去考虑父节点了。

public://递归实现插入bool _Insert(const pair<K, V> vk){return _InsertR(_root, vk);}private:bool _InsertR(BSTreeNode*& _root, const pair<K, V> vk){if (_root == nullptr){_root = new BSTreeNode(vk);return true;}if (_root->_vk.first > vk.first){return _InsertR(_root->left, vk);}else if(_root->_vk.first < vk.first){return _InsertR(_root->right, vk);}else  //相等，不用插入{return false;}}

递归实现删除

递归实现删除并不是完全递归，只是在找位置的时候，使用递归。在删除的时候还是需要分类讨论。

public://递归删除bool _Erase(const pair<K, V> vk){return _EraseR(_root,vk);}
private://递归删除bool _EraseR(BSTreeNode*&root,const pair<K, V> vk){if (root == nullptr)return false;if (root->_vk.first > vk.first){return _EraseR(root->left, vk);}else if (root->_vk.first < vk.first){return _EraseR(root->right, vk);}else{BSTreeNode* del = root;if (root->left == nullptr){root = root->right;}else if (root->right == nullptr){root = root->left;}else{//找到了删除//找左树的最大节点替换BSTreeNode* leftMax = root->left;while (leftMax->right){leftMax = leftMax->right;}swap(root->_vk, leftMax->_vk);return _EraseR(root->left, vk);  //不能直接删除del,这样会导致del节点与父节点                //的联系没有处理}delete del;del = nullptr;return true;}    }

概念

代码实现

成员

基本结构

查找

插入

删除

中序遍历

拷贝构造

赋值运算符重载

析构函数

递归实现

递归实现查找

递归实现插入

递归实现删除

相关文章：