二叉搜索樹(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;
}
碼字不易,求關注