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

做ppt的网站叫什么软件广告设计方案

news 2025/9/17 1:34:30
做ppt的网站叫什么软件,广告设计方案,计算机程序网站开发是什么,中科汇联网站建设手册1.二叉搜索树概念 二叉搜索树又称二叉排序树、二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 非空左子树的所有键值小于其根节点的键值 2. 非空右子树的所有键值大于其根节点的键值 3. 左右子树也分别为二叉搜索树 二叉搜索树一般不支持…

1.二叉搜索树概念

二叉搜索树又称二叉排序树、二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树:
1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树也分别为二叉搜索树

二叉搜索树一般不支持key值冗余（不允许有重复的key值）
二叉搜索树的性质使搜索时非常方便高效，最多搜索高度次O(log N)（二叉树退化为O(N)，需要二叉搜索树平衡，使用AVL树或红黑树）
二叉搜索树的中序遍历能对key进行排序

二叉搜索树的应用：
K模型：K模型只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值
例如查找某个key值存不存在？
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对
key值不能冗余，但value值可以相同
例如key值为单词，value为对应单词的英文

 2.二叉搜索树操作（K模型为例）

2.1 二叉搜索树的查找

1. 从根节点开始查找，查找的key比cur(当前节点)的key大，则cur向右查找；查找的key比cur的key小，则cur向左查找，直到找到key值相同或查找的key值不存在。
2. 最多查找高度次，cur走到空，就说明查找的key不存在。

Node* find(const T& data)
{Node* cur = _root;while (cur){//找到返回if (data == cur->_data)return cur;//大于cur，向右找else if (data > cur->_data)cur = cur->_right;//小于cur，向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;
}

 2.2 二叉搜索树的插入

1. 树为空树时，则直接新增节点，并作为该对象的根节点(_root)。
2. 树不为空树时，按二叉树的性质查找位置并插入

bool insert(const T& data)
{//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data > parent->_data)parent->_right = cur;elseparent->_left = cur;return true;
}

 2.3 二叉搜索树的删除

查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点分四种情况：
1. 要删除的节点无孩子节点 -- 直接删除该节点
2. 要删除的节点只有左孩子节点 -- 让左孩子节点替代该节点位置，并删除该节点
3. 要删除的节点只有右孩子节点 -- 让右孩子节点替代该节点位置，并删除该节点
4. 要删除的节点有左右孩子节点 -- 由二叉树性质，查找删除节点的右子树key值最小节点，让最小节点的key覆盖掉删除节点的key，最小节点一定是只有一个右孩子节点或没有孩子节点的情况，按1或2删除最小节点。（最小节点不可能存在左孩子，不然就不是最小节点了，更不可能有两个孩子）

bool erase(const T& data)
{//空树，删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}
}

2.4 二叉搜索树代码（K模型和KV模型）

KV模型与K模型类似，只是KV模型的data类型是pair类型，first是key，second是value。

K模型：

namespace myBSTree_K
{template <class T>struct BSTNode{BSTNode(const T& data = T()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<T>* _left;BSTNode<T>* _right;T _data;};template <class T>class BSTree{typedef BSTNode<T> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree& tree){_root = _Copy(tree._root);}//析构函数无法传参，只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root = nullptr;}Node* find(const T& data){Node* cur = _root;while (cur){//找到返回if (data == cur->_data)return cur;//大于cur，向右找else if (data > cur->_data)cur = cur->_right;//小于cur，向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;}bool insert(const T& data){//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data > parent->_data)parent->_right = cur;elseparent->_left = cur;return true;}bool erase(const T& data){//空树，删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(const Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << ' ';_InOrder(root->_right);}//成员变量Node* _root;};
}

KV模型：

namespace myBSTree_KV
{template <class K, class V>struct BSTNode{BSTNode(const pair<K,V>& data = pair<K,V>()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<K,V>* _left;BSTNode<K,V>* _right;pair<K,V> _data;};template <class K, class V>class BSTree{typedef BSTNode<K,V> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree& tree){_root = _Copy(tree._root);}//析构函数无法传参，只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root = nullptr;}Node* find(const K& key){Node* cur = _root;while (cur){//找到返回if (key == cur->_data.first)return cur;//大于cur，向右找else if (key > cur->_data.first)cur = cur->_right;//小于cur，向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;}bool insert(const pair<K, V>& data){//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data.first > parent->_data.first)parent->_right = cur;elseparent->_left = cur;return true;}bool erase(const K& key){//空树，删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (key> cur->_data.first){parent = cur;cur = cur->_right;}else if (key < cur->_data.first){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}}//改--如果key相同，改value，如果key不存在，不改bool update(const pair<K, V>& data){Node* cur = find(data.first);if (cur == nullptr)return false;else{cur->_data.second = data.second;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(const Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data.first << ':' << root->_data.second << endl;_InOrder(root->_right);}//成员变量Node* _root;};
}

3. 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表二叉搜索树的各个操作的性能
对有n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多，但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2​N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N/2

二叉搜索树退化，使二叉搜索树性能丢失，需要使二叉搜索树平衡，可以使用AVL树和红黑树。

http://www.yayakq.cn/news/21259/

相关文章：

  • 荥阳网站建设公司做家居商城网站
  • 上海企业网站建设服务阿里云商标注册
  • 大学营销型网站建设实训课程网站建设推广是什么意思
  • 网站图片的作用南充网站建设公司
  • 站长工具无吗经典做阿里巴巴网站多少钱
  • 扬州住房城乡建设局网站网站首页设计特点有哪些
  • 上饶做网站静态网页模板简约
  • 初学者做网站c2c网站管理系统
  • ftp 企业网站购物网站项目建设内容
  • 什么软件可以做dj视频网站南京企业免费建站
  • 网站名字和域名西部数码网站管理助手 伪静态
  • 站长工具seo下载益韧建筑培训网
  • 三亚官方网站建设建设高端网站的公司
  • 上海金山网站建设微站和网站数据
  • 深圳西丽网站建设网页设计尺寸怎么测量
  • 免费网站推荐货源网站建设 外文文献
  • 网站项目签约怎么直播带货卖东西
  • ppt模板怎么做 下载网站wordpress页面里可不可以写php
  • 做网站挣外快seo01
  • 摄影 网站 模板html怎么下载安装
  • 青岛网站建设价格游戏网页制作模板
  • 简介网站建设流程套模板网站建设
  • dw怎样做网站链接安庆高端网站建设公司
  • 摄影网站的制作广州网站设计教程
  • 潍坊个人网站制作代码编程基础知识
  • 创建网站无法播放视频个人网站怎么做收款链接
  • 做网站收费提供低价网站建设
  • 宁波好品质品牌网站设计哪家好做外贸网站企业
  • 池州专业网站建设丽水市做网站的
  • 网上购物的网站有哪些wordpress自动采集aote