C--树的常见案例
二叉树
二叉树（Binary Tree）是树形结构的一个重要类型。它的特点是每个节点最多有两个子节点，通常被称为左子节点和右子节点。这种结构在计算机科学中非常常见，被广泛应用于各种算法和数据结构中。
二叉树的基本性质
- 非空二叉树只有一个根节点。
- 每个节点最多有两个子节点，通常称为左子节点和右子节点。
- 节点的子树分左右，左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于或等于它的根节点的值。
- 二叉树的第i层上的节点数目最多为 2^(i-1) 个(i>=1)。
- 深度为k的二叉树最多有 2^k - 1 个节点(k>=1)。
二叉树的类型
- 满二叉树：每一层的节点数都达到最大值。也就是说，如果一个二叉树的层数为K，且节点总数是(2^k) -1 ，则它就是满二叉树。
- 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有节点，并且所有节点从左向右连续紧密排列，这样的二叉树被称为完全二叉树。
二叉树的遍历
遍历二叉树是指按照某种规则访问二叉树的每个节点，使得每个节点被访问且仅被访问一次。常见的遍历方式有四种：前序遍历、中序遍历、后序遍历和层次遍历。
- 前序遍历：根节点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 根节点 -> 右子树
- 后序遍历：左子树 -> 右子树 -> 根节点
- 层次遍历：按照树的层次，从上到下、从左到右遍历节点。
二叉树的应用
二叉树在许多领域都有广泛的应用，例如：
- 搜索：二叉搜索树是一种特殊的二叉树，它允许我们以对数时间复杂度进行搜索、插入和删除操作。
- 表达式树：在编译器设计中，表达式通常以二叉树的形式表示，其中叶子节点是操作数，非叶子节点是操作符。
- 优先队列：堆（一种特殊的完全二叉树）是实现优先队列的有效数据结构。
- 数据压缩：霍夫曼编码等压缩算法使用二叉树来存储编码信息。
二叉树不仅是数据结构课程中的重要内容，也是解决实际问题时常用的工具。通过学习和掌握二叉树，你可以更好地理解树形结构的概念，并将其应用于实际编程中。
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int value; // 节点的值
struct TreeNode* left; // 指向左子节点的指针
struct TreeNode* right; // 指向右子节点的指针
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!newNode) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 插入节点（这里仅作简单示例，插入逻辑需要进一步完善）
void insertNode(TreeNode** root, int value) {
if (*root == NULL) {
*root = createNode(value);
} else {
// 示例中不实现具体的插入逻辑，因为这会依赖于特定的二叉树类型（如二叉搜索树）
// 实际使用时需要根据树的类型来确定插入位置
}
}
// 前序遍历
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->value); // 访问根节点
preOrderTraversal(root->left); // 遍历左子树
preOrderTraversal(root->right); // 遍历右子树
}
// 中序遍历
void inOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left); // 遍历左子树
printf("%d ", root->value); // 访问根节点
inOrderTraversal(root->right); // 遍历右子树
}
// 后序遍历
void postOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left); // 遍历左子树
postOrderTraversal(root->right); // 遍历右子树
printf("%d ", root->value); // 访问根节点
}
// 释放二叉树
void freeTree(TreeNode* root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
// 主函数，测试二叉树操作
int main() {
TreeNode* root = NULL;
// 插入节点（这里的插入逻辑并不完整，只是示例）
insertNode(&root, 1);
insertNode(&root, 2); // 注意：这样插入并不会创建出正确的二叉树结构，因为没有考虑树的特性
insertNode(&root, 3);
// 前序遍历
printf("Pre-order traversal: ");
preOrderTraversal(root);
printf("\n");
// 中序遍历
printf("In-order traversal: ");
inOrderTraversal(root);
printf("\n");
// 后序遍历
printf("Post-order traversal: ");
postOrderTraversal(root);
printf("\n");
// 释放二叉树内存
freeTree(root);
return 0;
}注意：上面的代码只是一个非常简单的二叉树结构和遍历操作的示例。它没有实现一个具体的二叉树类型（如二叉搜索树），并且插入操作也没有真正的逻辑。在实际应用中，你需要根据树的类型来实现插入、删除和搜索等操作。
例如，在二叉搜索树（BST）中，插入一个新节点需要遵循以下规则：
- 如果树为空，新节点成为根节点。
- 如果新节点的值小于当前节点的值，将其插入到当前节点的左子树中。
- 如果新节点的值大于当前节点的值，将其插入到当前节点的右子树中。
- 如果新节点的值等于当前节点的值，则根据具体情况处理（可能不允许重复值，或者可以将新节点作为当前节点的副本插入）。
对于二叉搜索树，插入操作需要递归地向下搜索合适的插入位置。上面的insertNode函数需要修改以支持这种递归插入。
红黑树（Red Black Tree）是一种自平衡的二叉查找树，它在计算机科学中广泛应用，主要用于实现关联数组。红黑树通过颜色的约束和特定的调整操作来保持树的平衡，从而在动态数据环境下提供高效的查找、插入和删除操作。
红黑树
红黑树具有以下几个关键特性：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL或空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些特性确保了红黑树在插入或删除节点后能够自动调整以保持平衡。这种平衡性保证了红黑树在最坏情况下的查找、插入和删除操作的时间复杂度都是O(log n)，其中n是树中元素的数目。
红黑树的自平衡特性是通过在插入或删除节点时进行特定的旋转和颜色调整来实现的。这些操作包括左旋、右旋、改变节点颜色等，它们旨在重新平衡树的结构，同时保持红黑树的特性。
红黑树的应用非常广泛，特别是在需要高效查找、插入和删除操作的场景中。例如，在数据库索引、文件系统和内存管理等领域，红黑树都发挥着重要的作用。由于其出色的性能表现，红黑树也成为了许多编程语言标准库中的一部分，用于实现诸如集合、映射等数据结构。
总之，红黑树是一种强大而高效的数据结构，它通过颜色约束和自平衡特性提供了优秀的查找、插入和删除性能。这使得红黑树在各种应用场景中都能发挥出色的作用。
#include <stdio.h>
#include <stdlib.h>
// 定义红黑树节点的颜色
typedef enum { RED, BLACK } Color;
// 定义红黑树节点
typedef struct RBNode {
int value;
Color color;
struct RBNode *left;
struct RBNode *right;
struct RBNode *parent;
} RBNode, *RBTree;
// 创建新节点
RBNode* createNode(int value, Color color, RBNode* parent) {
RBNode* newNode = (RBNode*)malloc(sizeof(RBNode));
if (!newNode) {
exit(1);
}
newNode->value = value;
newNode->color = color;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = parent;
return newNode;
}
// 左旋操作
void leftRotate(RBTree *root, RBNode *x) {
RBNode *y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
*root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
// 右旋操作
void rightRotate(RBTree *root, RBNode *y) {
RBNode *x = y->left;
y->left = x->right;
if (x->right != NULL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
*root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
x->right = y;
y->parent = x;
}
// 插入节点并调整红黑树
void insertFixUp(RBTree *root, RBNode *z) {
while (z != *root && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
RBNode *y = z->parent->parent->right;
if (y != NULL && y->color == RED) {
// 叔叔节点是红色，叔叔和父节点变色，祖父节点变红
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
// z是右孩子，左旋
z = z->parent;
leftRotate(root, z);
}
// z是左孩子，父节点变色并右旋
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(root, z->parent->parent);
}
} else {
// 情况和上面类似，只是方向相反
RBNode *y = z->parent->parent->left;
if (y != NULL && y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(root, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(root, z->parent->parent);
}
}
}
(*root)->color = BLACK;
}
// 插入节点
void insert(RBTree *root,van Emde Boas树
van Emde Boas树是一种特殊的数据结构，支持优先队列操作以及一些其他操作，如查找最大值、后继元素等。其关键特性在于，每个操作的最坏运行时间为O(lg lgn)，这在处理大规模数据时具有显著优势。
van Emde Boas树的基本方法是通过使用一个u位的数组A[0..u-1]来存储一个值来自全域{0,1,2,…,u-1}的动态集合。若值x属于动态集合，则元素A[x]为1；否则，A[x]为0。这使得查找、插入、删除等操作的时间复杂度达到O(1)。然而，对于查找最大值、后继元素等操作，其最坏情况时间复杂度为θ(u)。
为了优化这些操作，van Emde Boas树引入了叠加的二叉树结构。这个结构使用位向量上方叠加的一棵位二叉树，通过缩短对位向量的长扫描来改进性能。位向量的全部元素组成了二叉树的叶子，并且每个内部结点存储的是其两个孩子的逻辑或。这种结构使得查找最大值和后继元素等操作更为高效。
值得注意的是，van Emde Boas树对关键字有严格的限制，即它们必须是0到n-1的整数且无重复。这使得它在某些特定应用场景中非常有用，但也可能限制了其通用性。
总的来说，van Emde Boas树是一种高效的数据结构，特别适用于需要快速处理大量数据且关键字范围有限的情况。然而，由于其特殊性和复杂性，它并不总是最佳选择，需要根据具体应用场景进行权衡。
实现一个完整的 van Emde Boas 树在 C 语言中是一个相对复杂的任务，因为它涉及到递归结构以及多个层级的数组。以下是一个简化的 van Emde Boas 树示例，只包含插入和查找操作，并不包括所有高级功能。请注意，这个示例并没有实现完整的 van Emde Boas 树结构，而是为了展示其基本概念。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 64
typedef struct VanEmdeBoasNode {
bool value; // 对应位是否设置
struct VanEmdeBoasNode *high; // 高位节点
struct VanEmdeBoasNode *low; // 低位节点
} VanEmdeBoasNode;
VanEmdeBoasNode* createNode() {
VanEmdeBoasNode *node = (VanEmdeBoasNode*)malloc(sizeof(VanEmdeBoasNode));
node->value = false;
node->high = NULL;
node->low = NULL;
return node;
}
void insert(VanEmdeBoasNode **root, int value) {
if (*root == NULL) {
*root = createNode();
}
if (value < MAX_SIZE / 2) {
if ((*root)->low == NULL) {
(*root)->low = createNode();
}
insert(&((*root)->low), value);
} else {
if ((*root)->high == NULL) {
(*root)->high = createNode();
}
insert(&((*root)->high), value - MAX_SIZE / 2);
}
(*root)->value = ((*root)->low != NULL || (*root)->high != NULL);
}
bool contains(VanEmdeBoasNode *root, int value) {
if (root == NULL) {
return false;
}
if (value < MAX_SIZE / 2) {
return contains(root->low, value);
} else {
return contains(root->high, value - MAX_SIZE / 2);
}
}
void freeTree(VanEmdeBoasNode *root) {
if (root == NULL) {
return;
}
freeTree(root->low);
freeTree(root->high);
free(root);
}
int main() {
VanEmdeBoasNode *tree = NULL;
// 插入一些值
insert(&tree, 3);
insert(&tree, 7);
insert(&tree, 1);
insert(&tree, 6);
// 查找值
printf("Contains 3? %s\n", contains(tree, 3) ? "Yes" : "No");
printf("Contains 5? %s\n", contains(tree, 5) ? "Yes" : "No");
// 释放树
freeTree(tree);
return 0;
}这个示例实现了一个简单的 van Emde Boas 树，它只能处理从 0 到 MAX_SIZE - 1 的整数，其中 MAX_SIZE 是树的容量。在这个例子中，MAX_SIZE 被设置为 64，这意味着树可以存储从 0 到 63 的整数。
请注意，这个实现并没有充分利用 van Emde Boas 树的所有优点，特别是它缺少了一些高级操作，如查找最大值、后继元素等。此外，这个例子也没有实现树的部分更新和合并操作，这些操作是 van Emde Boas 树在更高级应用中非常重要的部分。
为了完整实现 van Emde Boas 树，你需要添加更多的功能，包括处理合并操作、支持更复杂的查询以及处理边界情况。这样的实现将更为复杂，并且超出了这个简单示例的范围。在实际应用中，你可能还需要考虑内存管理和性能优化等问题。
最小生成树
最小生成树是图论中的一个重要概念，主要用于解决在给定带权连通图中找到一棵边权值和最小的生成树的问题。这里的生成树指的是一个连通无向图的子图，它包含了原图的所有顶点，并且是一个树形结构（即任意两个顶点之间有且仅有一条简单路径）。最小生成树则是所有生成树中边的权值之和最小的那一棵。
最小生成树具有一些重要的性质。首先，最小生成树不是唯一的，即对于一个给定的连通带权图，可能存在多棵不同的最小生成树。然而，尽管最小生成树的形态可能不同，但它们对应的边的权值之和总是唯一的，并且是最小的。其次，最小生成树的边数总是等于顶点数减一，这是因为生成树是一个连通无环的图，所以边数必然等于顶点数减一。
构建最小生成树的经典算法主要有两种：Kruskal算法和Prim算法。这两种算法的基本思想都是逐步构建最小生成树，通过选择权值最小的边来连接顶点，同时避免形成环路。Kruskal算法从权值最小的边开始，依次选择边并加入最小生成树，如果加入某条边后会形成环路，则舍弃该边并选择下一条边。而Prim算法则从任意一个顶点开始，逐步添加与当前生成树距离最近的顶点及其相关的边，直到所有顶点都被包含在内。
最小生成树在实际应用中有着广泛的应用。例如，在计算机网络中，最小生成树可以用于构建通信网络的拓扑结构，以最小化通信成本；在电力系统规划中，最小生成树可以帮助确定最佳的输电线路布局，以降低成本并提高效率。此外，在生物学、物流优化等领域，最小生成树也发挥着重要的作用。
总的来说，最小生成树是图论中的一个重要概念，它提供了一种在带权连通图中找到边权值和最小的生成树的方法。通过应用最小生成树算法，我们可以解决许多实际问题，如网络设计、电力系统规划等。
下面是一个使用Kruskal算法实现最小生成树的C语言案例。Kruskal算法的基本思想是按照边的权值从小到大排序，然后从最小的边开始，依次判断每条边是否会与已选择的边构成环，如果不构成环，则将其加入到最小生成树中。
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
#define INFINITY 99999
typedef struct Edge {
int src, dest, weight;
} Edge;
int find(int parent[], int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
int unionSets(int parent[], int rank[], int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
return 0;
}
int compare(const void *a, const void *b) {
return ((Edge *)a)->weight - ((Edge *)b)->weight;
}
int kruskalMST(int graph[MAX_VERTICES][MAX_VERTICES], int V) {
Edge result[V];
int e = 0;
int i, x, y;
for (i = 0; i < V; i++)
for (int j = 0; j < V; j++) {
result[e].src = i;
result[e].dest = j;
result[e].weight = graph[i][j];
e++;
}
qsort(result, e, sizeof(Edge), compare);
int parent[V];
int rank[V];
for (i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
int num_edges = 0;
for (i = 0; i < e && num_edges < V - 1; i++) {
x = find(parent, result[i].src);
y = find(parent, result[i].dest);
if (x != y) {
unionSets(parent, rank, x, y);
num_edges++;
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}
}
return 0;
}
int main() {
int V = 4;
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 10, INFINITY, INFINITY},
{10, 0, 3, INFINITY},
{INFINITY, 3, 0, 1},
{INFINITY, INFINITY, 1, 0}
};
kruskalMST(graph, V);
return 0;
}请注意，这个代码示例中的图是通过邻接矩阵表示的，其中graph[i][j]表示从顶点i到顶点j的边的权值。如果两个顶点之间没有边，则权值被设置为INFINITY。
这个代码示例中，kruskalMST函数首先创建一个包含图中所有边的Edge结构体数组，并按照边的权值对它们进行排序。然后，它使用并查集数据结构（通过parent和rank数组实现）来跟踪已经加入最小生成树的顶点集合，并逐步添加不会形成环的边到最小生成树中。
运行这个程序将输出最小生成树的边和它们的权值。在这个例子中，输出将是：
0 -- 1 == 10
2 -- 3 == 1
1 -- 2 == 3这表示最小生成树包含边0-1（权值10）、边2-3（权值1）和边1-2（权值3）。注意，边的表示方式可能因实际图的表示和顶点的编号而有所不同。