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

有什么做宝宝辅食的网站吗优秀营销软文范例500字

news 2025/8/13 12:22:22

有什么做宝宝辅食的网站吗,优秀营销软文范例500字,自己在线制作logo免费模板,北京便宜做网站本期内容我们讲解二叉树的进阶知识，没有看过之前内容的小伙伴建议先看往期内容二叉树-----补充_KLZUQ的博客-CSDN博客目录二叉搜索树代码实现基础框架 Insert Find Erase 析构函数拷贝构造赋值二叉搜索树的应用全部代码二叉搜索树二叉搜索树…

本期内容我们讲解二叉树的进阶知识，没有看过之前内容的小伙伴建议先看往期内容

二叉树-----补充_KLZUQ的博客-CSDN博客

二叉搜索树

代码实现

基础框架

Insert

Find

Erase

析构函数

拷贝构造

赋值

二叉搜索树的应用

全部代码

二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树 ，或者是具有以下性质的二叉树 :

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

由于结构特性，二叉搜索树很适合查找数据，那它最多查找多少次呢？高度次吗？

其实不是的，二叉搜索树是可能会有右边这种情况的，时间复杂度是O(N)

这其实是不好的，后面我们会讲AVL树和红黑树，他们的时间复杂度是O(longN)

话不多说，下面我们来实现二叉搜索树

代码实现

基础框架

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){}bool Insert(const K& key){}
private:Node* _root;
};

我们先写出基本框架，接着我们来实现插入

Insert

假设我们有这样一棵树，我们要插入11，13和16，该怎么办呢？我们将11和root节点对比，11比8大，应该在右边，继续对比11和10，比10大，在右边，11比14小，在左边，比13小，在左边

就成了这个样子，再看13，我们对比后发现树里面已经有13了，所以插入失败，最后看16，16比14大，链接在14的右边即可

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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else {return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else {parent->_left = cur;}return true;}

我们先用循环来实现

下面为了测试，我们写一个中序遍历

void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

我们写成子函数是因为我们在调用时还得传root，比如封装写成子函数，这样我们就不用传了，下面进行测试

没有问题，中序遍历出来是有序的

bool InsertR(const K& key){return _InsertR(_root, key);}
private:bool _InsertR(Node*& root, const K& key){if (root == nullptr)//因为引用，所以下面可以直接new{root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}

我们再看递归版本的，递归版本里参数加了引用，这个引用可以让我们在插入节点时不用找该节点的父亲节点，可谓是神之一手

Find

bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}

find也非常简单

bool FindR(const K& key){return _FindR(_root, key);}
private:bool _FindR(Node* root,const K& key)//递归版本{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}

还有递归版本的，我们再把子函数写成私有的

Erase

删除是一个重点，我们有这样一棵树，假设我们要删除7，14和3

7是叶子节点，删除后再把6的右置为空即可，14也还好说，它只有一个孩子，我们可以让10的右节点指向13，最麻烦的是3，我们该如何删除3呢？这里就要用到替换法，用3的左子树的最大节点或者右子树的最小节点来替换，一棵树的最大节点是这棵树的最右边的节点，所以左子树的最大节点很好找，最小的节点就是最左边的，所以右子树的最小节点也很好找

bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//找到了{//左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}		}//右为空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;}}			}//左右都不为空else{//找替代节点Node* parent = cur;//这里不能给空，防止leftMax是根节点的左子树的第一个节点Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_left;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}

删除要考虑的情况非常多，大家一定要画图才能理解

大家用这几张图画一画，结合代码，里面的坑是非常多的

下面我们测试一下

没有问题，大家测试时再把整棵树删空测试一下

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->_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;}}

我们再看递归版本，这里同样使用了引用，可以方便很多，大家画图对照一下就可以理解

下面我们再完成一下析构函数

析构函数

~BSTree(){Destroy(_root);}
void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}

也是同样使用引用，为了方便置空

拷贝构造

BSTree(const BSTree<K>& t){_root = Copy(t._root);}
Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyroot = new Node(root->_key);copyroot->_left = Copy(root->_left);copyroot->_right = Copy(root->_right);return copyroot;}

拷贝构造这里是不能调用insert的，因为任何顺序的插入都不能保证和原来树的一样，大家可以试一试，而我们这样写拷贝构造就可以解决问题

赋值

BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}

赋值的话我们直接用现代写法即可

二叉搜索树的应用

1. K 模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到 的值。

比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：

以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该种方式在现实生活中非常常见：

比如 英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英

文单词与其对应的中文 <word, chinese> 就构成一种键值对；

再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出

现次数就是 <word, count> 就构成一种键值对 。

下面我们修改我们上面的程序，把它变成KV的

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){}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->_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;}}bool _InsertR(Node*& root, const K& key,const V& value){if (root == nullptr)//因为引用，所以下面可以直接new{root = new Node(key,value);return true;}if (root->_key < key){return _InsertR(root->_right, key,value);}else if (root->_key > key){return _InsertR(root->_left, key,value);}else{return false;}}Node* _FindR(Node* root, const K& key)//递归版本{if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << ":"<<root->_value<<endl;_InOrder(root->_right);}private:Node* _root;};

这里我删除了一些，下面我们来进行测试

这里我们模拟一个字典

还有统计水果出现的次数，没有出现的水果我们存进去，出现的让value++

全部代码

namespace key
{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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//找到了{//左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//右为空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;}}}//左右都不为空else{//找替代节点Node* parent = cur;//这里不能给空，防止leftMax是根节点的左子树的第一个节点Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_left;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}void InOrder(){_InOrder(_root);cout << endl;}bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}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->_right);return copyroot;}void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}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;return true;}}bool _InsertR(Node*& root, const K& key){if (root == nullptr)//因为引用，所以下面可以直接new{root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}bool _FindR(Node* root, const K& key)//递归版本{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;};void Test(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.InsertR(e);}t.InOrder();t.EraseR(4);t.InOrder();t.EraseR(6);t.InOrder();t.EraseR(7);t.InOrder();t.EraseR(3);t.InOrder();for (auto e : a){t.Erase(e);}t.InOrder();}void Test2(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();BSTree<int> t1(t);t1.InOrder();}
}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){}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->_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;}}bool _InsertR(Node*& root, const K& key,const V& value){if (root == nullptr)//因为引用，所以下面可以直接new{root = new Node(key,value);return true;}if (root->_key < key){return _InsertR(root->_right, key,value);}else if (root->_key > key){return _InsertR(root->_left, key,value);}else{return false;}}Node* _FindR(Node* root, const K& key)//递归版本{if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << ":"<<root->_value<<endl;_InOrder(root->_right);}private:Node* _root;};void test(){BSTree<string, string> dict;dict.InsertR("insert", "插入");dict.InsertR("right", "右边");dict.InsertR("sort", "排序");dict.InsertR("left", "左边");dict.InsertR("date", "日期");string str;while (cin >> str){BSTreeNode<string, string>* ret = dict.FindR(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}}void test2(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (auto& str : arr){auto ret = countTree.FindR(str);if (ret == nullptr){countTree.InsertR(str, 1);}else{ret->_value++;}}countTree.InOrder();}
}

以上即为本期全部内容，希望大家可以有所收获

如有错误，还请指正