网站开发项目组成员,什么样的网站利于seo,wordpress上传apk,南宁网络推广外包朋友们、伙计们#xff0c;我们又见面了#xff0c;本期来给大家解读一下有关多态的知识点#xff0c;如果看完之后对你有一定的启发#xff0c;那么请留下你的三连#xff0c;祝大家心想事成#xff01; C 语 言 专 栏#xff1a;C语言#xff1a;从入门到精通 数据结… 朋友们、伙计们我们又见面了本期来给大家解读一下有关多态的知识点如果看完之后对你有一定的启发那么请留下你的三连祝大家心想事成 C 语 言 专 栏C语言从入门到精通 数据结构专栏数据结构 个 人 主 页 stackY、 C 专 栏 C Linux 专 栏 Linux
目录
1. 搜索二叉树
1.1 概念
1.2 搜索二叉树操作
2. 模拟实现搜索二叉树
2.1 非递归版本
2.1.1 基本构造
2.1.2 插入
2.1.3 删除
2.1.4 查找
2.2 递归版本
2.2.1 插入
2.2.2 删除
2.2.3 查找
2.2.4 中序遍历
3. 完整代码 1. 搜索二叉树 1.1 概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 1.2 搜索二叉树操作 1. 二叉树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到空还没找到这个值不存在。 2. 二叉树的插入 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 3. 二叉树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 2. 模拟实现搜索二叉树 搜索二叉树有两种模型 1. Key模型节点中只存在一个值key并且这个值不可以修改比如后面学习到的set 2. Key_Value模型节点中存在两个值一个是key不可修改另一个是与key对应的value可以修改比如后面学习到的map 在这里我们只实现Key模型的搜索二叉树 2.1 非递归版本 2.1.1 基本构造 //节点
templateclass K
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;//构造BSTreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){}
};//搜索二叉树
templateclass K
class BSTree
{
public:typedef BSTreeNodeK Node;//构造BSTree() //给定了缺省值{}//拷贝构造BSTree(const BSTreeK tmp){_root Copy(tmp._root);}//operatorBSTreeK operator(BSTreeK tmp){swap(_root, tmp._root);return *this;}//析构~BSTree(){Destroy(_root);}
private://递归拷贝左右子树Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newNode new Node(root-_key);newNode-_left Copy(root-_left);newNode-_right Copy(root-_right);return newNode;}//后序遍历删除void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}private:Node* _root nullptr; //缺省值给空即可
}; 2.1.2 插入 插入时如果为空直接插入即可若存在节点需要先进行判断比根节点大的插入到它的右子树比根节点小的插入左子树即可这时需要注意的插入的节点需要与它的父节点进行链接这时在往下比较的过程中就需要记录一下它的父节点。 //插入bool Insert(const K key){//如果为空可以直接插入链接if (_root nullptr){_root new Node(key);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;}elsereturn false;}//链接cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;} 2.1.3 删除 首先找到需要删除的节点删除的时候需要注意分下面几种情况 左子树为空可以直接删除右子树为空可以直接删除左右子树都不为空需要使用替换法删除替换法使用左子树最大的节点替换需要删除的节点或者使用右子树最小的节点替换需要删除的节点替换之后直接删除被替换的节点即可完成删除。需要注意的是在这个过程中需要记录父节点在删除之后需要及时链接并且要注意的是删除的节点是根节点的时候可以直接将它的左右子树直接链接。 //删除bool Erase(const K key){Node* cur _root;//记录父亲Node* parent nullptr;while (cur){//找到要删除的keyif (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 //不为根节点{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 //左右子树都不为空 //使用替换法{Node* parent cur;//右树的最小节点进行替换或者左树的最大节点Node* subRight cur-_right;while (subRight-_left) //找到右树的最小节点{parent subRight;subRight subRight-_left;}swap(cur-_key, subRight-_key); //替换两个节点//将删除节点的右树链接在它的父亲if (parent-_left subRight){parent-_left subRight-_right;}else {parent-_right subRight-_right;}delete subRight;}return true;}}return false;} 2.1.4 查找 //查找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;}elsereturn true;}return false;} 2.2 递归版本 2.2.1 插入 递归插入时也需要进行一层封装在里面传递root在这里采用引用传参比较好可以不用额外的链接遇到空直接创建一个节点即可直接在原数上进行操作。 //插入bool InsertR(const K key){return _InsertR(key, _root);}bool _InsertR(const K key, Node* root){//树为空直接插入即可if (root nullptr){root new Node(key);return true;}//递归左if (root-_key key)return _InsertR(key, root-_left);else if (root-_key key) //递归右return _InsertR(key, root-_right);elsereturn false;} 2.2.2 删除 还是采用里面封装一层在递归删除的时候先递归找到要删除的key然后判断它的左右子树如果左右子树只存在一个可以直接进行删除然后将它的孩子链接在它的节点上如果左右孩子均存在使用替换法用该节点的右子树的最小节点进行替换先使用循环找到该最小节点然后与其交换然后转化为递归该节点右子树的删除问题即可。 //删除bool EraseR(const K key){return _EraseR(key, _root);}
bool _EraseR(const K key, Node* root){if (root nullptr)return false;//查找keyif (root-_key key){return _EraseR(root-_right, key);}else if (root-_key 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* subRight root; //找到右树的最小节点while (subRight-left){subRight subRight-_left;}swap(root-_key, subRight-_key); //交换return _EraseR(key, root-_right); //转化为递归右子树的子问题}}} 2.2.3 查找 //查找bool FindR(const K key){_FindR(key, _root);}
bool _FindR(const K key, Node* root){if (root nullptr)return false;if (root-_key key)return _FindR(root-_left);else if (root-_key key)return _FindR(root-_right);elsereturn true;} 2.2.4 中序遍历 中序遍历时需要封装一层在外面不好传递节点中序遍历左子树、根、右子树 //中序遍历void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root nullptr)return; _InOrder(root-_left);cout root-_key ;_InOrder(root-_right);} 3. 完整代码 #pragma once
#include iostreamusing namespace std;templateclass K
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){}
};templateclass K
class BSTree
{
public:typedef BSTreeNodeK Node;//构造BSTree() //给定了缺省值{}//拷贝构造BSTree(const BSTreeK tmp){_root Copy(tmp._root);}//operatorBSTreeK operator(BSTreeK tmp){swap(_root, tmp._root);return *this;}//析构~BSTree(){Destroy(_root);}//非递归版本//插入bool Insert(const K key){//如果为空可以直接插入链接if (_root nullptr){_root new Node(key);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;}elsereturn false;}//链接cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}//删除bool Erase(const K key){Node* cur _root;//记录父亲Node* parent nullptr;while (cur){//找到要删除的keyif (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 //不为根节点{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 //左右子树都不为空 //使用替换法{Node* parent cur;//右树的最小节点进行替换或者左树的最大节点Node* subRight cur-_right;while (subRight-_left) //找到右树的最小节点{parent subRight;subRight subRight-_left;}swap(cur-_key, subRight-_key); //替换两个节点//将删除节点的右树链接在它的父亲if (parent-_left subRight){parent-_left subRight-_right;}else{parent-_right subRight-_right;}delete subRight;}return true;}}return 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;}elsereturn true;}return false;}//递归版本//插入bool InsertR(const K key){return _InsertR(key, _root);}//删除bool EraseR(const K key){return _EraseR(key, _root);}//查找bool FindR(const K key){_FindR(key, _root);}//中序遍历void InOrder(){_InOrder(_root);cout endl;}private://插入bool _InsertR(const K key, Node* root){//树为空直接插入即可if (root nullptr){root new Node(key);return true;}//递归左if (root-_key key)return _InsertR(key, root-_left);else if (root-_key key) //递归右return _InsertR(key, root-_right);elsereturn false;}//删除bool _EraseR(const K key, Node* root){if (root nullptr)return false;//查找keyif (root-_key key){return _EraseR(root-_right, key);}else if (root-_key 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* subRight root; //找到右树的最小节点while (subRight-left){subRight subRight-_left;}swap(root-_key, subRight-_key); //交换return _EraseR(key, root-_right); //转化为递归右子树的子问题}}}//查找bool _FindR(const K key, Node* root){if (root nullptr)return false;if (root-_key key)return _FindR(root-_left);else if (root-_key key)return _FindR(root-_right);elsereturn true;}//中序遍历void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}//拷贝Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newNode new Node(root-_key);newNode-_left Copy(root-_left);newNode-_right Copy(root-_right);return newNode;}//销毁void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}
private:Node* _root nullptr;
}; 朋友们、伙计们美好的时光总是短暂的我们本期的的分享就到此结束欲知后事如何请听下回分解~最后看完别忘了留下你们弥足珍贵的三连喔感谢大家的支持
