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

怎么搭建自己的网页整站seo怎么做

news 2025/7/20 1:16:55
怎么搭建自己的网页,整站seo怎么做,如何创办视频网站,企业手机网站建设联系方式二叉搜索树 概念二叉搜索树的应用二叉搜索树的实现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.dt0577.cn/news/46372.html

相关文章：

  • 福州培训网站建设抖音关键词排名软件
  • 北京市建设投标网站天门网站建设
  • 网站怎么做短信ip限定一个域名大概能卖多少钱
  • 响应式网站模板分享宁波seo深度优化平台有哪些
  • 免费视频素材下载的网站免费顶级域名注册网站
  • 网站收录 作用口碑营销名词解释
  • 湘潭网站建设湘潭振企专业系统优化的方法
  • 企业网站制作公司云南网络营销公司
  • 社交app网站开发长沙网站设计
  • 企业宣传网站在哪里做深圳经济最新新闻
  • 网站 技术支持爱站数据
  • 优科技网站建设最好用的手机优化软件
  • 网站建设zhongguoweb营销渠道的三个类型
  • 推广平台网站制作网络营销推广方式包括哪些
  • 网站建设报价单 excel网站结构优化的内容和方法
  • 上海网站建设seodian宁波网站关键词优化公司
  • 网页制作与网站建设技术大全 pdf怎么免费创建网站
  • 网站建设制作公司地址模板建站流程
  • king cms网站建设注册网站免费注册
  • 安徽网站开发武汉网站推广
  • 电脑什么网站可以做长图攻略网络营销有几种方式
  • 保定网站优化如何设计与制作网页
  • 宁波网站建设公司哪个好互联网舆情
  • 个人简历电子版可编辑seo博客教程
  • 怎么给网站做优化真实的优化排名
  • 花生壳官网免费域名申请seo资料站
  • 网站的网络推广策略有哪些googleseo优化
  • www 上海网站建设网站源码
  • 修改dns连接外国网站3天引流800个人技巧
  • 浏览器不限制访问网站网站查询ip