devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

树有好多知识点，详细归纳已整理_在一棵树中,每个节点代表一个家庭成员

作者：小小林熬夜学编程 | 2024-03-05 23:55:09

赞

踩

在一棵树中,每个节点代表一个家庭成员

树的定义与基本概念

节点、边、根、叶子等概念

假设我们有一家人，他们的谱系如下图所示：

          A
        /   \
       B     C
      / \   / \
     D   E F   G


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

  • 在这个谱系图中，每个人都代表着一个节点。节点是树的基本单位，它存储了一些数据，并且可能会连接到其他节点。在这里，每个节点代表一个家庭成员，而节点上存储的数据则包括姓名、出生日期等信息。

  • 这些节点之间的连接称为边。边表示一个节点与另一个节点之间的关系。在这个例子中，D和E两个节点是B节点的子节点，因此从B到D和E之间存在两条边。而A节点则连接着B和C两个节点，因此从A到B和C之间也存在两条边。

  • 树的最顶端的节点称为根。在这个例子中，A节点就是整棵树的根节点。根节点是树的起点，所有其他节点都可以通过它来访问。

  • 叶子节点是指没有子节点的节点。在这个例子中，D、E、F和G四个节点就是叶子节点。它们没有任何子节点，只有父节点和兄弟节点。叶子节点也被称为终端节点，因为它们不再连接其他节点。

  • 深度：每个节点都有一个深度值，它表示这个节点到根节点的距离。在这个例子中，A节点的深度为0，B和C节点的深度为1，D、E、F和G节点的深度为2。

  • 高度：树的高度是指从根节点到最远叶子节点的距离。在这个例子中，树的高度为2，因为最远的叶子节点与根节点的距离为2。

  • 子树：每个节点可以看作是一棵子树的根节点。子树包括该节点及其所有后代节点以及它们之间的边。例如，在上面的例子中，B节点的子树包括D和E两个节点以及它们之间的边。

  • 父节点和兄弟节点：每个节点都有一个父节点，除了根节点。在上面的例子中，B和C节点的父节点是A节点。同时，具有相同父节点的节点称为兄弟节点。例如，D和E节点是兄弟节点，它们都是B节点的子节点。

  • 祖先节点和后代节点：节点的祖先节点是指它的父节点、父节点的父节点、父节点的父节点的父节点，以此类推。例如，B节点的祖先节点包括A节点和A节点的父节点（如果有的话）。相反，后代节点是指一个节点的子节点、子节点的子节点、子节点的子节点的子节点，以此类推。例如，B节点的后代节点包括D和E节点。

树的性质和分类

树是一种非线性数据结构，由若干个节点（vertex）和连接它们的边（edge）组成。树具有以下几个性质：

  • 每个节点最多只有一个父节点，即每个节点只有一个入度。
  • 除了根节点，每个节点都有唯一的一个父节点。
  • 每个节点可以有任意多个子节点，但子节点之间不互相连接，即不存在环路。
  • 每个叶子节点都在同一层级上。

根据树的特征，我们可以将其分为以下几类：

  • 二叉树：每个节点最多有两个子节点的树结构，分为普通二叉树、满二叉树和完全二叉树等。
  • 多叉树：每个节点可以有任意个子节点的树结构，如四叉树、十字链表等。
  • 有序树：每个节点的子节点有顺序之分，如二叉搜索树、B树等。
  • 无序树：每个节点的子节点没有顺序之分，如哈希树、Trie树等。

树还可以按照其形状和性质进行更加具体的划分：

  • AVL树：一种自平衡二叉搜索树，保证左右子树的高度差不大于1。
  • 红黑树：一种自平衡二叉搜索树，保证最长路径不超过最短路径的两倍，插入、删除操作效率较高。
  • B树：多路平衡查找树，每个节点可以有多个子节点，支持快速查找、插入和删除等操作，常用于数据库索引。
  • 二叉堆：一种完全二叉树，满足最大堆或最小堆的性质，可用于实现堆排序、优先队列等算法。
  • Trie树：一种前缀树，用于字符串的匹配和检索，可以快速找到所有以某个字符串为前缀的字符串。
  • Huffman树：一种带权路径长度最短的树，通常用于数据压缩领域。

树的遍历算法

树的遍历算法分为三种：前序遍历、中序遍历和后序遍历。下面通过C语言来举例说明：
假设我们有如下一棵二叉树：

       1
     /   \
    2     3
   / \   / \
  4   5 6   7


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

1、前序遍历（Preorder Traversal）
前序遍历按照“根左右”的顺序访问节点，即先访问根节点，然后递归地访问其左子树，最后递归地访问其右子树。

C代码实现如下：

