从LeetCode到课程设计：如何用C++优雅实现二叉排序树与散列表（含插入、删除、遍历全操作）

从LeetCode到课程设计：C++实现二叉排序树与散列表的工程实践

在算法与数据结构的学习中，二叉排序树和散列表是两种极为重要的数据结构，它们在实际项目开发、课程设计和技术面试中都有广泛应用。本文将带你从工程实践的角度，深入探讨如何用C++优雅地实现这两种数据结构，并分析在不同场景下的选择策略。

1. 二叉排序树的C++实现与封装

二叉排序树（Binary Search Tree, BST）是一种特殊的二叉树，它满足以下性质：对于树中的每个节点，其左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。这一特性使得BST在查找、插入和删除操作上具有较高的效率。

1.1 BST的基本操作实现

让我们首先实现BST的基本操作：插入、查找和删除。我们将这些操作封装在一个类中，提高代码的复用性。

class BST { private: struct Node { int data; Node* left; Node* right; Node(int val) : data(val), left(nullptr), right(nullptr) {} }; Node* root; // 递归插入辅助函数 Node* insert(Node* node, int val) { if (!node) return new Node(val); if (val < node->data) node->left = insert(node->left, val); else if (val > node->data) node->right = insert(node->right, val); return node; } // 递归查找辅助函数 bool search(Node* node, int val) const { if (!node) return false; if (val == node->data) return true; if (val < node->data) return search(node->left, val); return search(node->right, val); } // 递归删除辅助函数 Node* remove(Node* node, int val) { if (!node) return nullptr; if (val < node->data) { node->left = remove(node->left, val); } else if (val > node->data) { node->right = remove(node->right, val); } else { if (!node->left) { Node* temp = node->right; delete node; return temp; } else if (!node->right) { Node* temp = node->left; delete node; return temp; } Node* temp = minValueNode(node->right); node->data = temp->data; node->right = remove(node->right, temp->data); } return node; } // 找到子树中的最小值节点 Node* minValueNode(Node* node) { Node* current = node; while (current && current->left) current = current->left; return current; } public: BST() : root(nullptr) {} void insert(int val) { root = insert(root, val); } bool search(int val) const { return search(root, val); } void remove(int val) { root = remove(root, val); } };

1.2 BST的遍历与高级操作

除了基本操作，BST还支持多种遍历方式，每种遍历都有其特定的应用场景：

• 中序遍历：按升序输出所有节点
• 前序遍历：可用于复制树结构
• 后序遍历：常用于删除整个树
• 层序遍历：按层级输出节点

// 在BST类中添加遍历方法 class BST { // ... 前面的代码不变 void inorderTraversal(Node* node, vector<int>& result) const { if (!node) return; inorderTraversal(node->left, result); result.push_back(node->data); inorderTraversal(node->right, result); } void preorderTraversal(Node* node, vector<int>& result) const { if (!node) return; result.push_back(node->data); preorderTraversal(node->left, result); preorderTraversal(node->right, result); } void postorderTraversal(Node* node, vector<int>& result) const { if (!node) return; postorderTraversal(node->left, result); postorderTraversal(node->right, result); result.push_back(node->data); } void levelOrderTraversal(vector<int>& result) const { if (!root) return; queue<Node*> q; q.push(root); while (!q.empty()) { Node* current = q.front(); q.pop(); result.push_back(current->data); if (current->left) q.push(current->left); if (current->right) q.push(current->right); } } public: vector<int> inorder() const { vector<int> result; inorderTraversal(root, result); return result; } vector<int> preorder() const { vector<int> result; preorderTraversal(root, result); return result; } vector<int> postorder() const { vector<int> result; postorderTraversal(root, result); return result; } vector<int> levelOrder() const { vector<int> result; levelOrderTraversal(result); return result; } };

1.3 BST在实际项目中的应用案例

BST在实际项目中有广泛的应用，下面我们看一个学生成绩管理系统的例子：

class StudentManager { private: struct Student { int id; string name; double score; bool operator<(const Student& other) const { return id < other.id; } bool operator>(const Student& other) const { return id > other.id; } }; BST<Student> studentTree; public: void addStudent(int id, const string& name, double score) { studentTree.insert({id, name, score}); } bool removeStudent(int id) { return studentTree.remove({id, "", 0.0}); } Student* findStudent(int id) { return studentTree.search({id, "", 0.0}); } vector<Student> getAllStudents() { return studentTree.inorder(); } };

在这个例子中，我们使用BST来存储学生信息，按照学号排序。这使得查找、插入和删除操作的时间复杂度平均为O(log n)，非常高效。

2. 散列表的C++实现与封装

散列表（Hash Table）是另一种高效的数据结构，它通过哈希函数将键映射到存储位置，理想情况下可以实现O(1)时间复杂度的查找、插入和删除操作。

2.1 链地址法实现散列表

链地址法是解决哈希冲突的一种常用方法，它将哈希到同一位置的元素存储在链表中。下面是C++实现：

class HashTable { private: struct Node { int key; string value; Node* next; Node(int k, const string& v) : key(k), value(v), next(nullptr) {} }; static const int TABLE_SIZE = 13; Node* table[TABLE_SIZE]; int hashFunction(int key) { return key % TABLE_SIZE; } public: HashTable() { for (int i = 0; i < TABLE_SIZE; ++i) { table[i] = nullptr; } } ~HashTable() { for (int i = 0; i < TABLE_SIZE; ++i) { Node* current = table[i]; while (current) { Node* temp = current; current = current->next; delete temp; } } } void insert(int key, const string& value) { int index = hashFunction(key); Node* newNode = new Node(key, value); if (!table[index]) { table[index] = newNode; } else { Node* current = table[index]; while (current->next) { if (current->key == key) { current->value = value; // 更新已有键的值 delete newNode; return; } current = current->next; } current->next = newNode; } } bool search(int key, string& value) const { int index = hashFunction(key); Node* current = table[index]; while (current) { if (current->key == key) { value = current->value; return true; } current = current->next; } return false; } bool remove(int key) { int index = hashFunction(key); Node* current = table[index]; Node* prev = nullptr; while (current) { if (current->key == key) { if (prev) { prev->next = current->next; } else { table[index] = current->next; } delete current; return true; } prev = current; current = current->next; } return false; } void print() const { for (int i = 0; i < TABLE_SIZE; ++i) { cout << i << ": "; Node* current = table[i]; while (current) { cout << "(" << current->key << "," << current->value << ") "; current = current->next; } cout << endl; } } };

2.2 散列表的性能优化

散列表的性能很大程度上取决于哈希函数的设计和冲突解决策略。以下是一些优化技巧：

1. 选择好的哈希函数：

