三明住房和城乡建设部网站,上林住房和城乡建设网站,国外网站能否做百科参考资料,佛山高端网站目录
一、二叉搜索树
1.1 概念
1.2 二叉搜索树操作
二、二叉搜索树实现
2.1 框架总览
2.2 实现接口总览
2.2.1 构造函数
2.2.2 拷贝构造
2.2.3 赋值重载
2.2.4 析构函数
2.2.5 二叉搜索树的遍历
2.2.6 插入函数
2.2.7 查找函数
2.2.8 删除函数 2.3 二叉搜索数完整…目录
一、二叉搜索树
1.1 概念
1.2 二叉搜索树操作
二、二叉搜索树实现
2.1 框架总览
2.2 实现接口总览
2.2.1 构造函数
2.2.2 拷贝构造
2.2.3 赋值重载
2.2.4 析构函数
2.2.5 二叉搜索树的遍历
2.2.6 插入函数
2.2.7 查找函数
2.2.8 删除函数 2.3 二叉搜索数完整代码
三、二叉搜索树的应用
3.1 K模型
3.2 KV模型
四、二叉搜索树的性能分析 前言二叉搜索树是数据结构初阶二叉树的一部分二叉搜索树为后序所学的 map 和 set 做准备
一、二叉搜索树
1.1 概念 二叉搜索树BSTBinary Search Tree又称二叉排序树它或者是一棵空树二叉树搜索树具有以下性质:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
比如下面就是一颗二叉搜索树 左子树小于根节点右子树大于根节点每颗子树都保持这样的特性这样的树就称为二叉搜索树 二叉搜索树进行中序遍历遍历出来的结果是有序的升序二叉搜索树一般都是去重的即没有相同的值
1.2 二叉搜索树操作
二叉搜索树的主要接口就是插入、查找、删除、遍历
1查找Find
从根开始比较查找比根大则往右边走查找比根小则往左边走查找最多查找高度次走到到空还没找到这个值不存在
2插入Insert
插入一个节点插入后保持二叉搜索树的性质二叉搜索树实现下面解释
3删除Erase
删除一个节点删除后保持二叉搜索树的性质二叉搜索树实现下面解释
4遍历InOrder
使用中序遍历即可遍历结果为升序序列
二、二叉搜索树实现
2.1 框架总览 要实现二叉搜索树我们首先需要实现一个节点类结点类当中包含三个成员变量结点的值、左指针、右指针结点类当中只需实现一个构造函数即可 二叉搜索树类BSTree里面的成员变量只要包含一个根节点 _root 即可
为了书写简单对 BSTreeNodeK 进行 typedef 为 Node typedef BSTreeNodeK Node templateclass K
struct BSTreeNode
{BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:private:Node* _root;
};
2.2 实现接口总览
templateclass K
struct BSTreeNode
{BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public://构造函数BSTree(){}//拷贝构造BSTree(const BSTreeK t){}//赋值重载BSTreeK operator(BSTreeK t){}//析构~BSTree(){}bool Insert(const K key){}bool Find(const K key){}bool Erase(const K key){}//遍历搜索树void InOrder(){}private:Node* _root;
};
2.2.1 构造函数
构造函数非常简单构造一个空树即可
//构造函数BSTree():_root(nullptr){}
2.2.2 拷贝构造
由于要进行递归操作就不能把递归操作写在拷贝构造函数里面需要另写一个函数这个函数设置为私有拷贝构造也是深拷贝
//拷贝构造
BSTree(const BSTreeK t)
{_root Copy(t._root);
}private: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;}
2.2.3 赋值重载
赋值重载直接使用现代写法复用拷贝构造不解释了赋值重载也是深拷贝
//赋值重载
BSTreeK operator(BSTreeK t)
{swap(_root, t._root);return *this;
}
2.2.4 析构函数
析构函数也是如此需要进行递归操作需要另写一个函数进行递归操作
//析构
~BSTree()
{Destroy(_root);_root nullptr;
}private:void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;}
2.2.5 二叉搜索树的遍历
遍历使用中序遍历即可遍历出来的结果是升序的因为无法使用类成员变量就无法传根进行递归遍历所以也需要另写一个函数
代码如下
//遍历搜索树
void InOrder()
{_InOrder(_root);cout endl;
}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}
2.2.6 插入函数
根据二叉搜索树的性质其插入操作非常简单
如果是空树则直接将插入结点作为二叉搜索树的根结点如果不是空树则按照二叉搜索树的性质进行结点的插入
若不是空树插入结点的具体操作如下
若待插入结点的值小于根结点的值则需要将结点插入到左子树当中若待插入结点的值大于根结点的值则需要将结点插入到右子树当中若待插入结点的值等于根结点的值则插入结点失败二叉搜索树
插入成功返回 true插入失败返回 false
代码如下
bool Insert(const K key){//_root为空树if (_root nullptr){_root new Node(key);return true;}//不为空树进行查找Node* parent nullptr;Node* cur _root;while (cur)//遇到空就结束{if (_root-_key key)//在左子树{parent cur;cur cur-_left;}else if (_root-_key key)//在右子树{parent cur;cur cur-_right;}else//相等直接返回不允许插入相同值{return false;}}cur new Node(key);if (parent-_key key)//parent节点的_key比key大插入到左边{parent-_left cur;}else//parent节点的_key比key小插入到右边{parent-_right cur;}return true;}
2.2.7 查找函数
根据二叉搜索树的特性,分以下几种情况
若树为空树则查找失败返回 false若key值小于当前结点的值则应该在该结点的左子树当中进行查找若key值大于当前结点的值则应该在该结点的右子树当中进行查找若key值等于当前结点的值则查找成功返回 true查找完了还是没有找到返回 false
代码如下 bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else//找到了{return true;}}//空树或者找不到return false;}
2.2.8 删除函数 二叉搜索树的删除函数是最难实现的若是在二叉树当中没有找到待删除结点则直接返回 false 表示删除失败即可但若是找到了待删除结点此时就有以下三种情况
待删除结点的左子树为空待删除结点的右子树为空待删除结点的左右子树均不为空
下面进行一对一处理
1待删除结点的左子树为空即右子树不为空 若待删除结点的左子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的右孩子结点然后再将该结点释放便完成了该结点的删除进行删除操作后仍保持二叉搜索树的特性
动图演示 2待删除结点的右子树为空即左子树不为空 若待删除结点的右子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的左孩子结点然后再将该结点释放便完成了该结点的删除进行删除操作后仍需要保持二叉搜索树的特性
动图演示 3待删除结点的左右子树均不为空 若待删除结点的左右子树均不为空那么当我们在二叉搜索树当中找到该结点后可以使用替换法进行删除
有两种替换方法可以将让待删除结点左子树当中值最大的结点或是待删除结点右子树当中值最小的结点代替待删除结点被删除下面都以最小的结点代替待删除为例 然后将待删除结点的值改为代替其被删除的结点的值即可而代替待删除结点被删除的结点必然左右子树当中至少有一个为空树因此删除该结点的方法与前面说到的情12的方法相同 注意只能是待删除结点左子树当中值最大的结点或是待删除结点右子树当中值最小的结点代替待删除结点被删除因为只有这样才能使得进行删除操作后的二叉树仍保持二叉搜索树的特性 动图演示 代码如下
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//找到了要删除的节点{//左为空,右不为空if (cur-_left nullptr){if (cur _root)//要删除的为根节点{_root cur-_right;}else//非根节点{parent-_right cur-_right;}delete cur;}else if (cur-_right nullptr)//左不为空右为空{if (cur _root)//要删除的为根节点{_root cur-_left;}else//非根节点{parent-_left cur-_left;}delete cur;}else//左右不为空替换删除{//左右不为空需要左子树的最大值 或 右子树的左小值充当新的根对被删除节点进行值替换然后进行删除Node* minParent cur;Node* minRight cur-_right;//这里选用最小值进行替换while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_key minRight-_key;//值替换minRight换不换没影响minRight是要被删除的//分两种情况if (minRight minParent-_left){minParent-_left minRight-_right;}else{minParent-_right minRight-_right;}delete minRight;}return true;}}return false;
} 2.3 二叉搜索数完整代码
BSTree.h
#pragma oncetemplateclass K
struct BSTreeNode
{BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public://构造函数BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}//赋值重载BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}//析构~BSTree(){Destroy(_root);_root nullptr;}bool Insert(const K key){//_root为空树if (_root nullptr){_root new Node(key);return true;}//不为空树进行查找Node* parent nullptr;Node* cur _root;while (cur)//遇到空就结束{if (_root-_key key)//在左子树{parent cur;cur cur-_left;}else if (_root-_key key)//在右子树{parent cur;cur cur-_right;}else//相等直接返回不允许插入相同值{return false;}}cur new Node(key);if (parent-_key key)//parent节点的_key比key大插入到左边{parent-_left cur;}else//parent节点的_key比key小插入到右边{parent-_right cur;}return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else//找到了{return true;}}//空树或者找不到return false;}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//找到了要删除的节点{//左为空,右不为空if (cur-_left nullptr){if (cur _root)//要删除的为根节点{_root cur-_right;}else//非根节点{parent-_right cur-_right;}delete cur;}else if(cur-_right nullptr)//左不为空右为空{if (cur _root)//要删除的为根节点{_root cur-_left;}else//非根节点{parent-_left cur-_left;}delete cur;}else//左右不为空替换删除{//左右不为空需要左子树的最大值 或 右子树的左小值充当新的根对被删除节点进行值替换然后进行删除Node* minParent cur;Node* minRight cur-_right;//这里选用最小值进行替换while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_key minRight-_key;//值替换minRight换不换没影响minRight是要被删除的//分两种情况if (minRight minParent-_left){minParent-_left minRight-_right;}else{minParent-_right minRight-_right;}delete minRight;}return true;}}return false;}//遍历搜索树void InOrder(){_InOrder(_root);cout endl;}
private:void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete 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;}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}
private:Node* _root;
};
Test.cpp
#include iostream
using namespace std;#include BSTree.hvoid Test()
{BSTreeint t;t.Insert(4);t.Insert(3);t.Insert(5);t.Insert(4);t.Insert(6);t.Insert(1);t.Insert(7);t.Insert(9);t.InOrder();//拷贝构造BSTreeint t2 t;t2.InOrder();//查找cout t2.Find(1) endl;cout t2.Find(8) endl;//赋值重载BSTreeint t3;t3 t;t3.InOrder();//删除t3.Erase(4);t3.InOrder();t3.Erase(5);t3.InOrder();t3.Erase(3);t3.InOrder();t3.Erase(7);t3.InOrder();
}int main()
{Test();return 0;
}三、二叉搜索树的应用
3.1 K模型 K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值 比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误
3.2 KV模型 KV模型每一个关键码 Key都有与之对应的值 Value即Key, Value的键值对通过Key查找 Value 该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对
四、二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 对于有n个结点的二叉搜索树
最优的情况下二叉搜索树为完全二叉树其平均比较次数为O(logN)最差的情况下二叉搜索树退化为单支树其平均比较次数为O(N / 2)
所以实际上二叉搜索树在极端情况下是没办法保证效率的因此由二叉搜索树又衍生出来了AVL树、红黑树后面准备学
----------------我是分割线---------------
文章到这里就结束了下一篇即将更新