void preorderTraversal(TreeNode* root){
    if(root == NULL) return;
    printf("%d ", root->val); // 先访问根节点
    preorderTraversal(root->left); // 再递归遍历左子树
    preorderTraversal(root->right); // 最后递归遍历右子树
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

输出结果为：1 2 4 5 3 6 7

2、中序遍历（Inorder Traversal）
中序遍历按照“左根右”的顺序访问节点，即先递归地访问左子树，然后访问根节点，最后递归地访问右子树。

C代码实现如下：

void inorderTraversal(TreeNode* root){
    if(root == NULL) return;
    inorderTraversal(root->left); // 先递归遍历左子树
    printf("%d ", root->val); // 再访问根节点
    inorderTraversal(root->right); // 最后递归遍历右子树
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

输出结果为：4 2 5 1 6 3 7

3、后序遍历（Postorder Traversal）
后序遍历按照“左右根”的顺序访问节点，即先递归地访问左子树，然后递归地访问右子树，最后访问根节点。

C代码实现如下：

void postorderTraversal(TreeNode* root){
    if(root == NULL) return;
    postorderTraversal(root->left); // 先递归遍历左子树
    postorderTraversal(root->right); // 再递归遍历右子树
    printf("%d ", root->val); // 最后访问根节点
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

输出结果为：4 5 2 6 7 3 1

以上就是二叉树的三种遍历算法的C语言实现。需要注意的是，这里的TreeNode结构体表示树的一个节点，其中val表示节点的值，left和right分别表示节点的左子树和右子树。

二叉树及其遍历算法

二叉树的定义和性质

二叉树是一种特殊的树形数据结构，它由一组节点和一组有向边组成。每个节点包含一个值或数据元素，以及指向左子树和右子树的两个指针，这些指针可以为空。以下是二叉树的定义：

定义：一个二叉树是满足以下条件的树形结构：

  1. 每个节点最多有两个子节点。
  2. 左子树中的所有节点都比它们的父节点小（或按某种规定的优先级顺序），右子树中的所有节点都比它们的父节点大（或按某种规定的优先级顺序）。
  3. 在二叉树中，一个节点的左子树和右子树也是二叉树。如果一个节点的左子树不为空，则左子树上所有节点的值均小于该节点的值；如果一个节点的右子树不为空，则右子树上所有节点的值均大于该节点的值。

二叉树具有以下性质：

  1. 在二叉树的第i层上最多有2^(i-1)个节点。
  2. 高度为h的二叉树最多有2^h-1个节点。
  3. 对于任何一棵非空的二叉树，如果其叶节点数为n0，度为2的节点数为n2，则 n0=n2+1。
  4. 二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。其中，前序遍历顺序为 根节点-左子树-右子树；中序遍历顺序为左子树-根节点-右子树；后序遍历顺序为 左子树-右子树-根节点。
  5. 在二叉树的第i层上最多有2^(i-1）个节点，因此在高度为h的二叉树中最多有
    2^(h+1)-1个节点。
  6. 二叉树的深度为根节点到最远叶子节点的路径上的节点数，或者说是从根节点到达某一节点所经过的边的数量。根节点的深度为0。
  7. 如果一棵二叉树的所有叶子节点都在同一层上，则称之为完全二叉树。完全二叉树的特点是：除了最后一层外，其他层的节点数都是满的，最后一层的节点都靠左排列。
  8. 对于任意一棵二叉树，如果其叶子节点数为n0，度为2的节点数为n2，则 n0=n2+1。
  9. 二叉查找树（BST）是一种特殊的二叉树，它满足以下性质： a. 空树是一棵BST。 b.
    若一个节点的左子树不为空，则其左子树上所有节点的值均小于该节点的值。 c.
    若一个节点的右子树不为空，则其右子树上所有节点的值均大于该节点的值。 d. 一个节点的左右子树都是BST。

前序、中序、后序遍历算法

层次遍历算法

二叉树的层次遍历是按照从上到下、从左到右的顺序遍历二叉树中的所有节点。具体实现过程可以通过队列来完成，算法步骤如下：

  1. 首先将根节点入队列
  2. 从队列中取出队首元素，并访问该节点。
  3. 如果该节点有左孩子，则将左孩子入队列。
  4. 如果该节点有右孩子，则将右孩子入队列。
  5. 重复步骤2-4，直到队列为空。
    下面是一个用C语言实现二叉树层次遍历的示例代码：
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树的节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义队列结构体
typedef struct QueueNode {
    TreeNode *data;
    struct QueueNode *next;
} QueueNode;

typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = NULL;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == NULL;
}

// 入队列
void enqueue(Queue *q, TreeNode *data) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队列
TreeNode *dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return NULL;
    }
    TreeNode *data = q->front->data;
    QueueNode *temp = q->front;
    q->front = q->front->next;
    free(temp);
    return data;
}

// 创建二叉树
TreeNode *createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 层次遍历
void levelOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        TreeNode *node = dequeue(&q);
        printf("%d ", node->val);
        if (node->left != NULL) {
            enqueue(&q, node->left);
        }
        if (node->right != NULL) {
            enqueue(&q, node->right);
        }
    }
}

