平衡二叉树的调整(左旋与右旋)
平衡二叉树平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它在结构上保持一定的平衡，以确保在最坏情况下依然具有较好的查找、插入和删除性能。 平衡二叉树的定义平衡的具体定义可以根据不同类型的平衡树略有不同。一般来说，一个二叉树是平衡的，当其任意节点的左右子树高度差的绝对值不超过某个特定值（通常是1）时。 常见类型的平衡二叉树 AVL树： 每个节点的左右子树高度差（平衡因子）只允许为 -1、0 或...
单源最短路径问题与Dijkstra算法
单源最短路径问题（Single Source Shortest Path, SSSP）是图论中的一个经典问题。它的目标是在一个加权图中，找到给定的起点（源点）到图中所有其他节点的最短路径。问题定义： 图：图可以是有向图或无向图，通常包含若干个节点和边，每条边都有一个非负权重（即从一个节点到另一个节点的代价或距离）。 起点（源点）：单源最短路径问题会指定一个起始节点，称为源节点，问题要求从这个源节点出发，计算它到图中其他所有节点的最短路径。 最短路径：最短路径是指从源节点到目标节点经过的路径中，总边权重之和最小的路径。 具体目标：对于给定的源节点s，你需要找到从s到每个其他节点v的最短路径长度，并且路径上的权重和最小。 常见的算法： Dijkstra算法： 解决边权非负的单源最短路径问题，时间复杂度为$O((V + E) \log V)$，适合稀疏图。 Bellman-Ford算法： 可以处理负权边的情况，且能够检测负权环，时间复杂度为$O(V \times...
kahn算法实现拓扑排序
1. 拓扑排序（Topological Sorting）是什么？拓扑排序是一种用于 有向无环图（DAG, Directed Acyclic Graph） 的节点排序算法。它的目标是将图中的所有节点排成一个 线性序列，使得对于图中每一条从节点 u 到节点 v 的有向边 u -> v，在排序中节点 u 都排在节点 v 的前面。 简单来说，如果图中有一条边 u -> v，那么在拓扑排序中，节点 u 必须排在节点 v 的前面。这个排序是图中所有节点的线性排列，并且保证了这种有向依赖关系。 2. 拓扑序列是什么？拓扑序列是拓扑排序的结果，即节点的一个线性排列，满足上述的依赖关系。对于给定的有向无环图，可能存在多个不同的拓扑序列，只要它们满足图中所有边的依赖关系。 3....
最小生成树:Prim 算法和Kruskal 算法
在 C++ 中，实现最小生成树（MST）的常用算法有两种：Prim 算法和Kruskal 算法。这两种算法适用于加权无向图，用于寻找包含所有顶点的边的集合，使得边的总权重最小，且没有环路。 1. Prim 算法Prim 算法通过贪心策略来构建 MST，从任意起始顶点开始，每次选择权重最小的边扩展 MST。 实现步骤 初始化一个集合 MST，包含图中的任意一个顶点。 找到从集合 MST 到剩余顶点中权重最小的边，并将该边加入 MST。 重复步骤 2，直到所有顶点都包含在 MST 中。 C++ 实现示例（使用优先队列）123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <iostream>#include <vector>#include <queue>#include...
邻接表，邻接矩阵和十字链表
1. 邻接表的实现邻接表使用一个数组或 vector 来存储每个顶点的边列表。每个顶点的边列表存储在一个链表或 vector 中。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <iostream>#include <vector>using namespace std;class Graph { int V; // 顶点数量 vector<vector<int>> adj; // 邻接表public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int u, int v) { adj[u].push_back(v); } void printGraph() { for...
DFS，BFS遍历非联通图
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <iostream>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;// 深度优先搜索函数 (DFS)// 从当前节点 `node` 开始访问，并递归访问其所有相邻的未访问节点void DFS(char node, unordered_map<char, vector<char>>& graph, unordered_set<char>& visited) { // 标记当前节点为已访问 visited.insert(node); // 输出当前节点（此处可以进行自定义的处理，像打印或其他操作） ...
赫夫曼树与赫夫曼编码
1. 哈夫曼树（Huffman Tree）：定义：哈夫曼树是一种带权路径长度最短的二叉树，通常用于数据压缩。 它的“最优”体现在权重大的节点离根节点更近，从而使加权路径长度最小。构造过程：哈夫曼树的构建基于贪心算法，步骤如下： 将给定的所有权值看作是森林中的单节点树。 每次选择两个权值最小的节点进行合并，构成一个新的父节点，其权值为两个子节点的权值之和。 重复上述过程，直到所有节点合并成一棵二叉树。 应用： 数据压缩：哈夫曼树用于哈夫曼编码，它通过为高频率字符分配较短的编码，低频率字符分配较长的编码，达到压缩数据的目的。 例子：假设我们有字符集和对应的权值（频率）如下： 字符 频率 A 5 B 9 C 12 D 13 E 16 F 45 构建哈夫曼树的过程如下： 选择频率最小的 A(5) 和 B(9)，合并为一个新节点，权值为 14。 再选择 C(12) 和 D(13) 合并，权值为 25。 合并 14 和 E(16)，权值为 30。 合并 25 和 F(45)，权值为 70。 最后合并 30 和...
树与二叉树
米娜桑好久不见，国庆期间没有更新博客，属实有点摆烂 今天我们的主题是树与二叉树的转换，以及树的储存方法，遍历方法与二叉树的区别等 首先，我们要明白的是，树可以有多个子节点，而二叉树最多只有两个，所以二叉树是特殊的树 一.树的存储与转换1.父亲表示法（双亲表示法） 使用一个数组来存储每个节点，其中每个节点只包含一个指针（或索引），指向其父节点。这种表示法的缺点是无法快速找到子节点，但优点是节省了存储空间。 1234struct TreeNode { int data; int parentIndex; // 指向父节点在数组中的索引}; 2.孩子链表表示法 使用一个数组来存储每个节点，每个节点包含一个链表，链表中的每个节点指向该节点的子节点。这样，查找子节点的时间较快，但会增加空间开销。 123456789101112// 孩子链表中的节点struct ChildNode { int childIndex; // 子节点的索引（或指针） ChildNode* next; //...
线索化二叉树及其遍历
线索化二叉树以下是实现该结构并进行中序遍历的代码：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#include <iostream>using namespace std;// 定义线索二叉树节点的结构struct ThreadedNode { int value; // 节点的值 ThreadedNode* left; // 指向左子节点 ThreadedNode* right; // 指向右子节点 bool lThread; ...
二叉树的遍历访问的实现
引入我们从小学二年级开始，就学过二叉树了（bushi） 那么，如何用编程实现二叉树的遍历呢？ （这里使用c艹） 1234567struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}}; 二叉树的每个结点都是如此定义的 遍历方法分为前序，中序，后序三种遍历方法。前序是从根结点开始，访问到最左侧第一个叶子结点后，访问右侧叶子，然后返回上一级（不访问），访问同级右侧结点，然后往下按照先左后右的顺序访问，等左子树访问完毕后，访问右子树。 中序是从左侧第一个叶子结点开始，返回上一级（访问），下一级右侧，返回上上级，右侧最下方左侧结点，然后返回上一级（访问），以此类推。 后序是按从左到右的顺序，左侧第一个叶子结点开始，访问完上一级结点左侧后，去右侧，然后返回上一级。 每种遍历方法又分为递归和非递归两种非递归方法1....