   • 应该均匀分布键，减少冲突
   • 计算速度快
   • 对于整数键，取模是常见选择
   • 对于字符串键，可以使用多项式滚动哈希

2. 动态调整表大小：

   • 当负载因子（元素数量/表大小）超过阈值（如0.75）时，扩大表大小
   • 重新哈希所有元素到新表中

3. 开放寻址法：

   • 另一种冲突解决策略
   • 当发生冲突时，按照某种探测序列寻找下一个空槽

// 动态调整表大小的示例代码 void HashTable::resize(int newSize) { Node** newTable = new Node*[newSize]; for (int i = 0; i < newSize; ++i) { newTable[i] = nullptr; } int oldSize = TABLE_SIZE; TABLE_SIZE = newSize; for (int i = 0; i < oldSize; ++i) { Node* current = table[i]; while (current) { Node* next = current->next; int newIndex = hashFunction(current->key); current->next = newTable[newIndex]; newTable[newIndex] = current; current = next; } } delete[] table; table = newTable; }

2.3 散列表在实际项目中的应用案例

散列表非常适合实现高速缓存、字典和集合等数据结构。下面是一个单词频率统计的例子：

class WordCounter { private: unordered_map<string, int> wordCount; public: void processText(const string& text) { istringstream iss(text); string word; while (iss >> word) { // 简单清理单词 word.erase(remove_if(word.begin(), word.end(), [](char c) { return !isalpha(c); }), word.end()); transform(word.begin(), word.end(), word.begin(), ::tolower); if (!word.empty()) { wordCount[word]++; } } } int getCount(const string& word) const { auto it = wordCount.find(word); return it != wordCount.end() ? it->second : 0; } void printTopWords(int n) const { vector<pair<string, int>> sortedWords(wordCount.begin(), wordCount.end()); sort(sortedWords.begin(), sortedWords.end(), [](const auto& a, const auto& b) { return a.second > b.second; }); for (int i = 0; i < min(n, (int)sortedWords.size()); ++i) { cout << sortedWords[i].first << ": " << sortedWords[i].second << endl; } } };

3. 二叉排序树与散列表的比较与选择

在实际项目中，选择二叉排序树还是散列表取决于具体的应用场景和需求。下面我们从几个维度进行比较：

3.1 性能比较

3.2 适用场景分析

选择二叉排序树的情况：

1. 需要有序遍历或范围查询
2. 键的分布可能导致大量哈希冲突
3. 内存资源非常有限
4. 需要稳定的性能，避免哈希表最坏情况

选择散列表的情况：

1. 主要操作是查找，且不需要有序遍历
2. 键的分布均匀，哈希函数设计良好
3. 内存资源充足
4. 需要极快的平均查找速度

3.3 实际项目中的权衡

在实际项目中，我们经常需要根据具体需求做出选择。例如：

1. 学生信息管理系统：

