当前位置： 首页 > news >正文

怎么搭建自己的网页青岛seo博客

news 2025/8/15 8:27:06
怎么搭建自己的网页,青岛seo博客,网站开发设计资讯,wordpress改商城二叉搜索树 概念二叉搜索树的应用二叉搜索树的实现K模型基本结构和函数声明接口实现①find——查找关键码②Insert——插入关键码③Erase——删除关键码（重点）时间复杂度 源码（整体）非递归递归 KV模型 在使用C语言写数据结构阶段时…

二叉搜索树

  • 概念
  • 二叉搜索树的应用
  • 二叉搜索树的实现
    • K模型
      • 基本结构和函数声明
      • 接口实现
        • ①find——查找关键码
        • ②Insert——插入关键码
        • ③Erase——删除关键码（==重点==）
        • 时间复杂度
      • 源码（整体）
        • 非递归
        • 递归
    • KV模型

在使用C语言写数据结构阶段时，对二叉树进行了讲解。本节内容是对二叉树的深入探索，也是二叉树部分的收尾

概念

二叉搜索树也称二叉排序树（BST，Binary Search Tree）：

  1. 空树
  2. 非空树（要具有以下性质）
    • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
    • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
    • 它的左右子树也分别为二叉搜索树

注意： 二叉搜索树的key值互不相同

eg:下图就属于二叉搜索树
二叉搜索树

二叉搜索树的应用

  • K模型：即只有key作为关键码，结构中只需要存储key。关键码就是要搜索到的值

     eg: 给一个单词word，判断该单词是否拼写正确？具体步骤：1. 以词库中所有单词为基础，每个单词都是key，构建一颗搜索二叉树2. 在二叉树中搜索该单词是否存在，存在则返回true，否则返回false

  • KV模型：每一个关键码key，都有与之对应的value，即<Key, Value>的键值对

     eg1: 英汉词典 - 就是中文与英文的对应关系。通过英文可以快速找到与其对应的中文，英文单词和与其对应的中文<word, chinese>就构成键值对。eg2: 统计单词次数，统计成功后，给定单词就可以找到单词出现得次数。单词与其出现次数就是<word, count>就构成一种键值对

二叉搜索树的实现

注意： 通过二叉搜索树的应用，了解到其有两个模型，接下来对这两个模型分别进行实现。因为两个模型的接口都相似，所以仅对一个模型的接口进行详细介绍。

K模型

K模型的实现分为递归和非递归两种，但是接口的实现逻辑是一样的。为了便于理解把基本结构和函数声明先附上，然后对接口进行讲解，最后在贴上完整的源码

基本结构和函数声明

//二叉树节点
//节点使用struct，默认public访问
template<class K>
struct BSTreeNode   
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTree<K>& t);//赋值运算符重载BSTree<K>& operator=(BSTree<K> t);//析构函数~BSTree();//插入bool Insert(const K& key);//查找bool Find(const K& key);//删除bool Erase(const K& key);//中序遍历void InOrder();private:Node* _root;
};

接口实现

①find——查找关键码

功能：查找关键码是否在树中，是返回真，否则返回假。
原理：

  1. 从根开始比较，比根大则往右边查找，比根小往左边查找
  2. 最多查找高度次，走到nullptr，则这个值不存在

实现代码

  1. 非递归版本
template<class K>
bool BSTree<K>::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;
}
  1. 递归版本
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;
}

②Insert——插入关键码

原理：

  1. 树为空，直接把要插入的节点赋值给root
  2. 树不为空，通过查找的思路，找到要插入的合适位置。插入成功返回true
    注意：如果要插入的值和树中的值冲突，则返回false

实现代码

  1. 非递归版本
//插入
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}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{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;
}
  1. 递归版本
bool InsertR(const K& key)
{return _InsertR(_root, key);
}
bool _FindR(Node* root, const K& key)
{if (root == nullptr)return false;if (root->_key > key)return _FindR(root->_left, key);else if (root->_key < key)return _FindR(root->_right, key);elsereturn true;
}

③Erase——删除关键码（重点）

原理：

  1. 查找关键码是否在二叉搜索树中，不存在直接返回false
  2. 存在，则要分为四种情况

情况：
在考虑树的所有情况时，要把根节点的情况和普通情况，分离开来。哪怕最后根节点的情况和普通情况一样。（仅代表博主个人观点）

  1. 要删除的节点无孩子节点
    第一种情况
  1. 要删除的节点无左孩子节点
    第二种情况
  1. 要删除的节点无右孩子节点
    第三种情况
  1. 要删除的节点左右都不为空 （采用的方法 一 替换法）
    替换法：找到删除节点左子树的最大值节点(leftMax)，然后与删除节点交换，再删除现在的leftMax。（也可以找删除节点右子树的最小值节点(rightMin)，原理相同）
    第四种情况

实现代码

  1. 非递归版本
