美文的手机网站,新闻类网站怎么做百度推广,平面设计新手兼职接单,网站模板被抄袭怎么办二叉搜索树 一、认识二叉搜索树二、二叉搜索树实现2.1插入2.2查找2.3删除 总结 一、认识二叉搜索树
二叉搜索树#xff08;Binary Search Tree#xff0c;简称 BST#xff09;是一种特殊的二叉树#xff0c;它具有以下特征#xff1a;
若它的左子树不为空#xff0c;则… 二叉搜索树 一、认识二叉搜索树二、二叉搜索树实现2.1插入2.2查找2.3删除 总结 一、认识二叉搜索树
二叉搜索树Binary Search Tree简称 BST是一种特殊的二叉树它具有以下特征
若它的左子树不为空则左子树上所有节点的值都小于根节点的值。若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
如图
二、二叉搜索树实现
在实现各种操作之前我们先创建节点使用结构体类模板来创建因为结构体默认访问权限是共有的即public里面需要写到左子树、右子树、结点的值再写个构造函数赋初值。
templateclass K
struct BStreeNode
{BStreeNodeK* _left;BStreeNodeK* _right;K _key;BStreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){}
};2.1插入
插入操作步骤
树为空则直接新增节点赋值给root指针树不空按二叉搜索树性质查找插入位置插入新节点 解析 首先while循环进行遍历,若该key值比cur值小则向cur左树找反之右树找直到叶子节点为止。如果与cur值相同返回false因为二叉搜索树不允许有相同的数出现。 插入过程需要连接创建个parent节点跟着我们需要遍历的节点cur完成连接过程。 跟父节点比较比父节点大插入到他的右边反之就是左边。 代码
bool insert(const K key)
{if (_root nullptr){_root new node(key);return true;}node* parent nullptr;node* cur _root;////cur每次要向下走parent也跟着走while (cur){if (key cur-_key ){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{return false;}}cur new node(key);if (parent-_key key){//如果插入的值比目标值大就连接在右边parent-_right cur;}else{parent-_left cur;}return true;
}2.2查找
若key大于cur-_key就从右树找 key小于cur-_key就从左子树找。 如果相等 返回true
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;}}return false;
}2.3删除
1、首先定义个父节点parent和节点cur指向根节点 2、再循环遍历cur先找要删除的节点。
若删除的节点左数为空且删除的是根节点让根结点指向原根结点的右子树。删除的不是根节点让他的子树托孤给他的父节点。如果右节点空删除的是根节点让他的根节点只想原根结点的左子树不是根节点就托孤给父节点左右都不为空的情况下。父节点指向curleftnode被删节点的左子树指向cur的左子树循环遍历leftnode右子树交换cur与leftnode值如果leftnode在父节点的左子树那就将leftnode的左子树给父节点的左子树否则就给父节点的右子树。最后将leftnode传给cur再删除cur.
bool Erase(const K key)
{node* parent nullptr;node* cur _root;//没有节点while (cur){//找if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{//找到了 左空if (cur-_left nullptr){if (cur _root)//如果cur没有parent他就是根节点{_root cur-_right;}else {if (parent-_right cur)//如果cur右为空并且是父亲的右节{//节点指向curparent-_right cur-_right;}else{parent-_left cur-_right;}}}//else if (cur-_right nullptr)//如果cur右为空。{ if (cur _root){_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}else {node* parent cur;node* leftnode cur-_left;//右边不为空的情况一直找下去while (leftnode-_right){parent leftnode;//每次走之前给parentleftnode leftnode-_right;}swap(cur-_key, leftnode-_key);if (parent-_left leftnode){parent-_left leftnode-_left;}else{parent-_right leftnode-_left;}cur leftnode; }delete cur;return true;}}
}总结
以上就是本期内容以后会多多更新
