网站专题方案,德清县住房和城乡建设局网站,h5开发工具哪个好,互联网网站开发html5目录
一#xff0c;概念
二#xff0c;实现分析
1. 插入
#xff08;1.#xff09;非递归版本 #xff08;2.#xff09;递归版本 2. 打印搜索二叉树
3.查找函数
#xff08;1.#xff09;非递归版本
#xff08;2.#xff09;递归版本
4. 删除函数#x…目录
一概念
二实现分析
1. 插入
1.非递归版本 2.递归版本 2. 打印搜索二叉树
3.查找函数
1.非递归版本
2.递归版本
4. 删除函数重难点
易错点分析包你学会
1.删除目标没有左右孩子
2.删除目标只有一个孩子
3.删除目标有两个孩子
代码
1.非递归版本
2.递归版本
5. 析构函数
6.拷贝构造 三应用 四搜索二叉树的缺陷及优化
五代码汇总
结语 一概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 为啥又被称作二叉排序树呢 当该树被层序遍历时就是升序。 二实现分析
实验例子 int a[] {8, 3, 1, 10, 6, 4, 5, 7, 14, 13}; 1. 插入
1.非递归版本 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 比较简单这里就直接放代码
template class K
class BinarySeaTree_node
{typedef BinarySeaTree_nodeK BST_node;
public:BinarySeaTree_node(const K val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template class T
class BSTree
{typedef BinarySeaTree_nodeT BST_node;
private:BST_node* root nullptr;public:bool Insert(const T val){BST_node* key new BST_node(val);BST_node* cur root;BST_node* parent nullptr;while (cur){if (key-_val cur-_val){parent cur;cur cur-_left;}else if (key-_val cur-_val){parent cur;cur cur-_right;}else{return 0;}}// 查询好位置后建立链接if (!root){root key;return 0;}if (key-_val parent-_val){parent-_right key;}else{parent-_left key;}return 1;}
};2.递归版本 这里面整了个活大家注意了!!! bool Re_Insert(const T val){ return Re_Insert_table(root, val);}bool Re_Insert_table(BST_node* node, const T val){if (node nullptr){node new BST_node(val);return 1;}if (val node-_left){return Re_Insert_table(node-_left, val);}else if (val node-_right){ return Re_Insert_table(node-_right, val);}else{return 0;}}
这里方便大家理解我给大家花一个递归展开图。 2. 打印搜索二叉树 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 这里也是仅做代码分享
void Print_table() { Re_Print(root); }void Re_Print(const BST_node* node){if (node nullptr)return;Re_Print(node-_left);cout node-_val ;Re_Print(node-_right);}3.查找函数 思路其实也没啥思路比父结点小就找左边否则找右边。 1.非递归版本
BST_node* Find(const T val){//直接跟寻找位置一样BST_node* parent nullptr;BST_node* cur root; // 以返回cur的方式返回while (cur) // 非递归版本{if (val cur-_val){parent cur;cur cur-_left;}else if (val cur-_val){parent cur;cur cur-_right;}else{return cur;}}return cur;}
2.递归版本
BST_node* Re_Find(const T val){ return Re_Find_table(root, val); }BST_node* Re_Find_table(BST_node* node, const T val){if (node nullptr)return nullptr;if (val node-_val){return Re_Find_table(node-_left, val);}else if (val node-_val){return Re_Find_table(node-_right, val);}else{return node;}} 4. 删除函数重难点
我们简单寻找了一下思路如下 但这些思路只是大概方向其中藏着许多的坑点诺接下来我来带大家对这些易错点进行分析。 首先是查询到目标 这个比较简单这里不做解释。 //首先寻找到目标,并且记录到parentBST_node* parent nullptr;BST_node* cur root;while (cur){if (val cur-_val){parent cur;cur cur-_left;}else if (val cur-_val){parent cur;cur cur-_right;}else{break;}}if (!cur){return 0;}
易错点分析包你学会
1.删除目标没有左右孩子 2.删除目标只有一个孩子
一般的思路 但这是有漏洞的
诺 3.删除目标有两个孩子 好啦前菜上完了来看看本次的大菜。 代码
1.非递归版本
bool Erase(const T val){//首先寻找到指定值,并且记录到parentBST_node* parent nullptr;BST_node* cur root;while (cur){if (val cur-_val){parent cur;cur cur-_left;}else if (val cur-_val){parent cur;cur cur-_right;}else{break;}}if (!cur){return 0;}// 查询成功,开始删除if (!cur-_left !cur-_right) // cur没有左右孩子{ // 当要删除目标是根if (cur root){root nullptr;delete cur;}// 判断cur是左右孩子else if (cur-_val parent-_val){parent-_left nullptr;delete cur;}else{parent-_right nullptr;delete cur;}return 1;}else if (!cur-_left || !cur-_right) // 只有一个孩子{if (!parent) // 判断是否是目标是根{root cur-_left ! nullptr ? cur-_left : cur-_right;delete cur;}// 判断cur为啥孩子else if (cur-_val parent-_val) // 左侧{parent-_left cur-_left ! nullptr ? cur-_left : cur-_right;delete cur;}else // 右侧{parent-_right cur-_left ! nullptr ? cur-_left : cur-_right;delete cur;}}else // 有2个孩子{ // 使用左侧最大的孩子来领养// 寻找左侧最大BST_node* maxnode cur-_left;BST_node* max_parent cur;while (maxnode-_right){max_parent maxnode;maxnode maxnode-_right;}// 现在又进入一种特殊情况,1.max_parent就没进入循环2.进入了循环if (max_parent cur){max_parent-_left maxnode-_left;}else{max_parent-_right maxnode-_left;}// 值转移cur-_val maxnode-_val;delete maxnode;}return 1;}
2.递归版本
bool Re_Erease( const T val){return Re_Erease_table(root, val);}bool Re_Erease_table(BST_node* node, const T val){// 首先我们先找到值if (node nullptr){return 0; // 如果访问到了空则说明删除失败原因是不存在}if (val node-_val){return Re_Erease_table(node-_left, val);}else if (val node-_val){return Re_Erease_table(node-_right, val);}else{// 开始删除目标数据。方法如下// 1. 就按照非递归的思路不用改多少代码 // 2. 使用递归方法优势就是代码简洁// 这里使用方法2BST_node* del node; // 保存每次访问的对象如果是目标就备份好了if (node-_left nullptr){node node-_right;}else if (node-_right nullptr){node node-_left;}else{//处理左右都有孩子的目标// 左侧查找最大值右侧查找最小值BST_node* max_node node-_left;while (max_node-_right){max_node max_node-_right;}// 完成循环后max_node最多有左孩子然后数据交换我们以目标左侧树为起点// 再次递归删除替换数据。swap(max_node-_val, node-_val);return Re_Erease_table(node-_left, val); //已经完成删除就直接退出以免触发删除delete} //处理前两种情况delete del;}} 5. 析构函数
思路
~BSTree(){ Distroy_Re(root);root nullptr; }
void Distroy_Re(BST_node* node) // 我们采用递归删除{if (node nullptr)return ;// 先处理左右孩子Distroy_Re(node-_left);Distroy_Re(node-_right);delete node;node nullptr;} 6.拷贝构造 // 我们实现了拷贝构造默认构造函数则不会生成 // 解决方案1.实现构造函数 2.使用default关键字强制生成默认构造BSTree() {}// BSTree() defaultBSTree(const BSTree Tree) // 拷贝构造{root copy(Tree.root);}BST_node* copy(BST_node* root){if (root nullptr)return nullptr;BST_node* new_node new BST_node(root-_val);new_node-_left copy(root-_left);new_node-_right copy(root-_right);return new_node;} 三应用
1. K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如 给一个单词word判断该单词是否拼写正确具体方式如下以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 2. KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见 比如 英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对 再比如 统计单词次数统计成功后给定单词就可快速找到其出现的次数 单词与其出现次数就是word, count就构成一种键值对这个比较简单修改一下即可 四搜索二叉树的缺陷及优化
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最坏情况N 平均情况O(logN) 问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优那么我们后续章节学习的AVL树和红黑树就可以上场了。 五代码汇总
namespace key
{
template class K
class BinarySeaTree_node
{typedef BinarySeaTree_nodeK BST_node;
public:BinarySeaTree_node(const K val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template class T
class BSTree
{
public:typedef BinarySeaTree_nodeT BST_node;// 我们实现了拷贝构造默认构造函数则不会生成 // 解决方案1.实现构造函数 2.使用default关键字强制生成默认构造BSTree(){}// BSTree() defaultBSTree(const BSTree Tree) // 拷贝构造{root copy(Tree.root);}BSTreeT operator(BSTreeT t){swap(root, t.root);return *this;}BST_node* copy(BST_node* root){if (root nullptr)return nullptr;BST_node* new_node new BST_node(root-_val);new_node-_left copy(root-_left);new_node-_right copy(root-_right);return new_node;}bool Re_Insert(const T val) { return Re_Insert_table(root, val); }void Re_Print() { Re_Print_table(root); }bool Re_Erease(const T val) { return Re_Erease_table(root, val); }BST_node* Re_Find(const T val) { return Re_Find_table(root, val); }bool Insert(const T val){BST_node* key new BST_node(val);BST_node* cur root;BST_node* parent nullptr;while (cur){if (key-_val cur-_val){parent cur;cur cur-_left;}else if (key-_val cur-_val){parent cur;cur cur-_right;}else{return 0;}}// 查询好位置后建立链接if (!root){root key;return 0;}if (key-_val parent-_val){parent-_right key;}else{parent-_left key;}return 1;}BST_node* Find(const T val){//直接跟寻找位置一样BST_node* parent nullptr;BST_node* cur root; // 以返回cur的方式返回while (cur) // 非递归版本{if (val cur-_val){parent cur;cur cur-_left;}else if (val cur-_val){parent cur;cur cur-_right;}else{return cur;}}return cur;}bool Erase(const T val){//首先寻找到指定值,并且记录到parentBST_node* parent nullptr;BST_node* cur root;while (cur){if (val cur-_val){parent cur;cur cur-_left;}else if (val cur-_val){parent cur;cur cur-_right;}else{break;}}if (!cur){return 0;}// 查询成功,开始删除if (!cur-_left !cur-_right) // cur没有左右孩子{ // 当要删除目标是根if (cur root){root nullptr;delete cur;}// 判断cur是左右孩子else if (cur-_val parent-_val){parent-_left nullptr;delete cur;}else{parent-_right nullptr;delete cur;}return 1;}else if (!cur-_left || !cur-_right) // 只有一个孩子{if (!parent) // 判断是否是目标是根{root cur-_left ! nullptr ? cur-_left : cur-_right;delete cur;}// 判断cur为啥孩子else if (cur-_val parent-_val) // 左侧{parent-_left cur-_left ! nullptr ? cur-_left : cur-_right;delete cur;}else // 右侧{parent-_right cur-_left ! nullptr ? cur-_left : cur-_right;delete cur;}}else // 有2个孩子{ // 使用左侧最大的孩子来领养// 寻找左侧最大BST_node* maxnode cur-_left;BST_node* max_parent cur;while (maxnode-_right){max_parent maxnode;maxnode maxnode-_right;}// 现在又进入一种特殊情况,1.max_parent就没进入循环2.进入了循环if (max_parent cur){max_parent-_left maxnode-_left;}else{max_parent-_right maxnode-_left;}// 值转移cur-_val maxnode-_val;delete maxnode;}return 1;}~BSTree(){Distroy_Re(root);root nullptr;}protected:bool Re_Insert_table(BST_node* node, const T val){if (node nullptr){node new BST_node(val);return 1;}if (val node-_val){return Re_Insert_table(node-_left, val);}else if (val node-_val){return Re_Insert_table(node-_right, val);}else{return 0;}}void Re_Print_table(const BST_node* node){if (node nullptr)return;Re_Print_table(node-_left);cout node-_val ;Re_Print_table(node-_right);}BST_node* Re_Find_table(BST_node* node, const T val){if (node nullptr)return nullptr;if (val node-_val){return Re_Find_table(node-_left, val);}else if (val node-_val){return Re_Find_table(node-_right, val);}else{return node;}}bool Re_Erease_table(BST_node* node, const T val){// 首先我们先找到值if (node nullptr){return 0; // 如果访问到了空则说明删除失败原因是不存在}if (val node-_val){return Re_Erease_table(node-_left, val);}else if (val node-_val){return Re_Erease_table(node-_right, val);}else{// 开始删除目标数据。方法如下// 1. 就按照非递归的思路不用改多少代码 // 2. 使用递归方法优势就是代码简洁// 这里使用方法2BST_node* del node; // 保存每次访问的对象如果是目标就备份好了if (node-_left nullptr){node node-_right;}else if (node-_right nullptr){node node-_left;}else{//处理左右都有孩子的目标// 左侧查找最大值右侧查找最小值BST_node* max_node node-_left;while (max_node-_right){max_node max_node-_right;}// 完成循环后max_node最多有左孩子然后数据交换我们以目标左侧树为起点// 再次递归删除替换数据。swap(max_node-_val, node-_val);return Re_Erease_table(node-_left, val); //已经完成删除就直接退出以免触发删除delete}// 查找到删除数据delete del;}}void Distroy_Re(BST_node* node) // 我们采用递归删除{if (node nullptr)return;// 先处理左右孩子Distroy_Re(node-_left);Distroy_Re(node-_right);delete node;node nullptr;}
private:BST_node* root nullptr;};
} 结语 本小节就到这里了感谢小伙伴的浏览如果有什么建议欢迎在评论区评论如果给小伙伴带来一些收获请留下你的小赞你的点赞和关注将会成为博主创作的动力