// 主函数
int main() {
    printf("请输入二叉树的节点，-1表示空节点：\n");
    TreeNode *root = createTree();
    printf("层次遍历结果为：\n");
    levelOrder(root);
    printf("\n");
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

平衡二叉树及其应用

平衡二叉树的定义和性质

平衡二叉树是一种特殊的二叉查找树，具有以下两个性质：

  1. 空树或者任意节点左右子树的高度差不超过 1。
  2. 左右子树都满足平衡二叉树的性质。
    其中，平衡二叉树的高度定义为从根节点到最深叶子节点的路径长度，空树的高度为 0。基于这两个性质，平衡二叉树可以保证插入、删除、查找等操作的时间复杂度都是 O(log n) 级别的。由于平衡二叉树的高度始终保持在较小的范围内，因此它的性能优于普通的二叉查找树。

平衡二叉树有多种实现方式，其中 AVL 树和红黑树是最常用的两种：

  1. AVL 树：任意节点的左右子树高度差不超过 1，需要进行旋转操作来维护平衡性。
  2. 红黑树：通过染色和旋转操作来维护平衡性，相对来说更加简单，被广泛使用于各种场景中。

平衡二叉树具有以下一些重要的性质：

  1. 在平衡二叉树上进行插入、删除和查找等操作的时间复杂度都是 O(log n)。
  2. 平衡二叉树的高度始终保持在较小的范围内，通常是log(n)级别的，因此可以高效地支持各种操作。
  3. 平衡二叉树是一种自平衡数据结构，能够自动维护结构的平衡性，减少了算法实现和调试的难度。
  4. 平衡二叉树被广泛应用于数据库索引、缓存淘汰算法、优先级队列等场景中，具有广泛的应用价值。

AVL树及其实现

AVL树是一种自平衡二叉搜索树，也被称为高度平衡树。它在每个节点中维护一个平衡因子（balance factor），该因子表示其左子树的高度和右子树的高度之差。AVL树的平衡因子必须为-1、0或1，否则就需要通过旋转来重新平衡。

以下是AVL树的基本实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
    int height;
} Node;

int height(Node* n) {
    if (n == NULL) {
        return 0;
    }
    return n->height;
}

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; //新节点高度设为1
    return node;
}

