国家电子商务平台,上海专业seo服务公司,网络营销的机遇和挑战,p2p金融网站开发方案【本节要点】 二叉搜索树#xff08;BST#xff09;基本原理代码实现核心操作实现辅助函数测试代码完整代码 一、二叉搜索树#xff08;BST#xff09;基本原理与设计总结
注#xff1a;基本原理的详细分析可以在数据结构第六节中查看#xff0c;这里是简单描述。 二叉搜… 【本节要点】 二叉搜索树BST基本原理代码实现核心操作实现辅助函数测试代码完整代码 一、二叉搜索树BST基本原理与设计总结
注基本原理的详细分析可以在数据结构第六节中查看这里是简单描述。 二叉搜索树Binary Search Tree是一种特殊的二叉树结构具有以下核心性质 有序性每个节点的左子树所有节点值均小于当前节点值 递归结构每个节点的右子树所有节点值均大于当前节点值 动态维护通过插入和删除操作维护树的有序性 其时间复杂度特性为在平衡状态下插入、删除、查找操作的平均时间复杂度为O(log n)最坏情况下退化为链表结构时间复杂度为O(n) 在这里本设计使用了两个版本来实现二叉搜索树K版本和KV版本 K版本 声明并定义命名空间 K。实现了 BSTree 类这个类主要用于存储和操作单一的关键字Key。每个节点包含一个键 _key并且提供了插入Insert、查找Find和删除Erase等操作主要用于简单的关键字搜索和管理。 KV版本 实现了 BSTree 类这个类用于存储和操作键值对Key-Value Pair。每个节点包含一个键 _key 和一个值 _value并且提供了插入键值对Insert、通过键查找节点Find等操作。主要用于需要关联数据存储和检索的场景例如统计单词出现次数、存储配置信息等。 同时本设计使用了两个版本来实现增删查改与遍历的操作迭代版和递归版
设计思维导图 二、代码实现 2.1 节点结构定义K版本 在实现二叉搜索树之前首先需要定义树的结构。基本的二叉搜索树由节点组成每个节点包含一个键值Key、一个指向左子节点的指针Left和一个指向右子节点的指针Right。 下面是二叉搜索树节点的定义示例
templateclass K
struct BSTreeNode {BSTreeNodeK* _left; // 左子树指针BSTreeNodeK* _right; // 右子树指针K _key; // 存储的关键字BSTreeNode(const K key) // 构造函数:_left(nullptr), _right(nullptr), _key(key){}
}; 2.2 类框架与成员函数K版本 二叉搜索树的操作主要通过BSTree类来实现。该类包括树的根节点指针以及各种操作函数如插入Insert、查找Find、删除Erase等。 下面是BSTree类的一个基本实现示例
templateclass K
class BSTree {typedef BSTreeNodeK Node;
public:核心接口 bool Insert(const K key);bool Erase(const K key);bool Find(const K key);// 递归版本接口 //bool InsertR(const K key);bool EraseR(const K key);内部实现 void InOrder();~BSTree();
private:Node* _root nullptr; // 根节点指针
}; 2.3 节点结构定义KV版本 核心特性 双数据成员_key用于维护树结构_value存储关联数据 强类型约束构造函数强制要求同时初始化键值对 指针类型使用模板参数确保类型安全 // 定义支持键值对的二叉搜索树节点模板结构体
templateclass K, class V
struct BSTreeNode {BSTreeNodeK, V* _left; // 左子树指针BSTreeNodeK, V* _right; // 右子树指针K _key; // 键用于排序和索引V _value; // 值关联的存储数据// 构造函数必须同时初始化键值对BSTreeNode(const K key, const V value): _left(nullptr), _right(nullptr),_key(key),_value(value){}
}; 2.4 类框架与成员函数KV版本 成员函数详解 插入操作 参数必须同时提供键和值 特性保持二叉搜索树性质键唯一 时间复杂度O(h)h为树高度 查找操作 返回值节点指针可直接修改关联的_value 应用场景字典查找、配置项修改 遍历操作 输出格式key:value键值对形式 遍历顺序按键的中序升序排列 templateclass K, class V
class BSTree {typedef BSTreeNodeK, V Node; // 类型别名定义
public:核心接口 // 插入键值对迭代实现bool Insert(const K key, const V value);// 查找键对应的节点返回节点指针便于修改值Node* Find(const K key);// 中序遍历打印键值对void Inorder();private:内部实现 // 递归中序遍历实现void _Inorder(Node* root);// 根节点指针私有维护树结构Node* _root nullptr;
};
与K版本的关键差异
特性K版本KV版本节点数据单一_key_key _value插入参数单个键键值对查找返回值bool节点指针应用场景存在性检查数据关联存储构造函数要求允许默认构造必须显式初始化键值对 三、核心操作实现详解 3.1 插入操作迭代版 实现要点 空树直接创建根节点 循环查找插入位置维护parent指针 比较节点值决定插入方向 时间复杂度O(h)h为树高度 bool Insert(const K key) {if (_root nullptr) { // 空树处理_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;while (cur) { // 搜索插入位置parent cur;if (cur-_key key) cur cur-_right;else if (cur-_key key) cur cur-_left;else return false; // 已存在相同key}cur new Node(key); // 创建新节点// 链接到父节点if (parent-_key key) parent-_right cur;else parent-_left cur;return true;
} 3.2 删除操作迭代版 删除策略 单子树节点直接提升子树 双子树节点寻找右子树最小节点进行值替换 根节点处理需要特殊处理根指针 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{// 1、左为空// 2、右为空// 3、左右都不为空替换删除if (cur-_left nullptr){//if (parent nullptr)if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//if (parent nullptr)if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 右子树的最小节点Node* parent cur;Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}cur-_key minRight-_key;if (minRight parent-_left){parent-_left minRight-_right;}else{parent-_right minRight-_right;}delete minRight;}return true;}}return false;} 3.3 查找操作迭代版 时间复杂度分析 情况时间复杂度说明最佳情况O(1)目标节点为根节点平均情况O(log n)树接近平衡时最坏情况O(n)树退化为链表如有序插入 边界情况处理 空树处理初始时cur nullptr直接返回nullptr 键不存在处理循环自然结束返回nullptr 重复键处理由于插入时禁止重复键查找时不会遇到重复情况 // KV版本二叉搜索树的查找操作迭代实现
Node* Find(const K key) {Node* cur _root; // 从根节点开始搜索while (cur ! nullptr) { // 当当前节点存在时循环if (key cur-_key) { // 目标键大于当前节点键cur cur-_right; // 转向右子树搜索} else if (key cur-_key) { // 目标键小于当前节点键cur cur-_left; // 转向左子树搜索}else { // 找到匹配键return cur; // 返回目标节点指针}}return nullptr; // 遍历结束未找到返回空指针
} 3.4 增删查改递归版
// 插入递归实现
bool InsertR(const K key)
{return _InsertR(_root, key);
}
// 删除递归实现
bool EraseR(const K key)
{return _EraseR(_root, key);
}
// 查找递归实现
bool FindR(const K key)
{return _EraseR(_root, key);
}
递归与迭代实现对比
特性递归实现迭代实现代码复杂度简洁约10行复杂需维护parent指针空间效率O(h)栈空间O(1)额外空间可读性更符合算法逻辑需要显式指针操作栈溢出风险树高度1000时可能发生无风险 四、辅助函数
4.1 中序遍历 中序遍历是一种遍历二叉树的方式按照访问左子树——根节点——右子树的顺序进行。对于二叉搜索树中序遍历会按照节点键值的升序访问所有节点这是一种非常有用的遍历方式因为它可以生成树的有序列表。 以下是中序遍历的递归实现代码 // 中序遍历递归实现
void InOrder()
{_InOrder(_root);cout endl; 在这段代码中InOrder函数通过调用辅助函数_InOrder来实现递归遍历。_InOrder函数首先递归遍历左子树然后打印当前节点的键值最后递归遍历右子树。通过这种方式可以按照从小到大的顺序打印树中的所有节点。 4.2 树的销毁与拷贝 销毁二叉搜索树是指释放树中所有节点占用的内存空间。销毁操作通常在二叉搜索树不再需要时调用以确保不浪费内存资源。销毁操作可以通过递归实现从根节点开始先递归销毁左子树和右子树然后再销毁根节点。 以下是销毁二叉搜索树的代码实现 templateclass K
void BSTreeK::Destroy(BSTreeNodeK* root) {if (root nullptr) {return;}Destroy(root-_left);Destroy(root-_right);delete root;
} 在这段代码中Destroy函数通过递归调用自身先销毁左子树再销毁右子树最后销毁根节点从而释放整个树的内存空间。 拷贝二叉搜索树是指创建一个新的二叉搜索树其结构与原树完全相同节点的值也相同。拷贝操作通常在需要复制二叉搜索树时使用。拷贝操作同样可以通过递归实现从根节点开始先递归拷贝左子树和右子树然后再创建新节点并将其键值设置为原节点的键值。 以下是拷贝二叉搜索树的代码实现 templateclass K
BSTreeNodeK* BSTreeK::Copy(BSTreeNodeK* root) {if (root nullptr) {return nullptr;}BSTreeNodeK* newRoot new BSTreeNodeK(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;
} 在这段代码中Copy函数通过递归调用自身先拷贝左子树再拷贝右子树最后创建新节点并将其键值设置为原节点的键值从而生成与原树结构相同的新树。 五、测试代码 5.1 基本功能验证TestBSTree1
void TestBSTree1() {int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};K::BSTreeint t;// 测试递归插入for (auto e : a) t.InsertR(e); t.InOrder(); // 输出1 3 4 6 7 8 10 13 14// 测试拷贝构造函数K::BSTreeint copyt(t);copyt.InOrder(); // 应与原树输出一致// 测试插入新键t.InsertR(9);t.InOrder(); // 新增91 3 4 6 7 8 9 10 13 14// 测试迭代删除t.Erase(14); // 删除叶子节点t.InOrder(); // 14消失// 测试递归删除t.EraseR(3); // 删除有子树的节点t.EraseR(8); // 删除根节点t.InOrder(); // 输出剩余节点// 清空树for (auto e : a) {t.EraseR(e); // 删除所有元素t.InOrder(); // 逐步输出删除过程}
}
验证内容 插入操作的递归实现正确性拷贝构造函数实现深拷贝混合使用迭代和递归删除的兼容性树结构动态变化时的平衡性析构函数内存释放验证通过逐步删除 输出结果 5.2 字典应用TestBSTree2
void TestBSTree2() {KV::BSTreestring, string dict;// 构建词典dict.Insert(sort, 排序);dict.Insert(string, 字符串);dict.Insert(left, 左边);dict.Insert(right, 右边);// 交互式查询string str;while (cin str) {auto* ret dict.Find(str);if (ret) cout ret-_value endl;else cout 无此单词 endl;}
}
操作示例
输入sort → 输出排序
输入apple → 输出无此单词
输入left → 输出左边
验证内容 键值对插入的正确性 查找功能返回完整节点信息 交互式查询的稳定性 处理不存在键的鲁棒性 输出结果 5.3 统计应用TestBSTree3
void TestBSTree3() {string arr[] {苹果, 西瓜, 香蕉, 草莓, 苹果, /*...*/};KV::BSTreestring, int countTree;// 统计词频for (auto e : arr) {auto* ret countTree.Find(e);if (ret) ret-_value; // 存在则计数1else countTree.Insert(e, 1); // 不存在则插入}countTree.Inorder(); // 按键升序输出统计结果
}
预期输出
苹果:7
草莓:1
西瓜:3
香蕉:3
验证内容 动态更新值的能力 统计逻辑的正确性 中序遍历的有序性 混合插入与查找的稳定性
输出结果 六、完整代码
6.1 BSTree.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
using namespace std;
/*
* 声明并定义 命名空间 K
* 实现了 BSTree 类这个类主要用于存储和操作单一的关键字Key。
* 每个节点包含一个键 _key并且提供了插入Insert、查找Find和删除Erase等操作。
* 主要用于简单的关键字搜索和管理。
*/
namespace K
{// 定义二叉搜索树结点模板结构体 Ktemplateclass Kstruct BSTreeNode{BSTreeNodeK* _left; // 指针左孩子BSTreeNodeK* _right; // 指针右孩子K _key; // 数据存储该结点实际数据(单一的关键字)// 构建函数BSTreeNode(const K key):_left(nullptr), _right(nullptr),_key(key){}};// 定义二叉搜索树模板类 Ktemplateclass Kclass BSTree{// 使用Node作为二叉搜索树结点的别名typedef BSTreeNodeK Node;public://K 结构体结点 需要默认构造函数以便在没有提供关键字的情况下创建节点。一、默认成员函数// 1.1 构造函数BSTree():_root(nullptr){}// 1.2 拷贝构造BSTree(const BSTreeK t){_root Copy(t._root);}// 1.3 操作符重载BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}// 1.4 析构函数~BSTree(){Destroy(_root);_root nullptr;}二、二叉搜索树操作// 2.1 插入迭代实现// 根节点为空创建新结点键值已存在返回false键值不存在找到合适位置插入新结点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;}// 2.2 删除迭代实现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{// 1、左为空// 2、右为空// 3、左右都不为空替换删除if (cur-_left nullptr){//if (parent nullptr)if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//if (parent nullptr)if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 右子树的最小节点Node* parent cur;Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}cur-_key minRight-_key;if (minRight parent-_left){parent-_left minRight-_right;}else{parent-_right minRight-_right;}delete minRight;}return true;}}return false;}// 2.3 查找迭代实现// 从根节点开始找找到返回true否则返回 falsebool 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;}// 2.4 中序遍历递归实现void InOrder(){_InOrder(_root);cout endl;}// 2.5 插入递归实现bool InsertR(const K key){return _InsertR(_root, key);}// 2.6 删除递归实现bool EraseR(const K key){return _EraseR(_root, key);}// 2.7 查找递归实现bool FindR(const K key){return _EraseR(_root, key);}private:三、二叉搜索树结点操作// 3.1 销毁结点void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}// 3.2 拷贝结点Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}// 3.3 删除结点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-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}swap(root-_key, minRight-_key);// 转换成在子树中去删除节点return _EraseR(root-_right, key);}delete del;return true;}}// 3.4 插入结点bool _InsertR(Node* root, const K key){if (root nullptr){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);elsereturn false;}// 3.5 查找结点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);elsereturn true;}// 3.6 中序遍历结点void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;};}/*
* 实现了 BSTree 类这个类用于存储和操作键值对Key-Value Pair。
*每个节点包含一个键 _key 和一个值 _value并且提供了插入键值对Insert、通过键查找节点Find等操作。
*主要用于需要关联数据存储和检索的场景例如统计单词出现次数、存储配置信息等。
*/namespace KV
{// 定义二叉搜索树结点模板结构体 KVtemplateclass K,class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key; // 用于确定节点在二叉搜索树中的位置和排序是树的索引和查找依据V _value; // 用于存储与 _key 相关的数据提供额外的信息存储和检索能力// 构建函数BSTreeNode(const K key,const V value):_left(nullptr),_right(nullptr),_key(key),_value(value){}};/*这里KV不需要默认成员函数* KV 结构体结点 由于总是需要提供键值对来创建节点因此不需要默认构造函数。* 在实际编程中构造函数的目的是为了确保对象在创建时能够正确初始化其成员变量。*对于包含多个成员变量的类来说如果没有提供所有成员变量的初始化参数则需要默认构造函数来确保对象能够被正确创建。*/// 定义二叉搜索树模板类 KVtemplateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:二叉搜索树操作// 插入bool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);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, value);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* 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 cur;}}return nullptr;}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_key : root-_value endl;_Inorder(root-_right);}private:Node* _root nullptr;};
}
6.2 Test.cpp
#include BSTree.h
void TestBSTree1()
{int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };K::BSTreeint t;for (auto e : a){t.InsertR(e);}t.InOrder();K::BSTreeint copyt(t);copyt.InOrder();t.InsertR(9);t.InOrder();t.Erase(14);t.InOrder();t.EraseR(3);t.InOrder();t.EraseR(8);t.InOrder();for (auto e : a){t.EraseR(e);t.InOrder();}
}void TestBSTree2()
{// 场景检查单词拼写是否正确/车库出入系统/...//K::BSTreestring dict;// Key/Value的搜索模型,通过Key查找或修改ValueKV::BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(string, 字符串);dict.Insert(left, 左边);dict.Insert(right, 右边);string str;while (cin str){KV::BSTreeNodestring, string* ret dict.Find(str);if (ret){cout ret-_value endl;}else{cout 无此单词 endl;}}
}void TestBSTree3()
{// 统计水果出现的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓,苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };KV::BSTreestring, int countTree;for (auto e : arr){auto* ret countTree.Find(e);if (ret nullptr){countTree.Insert(e, 1);}else{ret-_value;}}countTree.Inorder();
}
int main()
{TestBSTree3();return 0;
}
以上就是关于二叉搜索树的设计总结如果有发现问题的小伙伴请在评论区说出来哦。后面还会持续更新C相关知识感兴趣请持续关注我哦
