树（Trees）
树是一种非线性数据结构，用于表示具有层次关系的数据。树由节点（nodes）组成，节点之间通过边（edges）连接。树的根节点（root node）位于顶部，其他节点通过分支（branches）连接。树的每个节点可以有零个或多个子节点（child nodes），没有子节点的节点称为叶节点（leaf nodes）。
树的基本术语
- 节点（Node）： 树中的基本单元，包含数据和指向其子节点的链接。
- 根节点（Root Node）： 树的最顶端节点，没有父节点。
- 父节点（Parent Node）： 一个节点的上一级节点。
- 子节点（Child Node）： 一个节点的下一级节点。
- 叶节点（Leaf Node）： 没有子节点的节点。
- 兄弟节点（Sibling Nodes）： 具有相同父节点的节点。
- 路径（Path）： 从一个节点到另一个节点的序列。
- 深度（Depth）： 从根节点到某节点的路径长度。
- 高度（Height）： 从某节点到其最远叶节点的路径长度。
- 子树（Subtree）： 以某个节点为根的树。
常见的树类型
- 二叉树（Binary Tree）： 每个节点最多有两个子节点，分别称为左子节点和右子节点。特殊形式包括完全二叉树、满二叉树、平衡二叉树等。
- 二叉搜索树（Binary Search Tree, BST）：
二叉树的一种，其中每个节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。
支持高效的查找、插入和删除操作。 - AVL树： 一种自平衡二叉搜索树，任何节点的两个子树的高度最大差别为1。 保证了树的高度总是对数级别的，从而保证了高效的操作。
- 红黑树（Red-Black Tree）： 一种自平衡二叉搜索树，通过颜色属性来保持树的平衡。 广泛应用于各种数据结构和算法中，如 C++
标准库中的 std::set 和 std::map。 - B树： 一种自平衡的搜索树，可以有多个子节点。 常用于文件系统和数据库系统中，支持高效的磁盘读写操作。
- B+树： B树的一种变体，所有数据都存储在叶节点上，叶节点之间有指针相连。 适合用于外部存储，如数据库索引。
- 堆（Heap）： 一种特殊的完全二叉树，分为最大堆和最小堆。 最大堆中每个节点的值都大于或等于其子节点的值，最小堆则相反。
常用于实现优先队列。
树的应用
- 文件系统： 文件系统中的目录结构可以用树来表示，每个目录是一个节点，文件是叶节点。
- 数据库索引： B树和B+树广泛用于数据库索引，支持高效的查找和范围查询。
- 编译器： 编译器中的语法树用于表示程序的结构，便于解析和优化。
- 网络路由： 路由表可以用树来表示，支持高效的路由查找。
- 游戏AI： 游戏中的决策树可以用来表示不同的策略和动作。
树的遍历
- 前序遍历（Pre-order Traversal）： 访问根节点 -> 递归遍历左子树 -> 递归遍历右子树。
- 中序遍历（In-order Traversal）： 递归遍历左子树 -> 访问根节点 -> 递归遍历右子树。二叉搜索树的中序遍历结果是有序的。
- 后序遍历（Post-order Traversal）： 递归遍历左子树 -> 递归遍历右子树 -> 访问根节点。
- 层次遍历（Level-order Traversal）： 按照从上到下、从左到右的顺序逐层访问节点。
#include <iostream>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};void preorderTraversal(TreeNode* root) {if (root == nullptr) return;std::cout << root->val << " ";preorderTraversal(root->left);preorderTraversal(root->right);
}void inorderTraversal(TreeNode* root) {if (root == nullptr) return;inorderTraversal(root->left);std::cout << root->val << " ";inorderTraversal(root->right);
}void postorderTraversal(TreeNode* root) {if (root == nullptr) return;postorderTraversal(root->left);postorderTraversal(root->right);std::cout << root->val << " ";
}int main() {// 创建一个简单的二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);std::cout << "Pre-order traversal: ";preorderTraversal(root);std::cout << std::endl;std::cout << "In-order traversal: ";inorderTraversal(root);std::cout << std::endl;std::cout << "Post-order traversal: ";postorderTraversal(root);std::cout << std::endl;// 清理内存delete root->left->left;delete root->left->right;delete root->left;delete root->right;delete root;return 0;
}
图（Graphs）
图（Graph）是一种非线性数据结构，用于表示对象之间的复杂关系。图由节点（顶点，Vertices）和边（Edges）组成，可以用来表示多种现实世界的问题，如社交网络、交通网络、计算机网络等。
图的基本概念
- 顶点（Vertex）： 图中的基本单元，表示一个实体或对象。
- 边（Edge）： 连接两个顶点的线，表示顶点之间的关系。
- 权重（Weight）： 边上的数值，表示边的某种属性，如距离、成本等。
- 有向图（Directed Graph）： 边有方向的图，表示从一个顶点到另一个顶点的单向关系。
- 无向图（Undirected Graph）： 边没有方向的图，表示两个顶点之间的双向关系。
- 邻接（Adjacency）： 如果两个顶点之间有一条边直接相连，则称这两个顶点是相邻的。
- 路径（Path）： 从一个顶点到另一个顶点的一系列边。
- 连通图（Connected Graph）： 无向图中任意两个顶点之间都存在路径。
- 强连通图（Strongly Connected Graph）： 有向图中任意两个顶点之间都存在路径。
- 环（Cycle）： 一条从一个顶点出发，经过若干个顶点后回到起点的路径。
- 度（Degree）： 顶点的度表示与该顶点相连的边的数量。
- 入度（In-degree）：有向图中进入一个顶点的边的数量。
- 出度（Out-degree）：有向图中从一个顶点出发的边的数量。
图的表示方法
- 邻接矩阵（Adjacency Matrix）： 一个二维数组，A[i][j] 表示顶点 i 和顶点 j 之间的关系。适用于稠密图，占用空间较大。
- 邻接表（Adjacency List）： 一个数组，每个元素是一个链表，链表中的每个节点表示与当前顶点相邻的顶点。适用于稀疏图，占用空间较小。
- 边列表（Edge List）： 一个数组或列表，每个元素是一个边的表示（如一对顶点）。 适用于简单图，不便于快速查找顶点的邻居。
图的常见操作
- 添加顶点： 在图中增加一个新的顶点。
- 添加边： 在图中增加一条新的边。
- 删除顶点： 从图中移除一个顶点及其相关的边。
- 删除边： 从图中移除一条边。
- 查找顶点： 判断图中是否存在某个顶点。
- 查找边： 判断图中是否存在某条边。
遍历图：
- 深度优先搜索（DFS）：从一个顶点开始，沿着一条路径尽可能深入地访问顶点，直到无法继续为止，然后回溯。
- 广度优先搜索（BFS）：从一个顶点开始，先访问其所有相邻的顶点，再依次访问这些顶点的相邻顶点。
图的应用
- 社交网络： 表示用户之间的关系，如好友关系、关注关系等。
- 交通网络： 表示城市之间的道路连接，用于路径规划和交通流量分析。
- 计算机网络： 表示设备之间的连接，用于网络拓扑分析和路由选择。
- 推荐系统： 表示用户和物品之间的关系，用于个性化推荐。
- 地图应用： 表示地理位置之间的连接，用于导航和路线规划。
- 电路设计： 表示电路元件之间的连接，用于电路仿真和优化。
简单的无向图的实现及其深度优先搜索和广度优先搜索
#include <iostream>
#include <vector>
#include <queue>
#include <stack>class Graph {
public:Graph(int n) : n(n), adj(n) {}void addEdge(int u, int v) {adj[u].push_back(v);adj[v].push_back(u); // 无向图}void DFS(int start) {std::vector<bool> visited(n, false);dfsUtil(start, visited);}void BFS(int start) {std::vector<bool> visited(n, false);bfsUtil(start, visited);}private:int n;std::vector<std::vector<int>> adj;void dfsUtil(int u, std::vector<bool>& visited) {visited[u] = true;std::cout << u << " ";for (int v : adj[u]) {if (!visited[v]) {dfsUtil(v, visited);}}}void bfsUtil(int start, std::vector<bool>& visited) {std::queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int u = q.front();q.pop();std::cout << u << " ";for (int v : adj[u]) {if (!visited[v]) {visited[v] = true;q.push(v);}}}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 3);std::cout << "Depth First Traversal (starting from vertex 0): ";g.DFS(0);std::cout << std::endl;std::cout << "Breadth First Traversal (starting from vertex 0): ";g.BFS(0);std::cout << std::endl;return 0;
}
堆（Heap）
堆（Heap）是一种特殊的完全二叉树，通常用于实现优先队列（Priority Queue）。堆有两种主要类型：最大堆（Max Heap）和最小堆（Min Heap）。在这两种堆中，每个节点的值都满足一定的条件，使得堆的根节点具有特殊的意义。
堆的基本概念
- 节点（Node）： 堆中的基本单元，包含数据。
- 根节点（Root Node）： 堆的最顶端节点，通常位于数组的索引 0 位置。
- 父节点（Parent Node）： 一个节点的上一级节点。对于索引为 i 的节点，其父节点的索引为 (i - 1) / 2。
- 子节点（Child Node）： 一个节点的下一级节点。对于索引为 i 的节点，其左子节点的索引为 2 * i + 1，右子节点的索引为
2 * i + 2。
堆的类型
- 最大堆（Max Heap）： 每个节点的值都大于或等于其子节点的值。根节点是堆中最大的元素。
- 最小堆（Min Heap）： 每个节点的值都小于或等于其子节点的值。 根节点是堆中最小的元素。
堆的操作
- 插入元素（Insert）： 将新元素添加到堆的末尾。 通过“上滤”（Percolate Up）操作，将新元素移动到合适的位置，以保持堆的性质。
- 删除根节点（Delete Root）： 移除根节点。 将最后一个元素移到根节点的位置。 通过“下滤”（Percolate Down）操作，将新根节点移动到合适的位置，以保持堆的性质。
- 构建堆（Build Heap）： 从一个无序数组构建堆。 通过“下滤”操作，从最后一个非叶子节点开始，逐步调整堆的结构。 堆的应用优先队列（Priority Queue）： 堆是实现优先队列的常用数据结构，支持高效的插入和删除操作。
- 堆排序（Heap Sort）： 一种基于堆的排序算法，时间复杂度为 O(n log n)。
- Dijkstra算法： 用于求解单源最短路径问题，优先队列通常使用堆来实现。
- Huffman编码： 用于数据压缩，构建最优前缀码树时使用最小堆。
简单的最小堆的实现及其基本操作
#include <iostream>
#include <vector>
#include <algorithm>class MinHeap {
public:MinHeap() {}void insert(int value) {heap.push_back(value);percolateUp(heap.size() - 1);}int extractMin() {if (heap.empty()) {throw std::runtime_error("Heap is empty");}int min = heap[0];heap[0] = heap.back();heap.pop_back();percolateDown(0);return min;}int getMin() const {if (heap.empty()) {throw std::runtime_error("Heap is empty");}return heap[0];}bool empty() const {return heap.empty();}size_t size() const {return heap.size();}private:std::vector<int> heap;void percolateUp(int index) {while (index > 0) {int parent = (index - 1) / 2;if (heap[parent] <= heap[index]) {break;}std::swap(heap[parent], heap[index]);index = parent;}}void percolateDown(int index) {int n = heap.size();while (true) {int left = 2 * index + 1;int right = 2 * index + 2;int smallest = index;if (left < n && heap[left] < heap[smallest]) {smallest = left;}if (right < n && heap[right] < heap[smallest]) {smallest = right;}if (smallest == index) {break;}std::swap(heap[index], heap[smallest]);index = smallest;}}
};int main() {MinHeap heap;heap.insert(3);heap.insert(1);heap.insert(4);heap.insert(1);heap.insert(5);heap.insert(9);std::cout << "Min element: " << heap.getMin() << std::endl;while (!heap.empty()) {std::cout << heap.extractMin() << " ";}std::cout << std::endl;return 0;
}