南阳网站营销外包公司,网站程序 不能创建文件夹,厦门市城市建设档案馆网站,商品关键词怎么优化前言#xff1a;二叉搜索树是一种常用的数据结构#xff0c;支持快速的查找、插入、删除操作#xff0c;C中map和set的特性也是以二叉搜索树作为铺垫来实现的#xff0c;而二叉搜索树也是一种树形结构#xff0c;所以#xff0c;在学习map和set之前#xff0c;我们先来学… 前言二叉搜索树是一种常用的数据结构支持快速的查找、插入、删除操作C中map和set的特性也是以二叉搜索树作为铺垫来实现的而二叉搜索树也是一种树形结构所以在学习map和set之前我们先来学习这种新的树形结构--二叉搜索树。 目录
1.二叉搜索树
二叉搜索树的功能及其实现
二叉搜索树的插入和查找
二叉搜索树的删除
查找函数递归实现
插入函数递归实现
删除函数递归实现
拷贝构造和赋值运算符重载
搜索二叉树的相关性质及其应用
二叉搜索树的查找
key-value模型 1.二叉搜索树
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树同样的我们可以发现二叉搜索树的中序遍历是升序排序的 二叉搜索树的功能及其实现 我们先定义基础的节点的数据结构明显是一个二叉树类型的节点有左右节点运用模板知识我们可以描述出以下的节点结构体和搜索树的类的描述
templateclass T
struct BSTreeNdoe {BSTreeNdoe(const T data T()): _left(nullptr), _right(nullptr), data(data){}BSTreeNdoeT* _left;BSTreeNdoeT* _right;T data;};
templateclass T
class BSTree {typedef BSTreeNdoeT Node;
public://成员函数private:Node* root nullptr;};
下面的功能函数将从上面给出的结构来进行扩充功能和优化改写
二叉搜索树的插入和查找
插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点从树的根节点依次寻找如果待插入的值比当前节点大那直接插入当前节点的右边反之插入当前节点的左边这里注意一般的在二叉搜索树中不会存在相同的值需要注意的是为了保证新节点能够和树连接起来需要记录好父节点。 //插入操作bool insert(const T key){if (root nullptr)//如果当前树为空那么直接建树{root new Node(key);return true;}//如果不为空直接寻找合适的位置插入即可Node* cur root;Node* parent nullptr;//记录父亲节点用来连接while (cur){parent cur;if (cur-data key)//比当前节点小往当前节点左边走cur cur-_left;else if (cur-data key)//比当前节点大往当前节点右边走cur cur-_right;//一般来说搜索二叉树不会存在相同的两个值elsereturn false;}cur new Node(key);if (parent-data key)parent-_left cur;else if (parent-data key)parent-_right cur;return true;}
二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 bool find(const T key){Node* cur root;while (cur){if (cur-data key)cur cur-_left;else if (cur-data key)cur cur-_right;elsereturn true;}return false;}
二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 实际上这四种情况中a情况可以算作b或者c情况中因为删除叶子结点本质上可以看做要删除的节点只有为nullptr的右孩子或者左孩子节点我们来分别对这三种情况进行分析 对于替换法我们需要注意特殊的情况从上面的图可以看出左子树中的最右节点本质上就是第一次往待删除节点的左孩子节点走之后的每一步都开始往其右孩子方向走右子树的最左节点是第一次往待删除节点的右孩子节点走之后一直往其左孩子方向走此时我们的替换法是建立在待删除节点的左右孩子都存在的前提下所以左树最右节点和右树最左节点左树和右树一定都具备但是不一定有最右和最左节点下面我们就以左树最右节点为例来进行讨论分析
下面是一颗普通的二叉树 因为此时待删除节点需要满足存在左右节点所以此时符合要求的节点只有8,3其中8是正常的情况因为其左子树有右孩子通过8到3之后可以直接找到7所以8可以直接和7进行交换因为此时已经遍历到了左子树的最右节点也就是说该节点不可能再存在右孩子但是不能保证没有左孩子比如说没有7这个节点要删除8,8就只能和6交换此时我们需要将4也就是被交换节点的左子树放在3的右孩子上这样就能达到删除8的目的 此时我们再来看3这个节点这个节点特殊在其只有一个左孩子节点并且左孩子节点没有了右子树导致我们找左树最右节点的时候只能找到第一步左树的位置而被迫停下来此时这个左树就只能当做左树的最右节点来看待只是此时我们在将1和3交换之后操作上要发生变化因为此时没有了右子树所以被交换后3成了左子树也就是说需要删除的是1的左子树而不是像上面的情况一样直接将被交换节点的父节点的右树直接被删除节点的左树。
这里我们给出代码和测试二叉树方便我们下来模拟运行和理解 //删除节点bool Erase(const T key){Node* parent nullptr;Node* cur root;while (cur){if (cur-data key){parent cur;cur cur-_right;}else if (cur-data key){parent cur;cur cur-_left;}else{//找到了开始删除//只有右孩子if (cur-_left nullptr){//此时父节点有三种情况//如果要删除的是根节点,需要特殊处理if (cur root)root cur-_right;else if (cur parent-_left)parent-_left cur-_right;else if (cur parent-_right)parent-_right cur-_right;delete cur;}//只有左孩子else if (cur-_right nullptr){//此时父节点有三种情况//如果要删除的是根节点if (cur root)root cur-_left;else if (cur parent-_left)parent-_left cur-_left;else if (cur parent-_right)parent-_right cur-_left;delete cur;}//有左右两个孩子节点else{//法1假设默认选择左子树的最大节点//Node* pright cur-_left;//先找到左子树此时我们能确保待删除节点是有两个孩子的,所以p一定不为空//Node* pp cur;//初始时父节点等于待删除节点//while (pright-_right)//{// pp pright;//更新父节点// pright pright-_right;//}//std::swap(cur-data, pright-data);////if (pright pp-_left)//左子树不存在右孩子直接将p-_left赋值pp的左孩子即可// pp-_left pright-_left;//else //左子树存在右孩子// pp-_right pright-_left; //直接将交换后的节点的左子树放到待删除节点的父节点的右子树上//delete pright;//法2假设选择右子树的最小节点Node* pleft cur-_right;//选择右子树,但是最终目的是寻找右子树的最左节点Node* pp cur;while (pleft-_left){pp pleft;pleft pleft-_left;}std::swap(cur-data, pleft-data);if (pleft pp-_right)//如果待删除节点的右子树没有左孩子pp-_right pleft-_right;else //如果是正常情况pp-_left pleft-_right;//最左节点的右孩子需要保留在pp的左子树delete pleft;}return true;}}return false;}
查找函数递归实现
protected:bool findr(Node* root,const Tkey){if (root nullptr)return false;else if (root-data key)return finr(root-_left, key);else if (root-data key)return finr(root-_right, key);elsereturn true;}
public:bool FindR(const Tkey){return findr(root,key);}
插入函数递归实现
protected:bool insertr(Node* root, const T key)//由于要修改原树所以建议传引用{if (root nullptr){root new Node(key);return true;}if (root-data key)return insertr(root-_left, key);else if (root-data key)return insertr(root-_right, key);elsereturn false;}
public:bool InsertR(const T key){return insertr(root, key);}
删除函数递归实现
//节点的删除递归实现
protected:bool eraser(Node* root, const T key){if (root nullptr)return false;if (root-data key){return eraser(root-_right, key);}else if (root-data key){return eraser(root-_left, key);}else{// 删除if (root-_left nullptr){Node* del root;root root-_right;delete del;return true;}else if (root-_right nullptr){Node* del root;root root-_left;delete del;return true;}else{//以删除右子树的最小节点为例Node* pleft root-_right;while (pleft-_left){pleft pleft-_left;}std::swap(root-data, pleft-data);// 转换成在子树递归删除return eraser(root-_right, key);}}}
public:bool EraseR(const T key){return eraser(root, key);}
拷贝构造和赋值运算符重载 //拷贝构造函数
protected:Node* copy(Node* root){if (root nullptr)return nullptr;Node* newroot new Node(root-data);newroot-_left copy(root-_left);newroot-_right copy(root-_right);return newroot;}
public:BSTree(const BSTreeT b){root copy(b.root);}BSTree(){}//构造函数//赋值运算符重载BSTreeT operator(BSTreeT b){std::swap(root, b.root);return *this;} 搜索二叉树的相关性质及其应用
二叉搜索树的查找 我们不难发现搜索二叉树的中序遍历是对应的升序排列当我们在二叉搜索树中查找某个值的时候我们却不能简单的认为其查找效率是logn级别的因为查找效率需要考虑最坏的情况而我们的logn的效率实际上是理想化的情况比某个数大和比某个数小的数各占一半分别在这个数的左右两侧子树上才有logn级别的效率但是若是在最坏的情况下搜索树变成了类似于单链表式的链状结构则查找效率就会变成 o(n) 级别的因此我们需要对二叉搜索树进行优化才能符合我们的要求就叫做所谓的平衡搜索二叉树AVL树红黑树等具体我们后面再做讲解。
key-value模型 实际上在C中key-value模型的例子有很多比如mappair等数据结构它们通常是一个键值一个值的方式组成其中键值作为功能函数的主要参数相当于数组的下标有了下标我们就可以按下标访问任何一个存在的元素相当于查找等操作现在我们想在二叉搜索树中实现key-value模型此时我们只需要将本来一个节点存储的一个数据修改为一个节点可以存储两个数据即可具体细节见下面的实现
namespace key_value{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public: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){parent cur;if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return false;}}cur new Node(key, value);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}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 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){//左为空if (cur _root){_root cur-_right;}else{if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}}else if (cur-_right nullptr){//右为空if (cur _root){_root cur-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}}else{//左右都不为空// 右树的最小节点(最左节点)Node* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left;}swap(cur-_key, subLeft-_key);if (subLeft parent-_left)parent-_left subLeft-_right;elseparent-_right subLeft-_right;}return true;}}return false;}void InOrder(){_InOrder(_root);std::cout std::endl;}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);std::cout root-_key : root-_value std::endl;_InOrder(root-_right);}private:Node* _root nullptr;};
} 以上就是二叉搜索树的初阶内容了我们后续在学习map和set时还会使用二叉搜索树来实现具体我们后面再来分析下一篇我们将讲解一些二叉树的相关例题敬请期待~ 要做一个情绪稳定的成年人。烦躁的时候千万不要讲话也不要做任何决定就安静的待一会。当你内心足够坚定的时候谁都没有办法影响你的情绪。经历的越多反而明白的更多把期待降低把依赖变少努力把生活变成自己想要的样子。