   • 如果需要按学号排序输出所有学生：选择BST
   • 如果主要通过学号快速查找学生：选择Hash Table
   • 如果两者都需要：可以考虑同时使用两种结构，或使用更高级的数据结构如TreeMap

2. 缓存系统：

   • 通常选择Hash Table，因为快速查找是关键
   • 如果需要实现LRU缓存，可以结合哈希表和双向链表

3. 数据库索引：

   • 范围查询多：使用B+树（BST的扩展）
   • 等值查询多：使用Hash索引

4. 高级话题与面试常见问题

4.1 平衡二叉搜索树

普通BST在最坏情况下会退化为链表，导致性能下降。平衡二叉搜索树（如AVL树、红黑树）通过旋转操作保持树的平衡，确保操作时间复杂度为O(log n)。

// AVL树节点结构 struct AVLNode { int key; string value; int height; AVLNode* left; AVLNode* right; AVLNode(int k, const string& v) : key(k), value(v), height(1), left(nullptr), right(nullptr) {} }; // 获取节点高度 int getHeight(AVLNode* node) { return node ? node->height : 0; } // 计算平衡因子 int getBalance(AVLNode* node) { return node ? getHeight(node->left) - getHeight(node->right) : 0; } // 右旋转 AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; x->right = y; y->left = T2; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; x->height = max(getHeight(x->left), getHeight(x->right)) + 1; return x; } // 左旋转 AVLNode* leftRotate(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; y->left = x; x->right = T2; x->height = max(getHeight(x->left), getHeight(x->right)) + 1; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; return y; }

4.2 解决哈希冲突的其他方法

除了链地址法，还有以下几种常见的冲突解决方法：

1. 开放寻址法：

   • 线性探测：h(k, i) = (h'(k) + i) mod m
   • 二次探测：h(k, i) = (h'(k) + c₁i + c₂i²) mod m
   • 双重哈希：h(k, i) = (h₁(k) + i·h₂(k)) mod m

2. 完美哈希：

   • 适用于静态键集合
   • 两级哈希，第一级将键分组，第二级为每组使用不同的哈希函数

3. 布谷鸟哈希：

   • 使用两个哈希函数和两个表
   • 插入时如果两个位置都占用，踢出其中一个元素并重新插入

4.3 面试常见问题与解答

问题1：如何实现一个支持范围查询的哈希表？

解决方案：结合哈希表和跳表。哈希表提供O(1)的查找，跳表维护有序的键序列，支持范围查询。插入和删除时需要同时更新两种结构。

问题2：设计一个数据结构，支持插入、删除和获取随机元素，所有操作平均O(1)时间。

解决方案：使用动态数组存储元素，配合哈希表存储元素到索引的映射。插入时添加到数组末尾并更新哈希表；删除时将要删除元素与末尾元素交换，然后删除并更新哈希表；获取随机元素只需随机选择数组索引。

class RandomizedSet { private: vector<int> nums; unordered_map<int, int> valToIndex; public: bool insert(int val) { if (valToIndex.count(val)) return false; valToIndex[val] = nums.size(); nums.push_back(val); return true; } bool remove(int val) { if (!valToIndex.count(val)) return false; int index = valToIndex[val]; int lastVal = nums.back(); nums[index] = lastVal; valToIndex[lastVal] = index; nums.pop_back(); valToIndex.erase(val); return true; } int getRandom() { return nums[rand() % nums.size()]; } };

问题3：如何设计一个高效的LRU缓存？

解决方案：使用双向链表维护访问顺序，配合哈希表快速查找。最近访问的节点移动到链表头部，淘汰时从尾部移除。

class LRUCache { private: struct Node { int key; int value; Node* prev; Node* next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; int capacity; unordered_map<int, Node*> cache; Node* head; Node* tail; void addToHead(Node* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; } void moveToHead(Node* node) { removeNode(node); addToHead(node); } Node* popTail() { Node* res = tail->prev; removeNode(res); return res; } public: LRUCache(int capacity) : capacity(capacity) { head = new Node(-1, -1); tail = new Node(-1, -1); head->next = tail; tail->prev = head; } int get(int key) { if (!cache.count(key)) return -1; Node* node = cache[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (cache.count(key)) { Node* node = cache[key]; node->value = value; moveToHead(node); } else { Node* newNode = new Node(key, value); cache[key] = newNode; addToHead(newNode); if (cache.size() > capacity) { Node* tail = popTail(); cache.erase(tail->key); delete tail; } } } };