Node* rotate_right(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

Node* rotate_left(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

int getBalance(Node* n) {
    if (n == NULL) {
        return 0;
    }
    return height(n->left) - height(n->right);
}

Node* insert(Node* node, int data) {
    if (node == NULL) {
        return newNode(data);
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else {
        return node; //插入相同元素时，不做操作
    }

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && data < node->left->data) {
        return rotate_right(node);
    }

    if (balance < -1 && data > node->right->data) {
        return rotate_left(node);
    }

    if (balance > 1 && data > node->left->data) {
        node->left = rotate_left(node->left);
        return rotate_right(node);
    }

    if (balance < -1 && data < node->right->data) {
        node->right = rotate_right(node->right);
        return rotate_left(node);
    }

    return node;
}

void preorder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

int main() {
    Node* root = NULL;

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    printf("Preorder traversal of the constructed AVL tree is:\n");
    preorder(root);

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121

在这个例子中，小编使用C语言实现了AVL树的基本功能。使用AVL树的一个重要优点是它能够快速地进行查找、插入和删除操作，并且保证树的平衡性。

红黑树及其实现

红黑树是一种自平衡二叉查找树，它可以保证在最坏情况下基本动态集合操作的时间复杂度为O(log n)。红黑树采用颜色标记来维护平衡性，每个节点都被涂上红色或黑色，同时满足以下5个性质：

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色
  3. 每个叶子节点（NIL）都是黑色的
  4. 如果一个节点是红色的，则其两个子节点都是黑色的
  5. 对于任意节点而言，其到叶子节点的每条路径都包含相同数目的黑色节点

通过以上性质，我们可以保证红黑树的高度不会超过 2log(n+1)，从而保证了查找、插入和删除操作的时间复杂度都为O(log n)。

以下是C语言实现红黑树的结构体和函数：

#include <stdio.h>
#include <stdlib.h>

typedef struct RBNode{
    int data;
    int color;
    struct RBNode *left, *right, *parent;
}RBNode;

typedef struct RBTree{
    RBNode *root;
    RBNode *NIL;
}RBTree;

void initRBTree(RBTree *T){
    T->NIL = (RBNode*)malloc(sizeof(RBNode));
    T->NIL->color = 0;
    T->root = T->NIL;
}

void LeftRotate(RBTree *T, RBNode *x)
{
    RBNode *y = x->right;
    x->right = y->left;
    if(y->left != T->NIL)   y->left->parent = x;
    y->parent = x->parent;
    if(x->parent == T->NIL) T->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 *T, RBNode *y)
{
    RBNode *x = y->left;
    y->left = x->right;
    if(x->right != T->NIL)  x->right->parent = y;
    x->parent = y->parent;
    if(y->parent == T->NIL) T->root = x;
    else if(y == y->parent->left)    y->parent->left = x;
    else    y->parent->right = x;
    x->right = y;
    y->parent = x;
}

void RBInsert(RBTree *T, int data)
{
    RBNode *z = (RBNode*)malloc(sizeof(RBNode));
    z->data = data;
    z->left = T->NIL;
    z->right = T->NIL;
    z->color = 1;
    RBNode *y = T->NIL;
    RBNode *x = T->root;
    while(x != T->NIL){
        y = x;
        if(z->data < x->data)   x = x->left;
        else    x = x->right;
    }
    z->parent = y;
    if(y == T->NIL) T->root = z;
    else if(z->data < y->data)  y->left = z;
    else    y->right = z;
    while(z->parent->color == 1){
        if(z->parent == z->parent->parent->left){
            RBNode *y = z->parent->parent->right;
            if(y->color == 1){
                z->parent->color = 0;
                y->color = 0;
                z->parent->parent->color = 1;
                z = z->parent->parent;
            }else{
                if(z == z->parent->right){
                    z = z->parent;
                    LeftRotate(T, z);
                }
                z->parent->color = 0;
                z->parent->parent->color = 1;
                RightRotate(T, z->parent->parent);
            }
        }else{
            RBNode *y = z->parent->parent->left;
            if(y->color == 1){
                z->parent->color = 0;
                y->color = 0;
                z->parent->parent->color = 1;
                z = z->parent->parent;
            }else{
                if(z == z->parent->left){
                    z = z->parent;
                    RightRotate(T, z);
                }
                z->parent->color = 0;
                z->parent->parent->color = 1;
                LeftRotate(T, z->parent->parent);
            }
        }
    }
    T->root->color = 0;
}

RBNode* RBSearch(RBTree *T, int data)
{
    RBNode *x = T->root;
    while(x != T->NIL && x->data != data){
        if(data < x->data)  x = x->left;
        else    x = x->right;
    }
    if(x != T->NIL)    return x;
    else    return NULL;
}

void RBDelete(RBTree *T, int data)
{
    RBNode *z = RBSearch(T, data);
    if(z == NULL)   return;
    RBNode *y, *x;
    if(z->left == T->NIL || z->right == T->NIL)   y = z;
	else{
	y = z->right;
	while(y->left != T->NIL)    y = y->left;
	}
	if(y->left != T->NIL)   x = y->left;
	else    x = y->right;
	x->parent = y->parent;
	if(y->parent == T->NIL) T->root = x;
	else if(y == y->parent->left)   y->parent->left = x;
	else    y->parent->right = x;
	if(y != z)  z->data = y->data;
	if(y->color == 0){
	while(x != T->root && x->color == 0){
	if(x == x->parent->left){
	RBNode *w = x->parent->right;
	if(w->color == 1){
	w->color = 0;
	x->parent->color = 1;
	LeftRotate(T, x->parent);
	w = x->parent->right;
	}
	if(w->left->color == 0 && w->right->color == 0){
	w->color = 1;
	x = x->parent;
	}else{
	if(w->right->color == 0){
	w->left->color = 0;
	w->color = 1;
	RightRotate(T, w);
	w = x->parent->right;
	}
	w->color = x->parent->color;
	x->parent->color = 0;
	w->right->color = 0;
	LeftRotate(T, x->parent);
	x = T->root;
	}
	}else{
	RBNode *w = x->parent->left;
	if(w->color == 1){
	w->color = 0;
	x->parent->color = 1;
	RightRotate(T, x->parent);
	w = x->parent->left;
	}
	if(w->right->color == 0 && w->left->color == 0){
	w->color = 1;
	x = x->parent;
	}else{
	if(w->left->color == 0){
	w->right->color = 0;
	w->color = 1;
	LeftRotate(T, w);
	w = x->parent->left;
	}
	w->color = x->parent->color;
	x->parent->color = 0;
	w->left->color = 0;
	RightRotate(T, x->parent);
	x = T->root;
	}
	}
	}
	x->color = 0;
	}
	free(y);
	}
	
	void InOrder(RBNode *root)
	{
	if(root->left)  InOrder(root->left);
	printf("%d ", root->data);
	if(root->right) InOrder(root->right);
	}
	
	int main()
	{
	RBTree T;
	initRBTree(&T);
	int arr[] = {11,2,14,1,7,15,5,8,4};
	for(int i=0;i<9;i++){
	    RBInsert(&T, arr[i]);
	}
	
	printf("Inorder traversal of the constructed RB tree: ");
	InOrder(T.root);
	printf("\n");
	
	RBDelete(&T, 11);
	RBDelete(&T, 14);
	
	printf("Inorder traversal of the modified RB tree: ");
	InOrder(T.root);
	printf("\n");
	
	return 0;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216

这段代码实现了红黑树的插入、删除和查找操作，并提供了一个中序遍历函数InOrder用于打印树形结构。在主函数中，我们初始化了一个红黑树并插入了一些元素，然后删除了两个节点，并打印出修改后的树形结构。

B树及其变体

B树的定义和特点

B树是一种多路平衡查找树，它的定义和特点如下：

  1. 定义：B树是一棵根节点至少有两个子节点的树，每个节点可以存放多个关键字，并按照大小顺序从小到大排列，同时每个节点的子节点数目也与关键字数目相同或者比关键字数目多1。

  2. 特点：

  • B树的平衡性：B树通过自动调整来保持平衡状态，任何一个关键字到根的路径长度都不会超过树的高度。
  • B树的节点大小：B树中的每个节点可以存储多个关键字，因此在访问磁盘时，可以一次读取多个关键字，这样可以减少磁盘I/O操作，提高检索效率。
  • B树的查找效率：B树的查询效率比较稳定，最坏情况下的时间复杂度为O(log n)。由于B树的平衡性，每个节点的子树高度相等，所以查找时可以采用二分查找的思想，加速查找过程。
  • B树的插入和删除效率: B树支持快速的插入和删除操作，当插入或删除一个关键字时，只需要调整经过该节点的路径就可以了，不需要像平衡二叉树那样将整个树重新调整。
  • B树的应用范围：B树常用于文件系统、数据库等大量数据的存储和检索场景中，可以有效地减少磁盘I/O操作，提高数据查询效率。

B+树及其应用

B+树是B树的一种变体，它与B树的区别在于：① 所有数据都存储在叶子节点上；② 叶子节点之间采用指针相连接，形成一个有序链表，便于范围查询。

下面是一个简单的C语言实现B+树的例子：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node* next;
} Node;

typedef struct BPlusTree {
    int degree;
    Node* root;
} BPlusTree;

// 创建新节点
Node* createNode(int val) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// 向有序链表中插入元素
void insertToList(Node** list, int val) {
    Node* node = createNode(val);
    if (*list == NULL || val < (*list)->val) {
        node->next = *list;
        *list = node;
    } else {
        Node* cur = *list;
        while (cur->next != NULL && val >= cur->next->val) {
            cur = cur->next;
        }
        node->next = cur->next;
        cur->next = node;
    }
}

// 初始化B+树
BPlusTree* initBPlusTree(int degree) {
    BPlusTree* tree = (BPlusTree*) malloc(sizeof(BPlusTree));
    tree->degree = degree;
    tree->root = NULL;
    return tree;
}

// 插入元素
void insertBPlusTree(BPlusTree* tree, int val) {
    if (tree->root == NULL) {
        tree->root = createNode(val);
    } else {
        Node* cur = tree->root;
        Node* parent = NULL;
        while (cur != NULL && cur->val <= val) {
            parent = cur;
            cur = cur->next;
        }
        if (parent == NULL) {
            insertToList(&(tree->root), val);
        } else {
            insertToList(&(parent->next), val);
        }
    }
}

// 输出有序链表中的元素
void printList(Node* list) {
    while (list != NULL) {
        printf("%d ", list->val);
        list = list->next;
    }
}

// 遍历B+树
void traverseBPlusTree(BPlusTree* tree) {
    Node* cur = tree->root;
    while (cur != NULL) {
        printList(cur);
        cur = cur->next;
    }
}

int main() {
    BPlusTree* tree = initBPlusTree(3);
    insertBPlusTree(tree, 1);
    insertBPlusTree(tree, 5);
    insertBPlusTree(tree, 2);
    insertBPlusTree(tree, 7);
    insertBPlusTree(tree, 3);
    insertBPlusTree(tree, 4);
    insertBPlusTree(tree, 6);

    traverseBPlusTree(tree); // 输出 1 2 3 4 5 6 7

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96

上面的代码演示了如何用C语言实现一个简单的B+树，其中节点为链表，元素按从小到大的顺序排列。具体来说，主要实现了以下几个函数：

  • createNode()：创建新节点；
  • insertToList()：向有序链表中插入元素；
  • initBPlusTree()：初始化B+树；
  • insertBPlusTree()：插入元素到B+树中；
  • printList()：输出有序链表中的元素；
  • traverseBPlusTree()：遍历B+树，输出所有元素。
    B+树常用于数据库索引、文件系统等场景中，可以有效地提高数据的检索效率。由于其特点是所有数据都存储在叶子节点上，因此在范围查询时只需要扫描一次叶子节点即可，大大提高了查询效率。

B*树及其优化

B*树是B+树的一种优化，它与B+树的区别在于：① 在非叶子节点中存储更多的关键字，使得非叶子节点可以容纳更多的子节点；② 叶子节点和非叶子节点的大小差距更小。

下面是一个简单的C语言实现B*树的例子：

#include <stdio.h>
#include <stdlib.h>

#define DEGREE 3

typedef struct Node {
    int num; // 关键字数量
    int vals[2 * DEGREE + 1]; // 关键字数组
    struct Node* children[2 * DEGREE + 2]; // 子节点数组
} Node;

// 创建新节点
Node* createNode() {
    Node* node = (Node*) malloc(sizeof(Node));
    node->num = 0;
    for (int i = 0; i < 2 * DEGREE + 2; i++) {
        node->children[i] = NULL;
    }
    return node;
}

// 在节点中查找关键字位置
int findIndex(Node* node, int val) {
    int i = 0;
    while (i < node->num && node->vals[i] < val) {
        i++;
    }
    return i;
}

// 插入关键字到节点中
void insertIntoNode(Node* node, int val) {
    int i = node->num - 1;
    while (i >= 0 && node->vals[i] > val) {
        node->vals[i + 1] = node->vals[i];
        i--;
    }
    node->vals[i + 1] = val;
    node->num++;
}

// 分裂节点
void splitNode(Node* parent, int index) {
    Node* node = parent->children[index];
    Node* newNode = createNode();
    int mid = DEGREE;

    for (int i = mid + 1; i < 2 * DEGREE + 1; i++) {
        newNode->vals[i - mid - 1] = node->vals[i];
        newNode->children[i - mid - 1] = node->children[i];
        if (newNode->children[i - mid - 1] != NULL) {
            newNode->children[i - mid - 1]->parent = newNode;
        }
    }
    newNode->children[DEGREE] = node->children[2 * DEGREE + 1];
    if (newNode->children[DEGREE] != NULL) {
        newNode->children[DEGREE]->parent = newNode;
    }
    newNode->num = DEGREE;

    for (int i = mid; i < 2 * DEGREE; i++) {
        node->vals[i] = 0;
        node->children[i + 1] = NULL;
    }
    node->num = DEGREE;

    insertIntoNode(parent, node->vals[mid]);
    int j = parent->num - 1;
    while (j > index) {
        parent->children[j + 1] = parent->children[j];
        j--;
    }
    parent->children[index + 1] = newNode;
    newNode->parent = parent;
}

// 插入关键字到B*树中
void insertBStarTree(Node** root, Node* node, int val) {
    int index = findIndex(node, val);
    if (node->children[index] != NULL) {
        insertBStarTree(root, node->children[index], val);
        if (node->children[index]->num > 2 * DEGREE) {
            splitNode(node, index);
        }
    } else {
        insertIntoNode(node, val);
        if (node->num > 2 * DEGREE && node != *root) {
            Node* parent = node->parent;
            int childIndex = findIndex(parent, node->vals[DEGREE]);
            splitNode(parent, childIndex);
        }
    }
}

// 输出B*树中的关键字
void printBStarTree(Node* root) {
    if (root != NULL) {
        for (int i = 0; i < root->num; i++) {
            printf("%d ", root->vals[i]);
        }
        printf("\n");
        for (int i = 0; i <= root->num; i++) {
            printBStarTree(root->children[i]);
        }
    }
}

int main() {
    Node* root = createNode();
    insertBStarTree(&root, root, 1);
    insertBStarTree(&root, root, 5);
    insertBStarTree(&root, root, 2);
    insertBStarTree(&root, root, 7);
    insertBStarTree(&root, root, 3);
    insertBStarTree(&root, root, 4);
    insertBStarTree(&root, root, 6);

    printBStarTree(root); // 输出 1 2 3 4 5 6 7

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121

上面的代码演示了如何用C语言实现一个简单的B*树，其中节点中存储多个关键字，非叶子节点也可以容纳更多的子节点。具体来说，主要实现了以下几个函数：

  • createNode()：创建新节点；
  • findIndex()：在节点中查找关键字位置；
  • insertIntoNode()：将关键字插入到节点中；
  • splitNode()：分裂节点；
  • insertBStarTree()：向B*树中插入关键字；
  • printBStarTree()：输出B*树中的所有关键字。
    B树相比于B+树，可以进一步减少磁盘I/O操作，提高数据查询效率，特别是在大数据量、高并发的场景下表现更加优秀。因此，B树常常被应用于数据库索引、文件系统等领域。

树的应用实例

哈夫曼编码

哈夫曼编码是一种可变字长编码方式，可以将不同长度的字符编码成等长的比特串，并且保证解码时不会出现歧义。哈夫曼编码的核心思想是利用字符出现的频率来构造一棵小根堆（也称为哈夫曼树），并且将频率较低的字符放在叶子节点的左侧，频率较高的字符放在叶子节点的右侧，从而使得编码后的字符串具有最短的平均长度。

下面是一个简单的C语言实现哈夫曼编码的例子：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 512

// 哈夫曼树节点
typedef struct HuffmanNode {
    char ch;
    int freq;
    struct HuffmanNode* left;
    struct HuffmanNode* right;
} HuffmanNode;

// 小根堆节点
typedef struct MinHeapNode {
    HuffmanNode* node;
    struct MinHeapNode* next;
} MinHeapNode;

// 创建新的哈夫曼树节点
HuffmanNode* createHuffmanNode(char ch, int freq) {
    HuffmanNode* node = (HuffmanNode*) malloc(sizeof(HuffmanNode));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建新的小根堆节点
MinHeapNode* createMinHeapNode(HuffmanNode* node) {
    MinHeapNode* heapNode = (MinHeapNode*) malloc(sizeof(MinHeapNode));
    heapNode->node = node;
    heapNode->next = NULL;
    return heapNode;
}

// 插入小根堆节点
void insertMinHeapNode(MinHeapNode** head, HuffmanNode* node) {
    MinHeapNode* heapNode = createMinHeapNode(node);
    if (*head == NULL || (*head)->node->freq > node->freq) {
        heapNode->next = *head;
        *head = heapNode;
    } else {
        MinHeapNode* cur = *head;
        while (cur->next != NULL && cur->next->node->freq <= node->freq) {
            cur = cur->next;
        }
        heapNode->next = cur->next;
        cur->next = heapNode;
    }
}

// 删除小根堆头节点
HuffmanNode* removeMinHeapNode(MinHeapNode** head) {
    if (*head == NULL) {
        return NULL;
    } else {
        HuffmanNode* node = (*head)->node;
        MinHeapNode* tmp = *head;
        *head = (*head)->next;
        free(tmp);
        return node;
    }
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char* str, int* freqs) {
    MinHeapNode* heapHead = NULL;

    // 统计字符频率并插入小根堆
    for (int i = 0; i < strlen(str); i++) {
        char ch = str[i];
        HuffmanNode* node = createHuffmanNode(ch, freqs[ch]);
        insertMinHeapNode(&heapHead, node);
    }

    // 合并小根堆中的节点，构造哈夫曼树
    while (heapHead->next != NULL) {
        HuffmanNode* node1 = removeMinHeapNode(&heapHead);
        HuffmanNode* node2 = removeMinHeapNode(&heapHead);
        HuffmanNode* parent = createHuffmanNode('\0', node1->freq + node2->freq);
        parent->left = node1;
        parent->right = node2;
        insertMinHeapNode(&heapHead, parent);
    }

    return removeMinHeapNode(&heapHead);
}

// 生成哈夫曼编码表
void generateHuffmanTable(HuffmanNode* root, char** table, char* code) {
    if (root != NULL) {
        if (root->ch != '\0') {
            int index = (int) root->ch;
            table[index] = (char*) malloc(strlen(code) + 1);
            strcpy(table[index], code);
        }
        char leftCode[MAX_SIZE], rightCode[MAX_SIZE];
        strcpy(leftCode, code);
                strcat(leftCode, "0");
        strcat(rightCode, "1");
        generateHuffmanTable(root->left, table, leftCode);
        generateHuffmanTable(root->right, table, rightCode);
    }
}

// 使用哈夫曼编码表对字符串进行编码
char* encodeString(char* str, char** table) {
    int len = strlen(str);
    char* code = (char*) malloc(MAX_SIZE * len * sizeof(char));
    strcpy(code, "");

    for (int i = 0; i < len; i++) {
        int index = (int) str[i];
        strcat(code, table[index]);
    }

    return code;
}

// 使用哈夫曼编码表对比特串进行解码
char* decodeString(char* code, HuffmanNode* root) {
    int len = strlen(code);
    char* str = (char*) malloc(MAX_SIZE * len * sizeof(char));
    strcpy(str, "");

    HuffmanNode* cur = root;
    for (int i = 0; i < len; i++) {
        if (code[i] == '0') {
            cur = cur->left;
        } else if (code[i] == '1') {
            cur = cur->right;
        }
        if (cur->ch != '\0') {
            str[strlen(str)] = cur->ch;
            cur = root;
        }
    }

    return str;
}

int main() {
    char str[MAX_SIZE] = "hello world";
    int freqs[128] = {0};

    // 统计字符频率
    for (int i = 0; i < strlen(str); i++) {
        char ch = str[i];
        freqs[ch]++;
    }

    // 构建哈夫曼树并生成哈夫曼编码表
    HuffmanNode* root = buildHuffmanTree(str, freqs);
    char* table[128] = {0};
    generateHuffmanTable(root, table, "");

    // 打印哈夫曼编码表
    for (int i = 0; i < 128; i++) {
        if (table[i] != NULL) {
            printf("'%c': %s\n", (char) i, table[i]);
        }
    }

    // 对字符串进行编码和解码
    char* code = encodeString(str, table);
    printf("Encoded: %s\n", code);
    char* decodedStr = decodeString(code, root);
    printf("Decoded: %s\n", decodedStr);

    return 0;
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176

上面的代码演示了如何用C语言实现一个简单的哈夫曼编码器，其中主要实现了以下几个函数：

  • createHuffmanNode()：创建新的哈夫曼树节点；
  • createMinHeapNode()：创建新的小根堆节点；
  • insertMinHeapNode()：插入小根堆节点；
  • removeMinHeapNode()：删除小根堆头节点；
  • buildHuffmanTree()：构建哈夫曼树；
  • generateHuffmanTable()：生成哈夫曼编码表；
  • encodeString()：使用哈夫曼编码表对字符串进行编码；
  • decodeString()：使用哈夫曼编码表对比特串进行解码。
    在上述代码中，我们首先通过统计字符频率来构建哈夫曼树，并且生成了一个字符到哈夫曼编码的映射表。然后，我们将输入字符串按照这个映射表进行编码，并且进行解码以验证编码的正确性。

并查集

并查集是一种用于维护一些不相交集合的数据结构，支持合并（即将两个集合合并成一个）和查询（判断两个元素是否属于同一个集合）操作。在实际应用中，常常用并查集来处理连通性问题，比如判断一个图是否连通、最小生成树等。其中，每个元素被视为一个节点，并按照某种规则组织在一起形成一个森林，每个集合对应着一棵树。

下面是一个简单的C语言实现并查集的例子：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 并查集节点
typedef struct UnionFindNode {
    int parent;
    int rank;
} UnionFindNode;

// 初始化并查集
void initUnionFind(UnionFindNode sets[]) {
    for (int i = 0; i < MAX_SIZE; i++) {
        sets[i].parent = i;
        sets[i].rank = 0;
    }
}

// 查找节点所在的集合（使用路径压缩优化）
int findSet(UnionFindNode sets[], int x) {
    if (sets[x].parent != x) {
        sets[x].parent = findSet(sets, sets[x].parent);
    }
    return sets[x].parent;
}

// 合并两个集合（使用按秩合并优化）
void unionSets(UnionFindNode sets[], int x, int y) {
    int root1 = findSet(sets, x);
    int root2 = findSet(sets, y);
    if (root1 == root2) {
        return;
    }
    if (sets[root1].rank > sets[root2].rank) {
        sets[root2].parent = root1;
    } else if (sets[root1].rank < sets[root2].rank) {
        sets[root1].parent = root2;
    } else {
        sets[root2].parent = root1;
        sets[root1].rank++;
    }
}

int main() {
    UnionFindNode sets[MAX_SIZE];
    initUnionFind(sets);

    // 合并集合
    unionSets(sets, 0, 1);
    unionSets(sets, 1, 2);
    unionSets(sets, 3, 4);
    unionSets(sets, 5, 6);
    unionSets(sets, 6, 7);
    unionSets(sets, 7, 8);

    // 查询元素所在的集合
    int x = 1, y = 3;
    printf("%d and %d are%s in the same set.\n", x, y, findSet(sets, x) == findSet(sets, y) ? "" : " not");

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

上面的代码演示了如何用C语言实现一个简单的并查集，其中主要实现了以下几个函数：

  • initUnionFind()：初始化并查集；
  • findSet()：查找节点所在的集合（使用路径压缩优化）；
  • unionSets()：合并两个集合（使用按秩合并优化）。

在上述代码中，我们将每个元素视为一个节点，并按照编号的大小组织在一起形成一个森林。初始时每个节点都是自己的父节点，rank表示该集合所在的树的深度（即高度）。通过调用findSet()函数来查找某个节点所在的集合，并且在查找时使用路径压缩优化，可以使得查找的复杂度接近于常数级别。同时，在unionSets()函数中，我们使用按秩合并优化来避免出现不平衡的树，从而提高效率。

并查集常常被应用于图算法、计算机网络等领域，例如用于判断一个无向图是否连通、寻找最小生成树等。

最小生成树算法

最小生成树算法是指在一个加权连通图中找到一棵生成树，使得树的所有边的权值之和最小。其中，普遍采用的算法有Kruskal算法、Prim算法等。下面我们以Kruskal算法为例，介绍如何使用C语言实现最小生成树算法。

Kruskal算法的核心思想是将边按照权重从小到大排序，并逐个加入到生成树中。如果加入某条边后形成了环，则不加入该边，直到生成树包含了所有的节点。可以使用并查集来判断两个节点是否属于同一个集合（即是否已经连接）。以下是一个简单的C语言实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 边的结构体
typedef struct Edge {
    int u, v;   // 边的两个端点
    int weight; // 边的权重
} Edge;

// 并查集节点
typedef struct UnionFindNode {
    int parent;
    int rank;
} UnionFindNode;

// 初始化并查集
void initUnionFind(UnionFindNode sets[]) {
    for (int i = 0; i < MAX_SIZE; i++) {
        sets[i].parent = i;
        sets[i].rank = 0;
    }
}

// 查找节点所在的集合（使用路径压缩优化）
int findSet(UnionFindNode sets[], int x) {
    if (sets[x].parent != x) {
        sets[x].parent = findSet(sets, sets[x].parent);
    }
    return sets[x].parent;
}

// 合并两个集合（使用按秩合并优化）
void unionSets(UnionFindNode sets[], int x, int y) {
    int root1 = findSet(sets, x);
    int root2 = findSet(sets, y);
    if (root1 == root2) {
        return;
    }
    if (sets[root1].rank > sets[root2].rank) {
        sets[root2].parent = root1;
    } else if (sets[root1].rank < sets[root2].rank) {
        sets[root1].parent = root2;
    } else {
        sets[root2].parent = root1;
        sets[root1].rank++;
    }
}

// 按边权重从小到大排序
int cmp(const void* a, const void* b) {
    Edge* edgeA = (Edge*) a;
    Edge* edgeB = (Edge*) b;
    return edgeA->weight - edgeB->weight;
}

// 输出最小生成树的边
void printMST(Edge mst[], int n) {
    printf("Minimum Spanning Tree:\n");
    for (int i = 0; i < n - 1; i++) {
        printf("%d -- %d\tweight: %d\n", mst[i].u, mst[i].v, mst[i].weight);
    }
}

// 计算最小生成树
void kruskalMST(Edge edges[], int n, int m) {
    qsort(edges, m, sizeof(Edge), cmp); // 按边权重从小到大排序
    UnionFindNode sets[MAX_SIZE];
    initUnionFind(sets); // 初始化并查集

    Edge mst[MAX_SIZE] = {0}; // 存储最小生成树的边
    int count = 0; // 记录加入的边数
    for (int i = 0; i < m && count < n - 1; i++) {
        int u = edges[i].u, v = edges[i].v;
        if (findSet(sets, u) != findSet(sets, v)) { // 判断是否形成环
            mst[count++] = edges[i]; // 加入到最小生成树中
            unionSets(sets, u, v); // 合并两个集合
        }
    }

    printMST(mst, n);
}

int main() {
    int n = 6, m = 9;
    Edge edges[] = {{0, 1, 6}, {0, 3, 4}, {0, 2, 1}, {1, 2, 5}, {1, 4, 3}, {1, 5, 7}, {2, 4, 8}, {3, 4, 9}, {4, 5, 2}};
    kruskalMST(edges, n, m);

return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

在上述代码中，我们首先定义了一个Edge结构体，用于表示边的信息。然后，通过使用并查集来判断两个节点是否属于同一个集合，并按照边权重从小到大排序，依次将边加入最小生成树中，如果形成环则不加入，并记录加入的边数。最后，输出最小生成树的所有边。

这里我们使用了并查集来帮助维护连通性信息，同时使用快速排序算法对所有边进行排序，以便能够高效地加入边并避免形成环。如果边的数量比较大，那么可以考虑使用更加高效的排序算法来排序。

最小生成树算法常见于网络设计、城市道路建设等领域，例如为一张电信网络设计出一个连接所有城市的最小成本方案。

关于树的相关知识，先写到这，进阶的知识点，小编后期会持续更新，希望各位大佬能够点赞支持。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/194703
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号