//删除
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  //找到了要删除的值{//分情况//1.左为空if (cur->_left == nullptr){if (cur == _root)_root = cur->_right;else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//2.右为空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}} //3.左右都不为空else{parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;cur = nullptr;return true;}}return false;
}
  1. 递归版本
//删除
bool EraseR(const K& key)
{return _EraseR(_root, key);
}bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)return false;if (root->_key < key)return _EraseR(root->_right, key);else if (root->_key > key)return _EraseR(root->_left, key);else{Node* del = root;if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;del = nullptr;return true;}
}

时间复杂度

二叉搜索树的操作时间复杂度：在O(logN)和O(N)之间。
画图解释时间复杂度：
时间复杂度

源码（整体）

非递归

//非递归
namespace key
{//二叉树节点//节点使用struct，默认public访问template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public://默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}//赋值运算符重载BSTree<K>& operator=(BSTree<K> t){swap(_root, t._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){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{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  //找到了要删除的值{//分情况//1.左为空if (cur->_left == nullptr){if (cur == _root)_root = cur->_right;else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//2.右为空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}} //3.左右都不为空else{parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;cur = nullptr;return true;}}return false;}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}private:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key);copyRoot->_left = Copy(root->_left);copyRoot->_right = Copy(root->_tight);return copyRoot;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;};
}

递归

//递归
namespace keyR
{//二叉树节点//节点使用struct，默认public访问template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public://默认构造BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}//赋值运算符重载BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}//析构函数~BSTree(){Destroy(_root);}//插入bool InsertR(const K& key){return _InsertR(_root, key);}//查找bool FindR(const K& key){return _FindR(_root, key);}//删除bool EraseR(const K& key){return _EraseR(_root, key);}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://在root添加引用很关键，要不然得是二级指针bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key > key)return _InsertR(root->_left, key);else if (root->_key < key)return _InsertR(root->_right, key);elsereturn false;}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key)return _EraseR(root->_right, key);else if (root->_key > key)return _EraseR(root->_left, key);else{Node* del = root;if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;del = nullptr;return true;}}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key > key)return _FindR(root->_left, key);else if (root->_key < key)return _FindR(root->_right, key);elsereturn true;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key);copyRoot->_left = CopyRoot(root->_left);copyRoot->_right = CopyRoot(root->_right);return copyRoot;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;};
}

KV模型

直接贴出源码：

namespace key_value
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree<K, V>& t){_root = Copy(t._root);}BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}void InOrder(){_InOrder(_root);cout << endl;}Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}bool EraseR(const K& key){return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;if (root->_left == nullptr){//这个root的引用，非常好，root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);//删的值在左边return _EraseR(root->_left, key);}delete del;return true;}}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key, root->_value);copyRoot->_left = Copy(root->_left);copyRoot->_right = Copy(root->_right);return copyRoot;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key > key){return _FindR(root->_left, key);}else if (root->_key < key){return _FindR(root->_right, key);}else{return root;}}bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr){root = new Node(key, value);return true;}if (root->_key > key){return _InsertR(root->_left, key, value);}else if (root->_key < key){return _InsertR(root->_right, key, value);}else{return false;}}private:Node* _root;};}
http://www.tj-hxxt.cn/news/112950.html

相关文章：

  • 做网站先做ue百度免费咨询
  • java网站开发seo优化教程下载
  • 电商运营这个工作真的很累吗网站seo关键词优化技巧
  • 怎么做 社区网站首页广州网站优化公司如何
  • 公司网站维护内容网站为什么要seo?
  • 做网站背景图片怎么放seo快速培训
  • 做电子章网站百度手机助手app下载安装
  • 投资公司的钱从哪里来seo基础知识考试
  • 东莞网站建设新闻资讯web网页
  • 如何建设免费网站视频广州优化seo
  • 网站建设在哪块做正规seo关键词排名网络公司
  • 网站管理的主要内容seo关键词优化最多可以添加几个词
  • 网站建设合同管辖it培训机构推荐
  • 江苏省建设厅官方网站资质查询网络优化网站
  • 做海报文案的参考网站线下推广方法及策略
  • 企业网站建设定制开发服务百度广告销售
  • 网站如何选取关键词快手刷粉网站推广
  • 诸城做网站网络营销模式
  • 杭州 定制网站淘宝店铺买卖交易平台
  • 怎么做汽车网站推广方案cps推广联盟
  • 做网站关键词注册网站怎么注册
  • 网站导航设计法则seo超级外链工具免费
  • 佛山专业网站建设百度竞价点击神器
  • php本地建站工具网站建设推广专家服务
  • 重庆网站建设推广优化专业网站优化排名
  • 湖南网站建设 要上磐石网络网站是怎么做出来的
  • 有没有一起做游戏棋牌网站的苏州seo招聘
  • 重庆做网站做得好的公司中国最大网站排名
  • html业务网站源码网络推广方法技巧
  • 做百度竞价网站修改影响排名吗整站优化服务