从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, vectorint result) const { if (!node) return; inorderTraversal(node-left, result); result.push_back(node-data); inorderTraversal(node-right, result); } void preorderTraversal(Node* node, vectorint result) const { if (!node) return; result.push_back(node-data); preorderTraversal(node-left, result); preorderTraversal(node-right, result); } void postorderTraversal(Node* node, vectorint result) const { if (!node) return; postorderTraversal(node-left, result); postorderTraversal(node-right, result); result.push_back(node-data); } void levelOrderTraversal(vectorint result) const { if (!root) return; queueNode* 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: vectorint inorder() const { vectorint result; inorderTraversal(root, result); return result; } vectorint preorder() const { vectorint result; preorderTraversal(root, result); return result; } vectorint postorder() const { vectorint result; postorderTraversal(root, result); return result; } vectorint levelOrder() const { vectorint 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; } }; BSTStudent 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}); } vectorStudent 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 散列表的性能优化散列表的性能很大程度上取决于哈希函数的设计和冲突解决策略。以下是一些优化技巧选择好的哈希函数应该均匀分布键减少冲突计算速度快对于整数键取模是常见选择对于字符串键可以使用多项式滚动哈希动态调整表大小当负载因子元素数量/表大小超过阈值如0.75时扩大表大小重新哈希所有元素到新表中开放寻址法另一种冲突解决策略当发生冲突时按照某种探测序列寻找下一个空槽// 动态调整表大小的示例代码 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_mapstring, 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 { vectorpairstring, 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 性能比较特性二叉排序树 (BST)散列表 (Hash Table)平均查找时间复杂度O(log n)O(1)最坏查找时间复杂度O(n) (退化为链表)O(n) (所有键哈希冲突)插入时间复杂度O(log n)O(1)删除时间复杂度O(log n)O(1)有序遍历支持 (中序遍历)不支持内存使用通常较少通常较多 (有未使用槽位)3.2 适用场景分析选择二叉排序树的情况需要有序遍历或范围查询键的分布可能导致大量哈希冲突内存资源非常有限需要稳定的性能避免哈希表最坏情况选择散列表的情况主要操作是查找且不需要有序遍历键的分布均匀哈希函数设计良好内存资源充足需要极快的平均查找速度3.3 实际项目中的权衡在实际项目中我们经常需要根据具体需求做出选择。例如学生信息管理系统如果需要按学号排序输出所有学生选择BST如果主要通过学号快速查找学生选择Hash Table如果两者都需要可以考虑同时使用两种结构或使用更高级的数据结构如TreeMap缓存系统通常选择Hash Table因为快速查找是关键如果需要实现LRU缓存可以结合哈希表和双向链表数据库索引范围查询多使用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 解决哈希冲突的其他方法除了链地址法还有以下几种常见的冲突解决方法开放寻址法线性探测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完美哈希适用于静态键集合两级哈希第一级将键分组第二级为每组使用不同的哈希函数布谷鸟哈希使用两个哈希函数和两个表插入时如果两个位置都占用踢出其中一个元素并重新插入4.3 面试常见问题与解答问题1如何实现一个支持范围查询的哈希表解决方案结合哈希表和跳表。哈希表提供O(1)的查找跳表维护有序的键序列支持范围查询。插入和删除时需要同时更新两种结构。问题2设计一个数据结构支持插入、删除和获取随机元素所有操作平均O(1)时间。解决方案使用动态数组存储元素配合哈希表存储元素到索引的映射。插入时添加到数组末尾并更新哈希表删除时将要删除元素与末尾元素交换然后删除并更新哈希表获取随机元素只需随机选择数组索引。class RandomizedSet { private: vectorint nums; unordered_mapint, 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_mapint, 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; } } } };