搜索二叉树-key的搜索模型
二叉搜索树(Binary Search Tree, BST)是一种重要的数据结构，它有两种基本模型：Key模型和Key/Value模型。
一、Key模型
1.基本概念
Key模型是二叉搜索树中最简单的形式，每个节点只存储一个键值(key)，没有额外的数据值(value)。这种模型主要用于判断某个键值是否存在树中。
2.Key模型的特点：
- 每个节点只包含一个键值(key)
- 节点的键值必须满足二叉搜索树的性质：左子节点的键值小于父节点，右子节点的键值大于父节点
- 不允许键值重复，即树中所有节点的键值都是唯一的
- 结构简单，适用于只需要判断元素是否存在的场景
3.典型的应用场景
- 单词拼写检查：将字典中的所有单词作为键值构建二叉搜索树，可以快速判断一个单词是否正确
- 门禁系统：存储所有授权人员的ID，快速验证某个ID是否有权限
- 数据去重：检查并确保集合中没有重复元素
单词拼写检查示例：
#include <iostream>
#include <string>// 定义二叉搜索树节点
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; // 节点类型别名private:
Node* _root = nullptr; // 根节点指针public:
// 构造函数
BSTree() : _root(nullptr) {}// 析构函数
~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;
}
}Node* newNode = new Node(key);
if (parent->_key < key)
{
parent->_right = newNode;
}
else {
parent->_left = newNode;
}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;
}private:
// 销毁树的辅助函数
void Destroy(Node* root)
{
if (root)
{
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
}
};int main()
{
BSTree<std::string> dictionary;// 初始化字典
dictionary.Insert("apple");
dictionary.Insert("banana");
dictionary.Insert("cherry");
dictionary.Insert("date");std::cout << "===== 单词拼写检查系统 =====" << std::endl;
std::cout << "已加载基础词典（4个单词）\n";
std::cout << "输入要验证的单词（输入 exit 退出）\n\n";std::string input;
while (true)
{
std::cout << "请输入单词: ";
std::cin >> input;if (input == "exit")
{
std::cout << "\n=== 感谢使用 ===" << std::endl;
break;
}if (dictionary.Find(input))
{
std::cout << "[正确] \"" << input << "\" 存在于词典中\n\n";
}
else
{
std::cout << "[警告] \"" << input
<< "\" 未在词典中找到，请注意拼写！\n\n";
}
}return 0;
}
二、Key/Value模型
1.基本概念
Key/Value模型是二叉搜索树的重要扩展形式，每个节点存储键值对(key-value pair)，支持通过key快速查找对应的value。这种模型是构建字典、索引等数据结构的核心基础。
2.核心特性
1. 键值对存储：每个节点存储唯一的key及其关联的value
2. 排序依据：仍然基于key维持二叉搜索树性质
3. 动态更新：允许通过相同key更新value
4. 高效查询：保持O(logN)平均查找时间复杂度
3.应用场景
-单词解释
-统计水果出现次数
统计水果出现次数代码示例：
#include <iostream>
#include <string>
#include <algorithm> // 用于大小写转换// 定义二叉搜索树节点
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;
Node* _root = nullptr;// 递归销毁子树
void Destroy(Node* root)
{
if (root)
{
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
}// 递归中序遍历打印
void _PrintInOrder(Node* root) const
{
if (root)
{
_PrintInOrder(root->_left);
std::cout << " " << root->_key << " : " << root->_value << "\n";
_PrintInOrder(root->_right);
}
}public:
BSTree() = default;~BSTree()
{
Destroy(_root);
}// 插入或递增计数
void InsertOrIncrement(const K& key)
{
if (!_root)
{
_root = new Node(key, 1);
return;
}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
{
++cur->_value;
return;
}
}Node* newNode = new Node(key, 1);
if (parent->_key < key)
{
parent->_right = newNode;
}
else {
parent->_left = newNode;
}
}// 打印统计结果
void PrintStatistics() const
{
std::cout << "\n===== 水果统计结果 =====\n";
_PrintInOrder(_root);
std::cout << "=======================\n";
}
};int main()
{
BSTree<std::string, int> fruitCounter;std::cout << "=== 水果统计系统 ===\n"
<< "输入水果名称进行统计（输入'q'结束）\n"
<< "（自动转换为小写，支持大小写混合输入）\n\n";std::string input;
while (true)
{
std::cout << "输入水果名称: ";
std::cin >> input;// 转换为小写
std::transform(input.begin(), input.end(), input.begin(),
[](unsigned char c) { return std::tolower(c); });if (input == "q") break;
fruitCounter.InsertOrIncrement(input);
}// 输出统计结果
fruitCounter.PrintStatistics();return 0;
}
单词解释代码示例：
#include <iostream>
#include <string>// 定义二叉搜索树节点
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; // 节点类型别名private:
Node* _root = nullptr; // 根节点指针public:
// 构造函数
BSTree() : _root(nullptr) {}// 析构函数
~BSTree()
{
Destroy(_root);
}// 插入操作
bool Insert(const K& key, const V& value)
{
if (!_root) { // 空树情况
_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 { // 键值已存在，更新value
cur->_value = value;
return false;
}
}// 创建新节点并插入
Node* newNode = new Node(key, value);
if (parent->_key < key)
{
parent->_right = newNode;
}
else
{
parent->_left = newNode;
}return true;
}// 查找操作
V* 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->_value;
}
}
return nullptr; // 查找失败
}private:
// 销毁树的辅助函数
void Destroy(Node* root)
{
if (root)
{
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
}
};
int main()
{
BSTree<std::string, std::string> dict;// 构建词典
dict.Insert("apple", "A round fruit with red, green, or yellow skin and a white inside.");
dict.Insert("banana", "A long curved fruit with yellow skin and soft sweet flesh.");// 交互查询
std::string word;
while (true)
{
std::cout << "Enter word to lookup (q to quit): ";
std::cin >> word;
if (word == "q") break;if (auto def = dict.Find(word))
{
std::cout << "Definition: " << *def << "\n\n";
}
else
{
std::cout << "Word not found. Add definition? (y/n) ";
char choice;
std::cin >> choice;
if (choice == 'y')
{
std::string newDef;
std::cout << "Enter definition: ";
std::cin.ignore();
std::getline(std::cin, newDef);
dict.Insert(word, newDef);
std::cout << "Added!\n\n";
}
}
}return 0;
}
码字不易，求关注
