【408考点之数据结构】树与二叉树的应用

树与二叉树的应用

一、树与二叉树的基本应用

树和二叉树是数据结构中的重要组成部分，具有广泛的应用。以下是树和二叉树的一些基本应用：

1. 表达式树：用于表示算术表达式，其中叶节点是操作数，内部节点是运算符。
2. 霍夫曼编码树：用于数据压缩，特别是文件压缩。
3. 文件系统：操作系统中的文件目录结构通常使用树形结构。
4. 数据库索引：B树和B+树被广泛应用于数据库索引，以加快数据检索速度。

二、表达式树

表达式树是一种用于表示算术表达式的二叉树，叶节点代表操作数，非叶节点代表操作符。通过遍历表达式树，可以对表达式进行计算。

代码实现：

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

// 定义树节点结构
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(char data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 构建表达式树
TreeNode* buildExpressionTree(char postfix[]) {
    TreeNode *stack[100];
    int top = -1;
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            stack[++top] = createNode(postfix[i]);
        } else {
            TreeNode *node = createNode(postfix[i]);
            node->right = stack[top--];
            node->left = stack[top--];
            stack[++top] = node;
        }
    }
    return stack[top];
}

// 前序遍历
void preorder(TreeNode *root) {
    if (root) {
        printf("%c ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序遍历
void inorder(TreeNode *root) {
    if (root) {
        inorder(root->left);
        printf("%c ", root->data);
        inorder(root->right);
    }
}

// 后序遍历
void postorder(TreeNode *root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%c ", root->data);
    }
}

// 计算表达式树的值
int evaluateExpressionTree(TreeNode *root) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->data - '0';
    int leftValue = evaluateExpressionTree(root->left);
    int rightValue = evaluateExpressionTree(root->right);
    if (root->data == '+') return leftValue + rightValue;
    if (root->data == '-') return leftValue - rightValue;
    if (root->data == '*') return leftValue * rightValue;
    if (root->data == '/') return leftValue / rightValue;
    return 0;
}

int main() {
    char postfix[] = "23*54*+";
    TreeNode *root = buildExpressionTree(postfix);
    printf("Preorder: ");
    preorder(root);
    printf("\nInorder: ");
    inorder(root);
    printf("\nPostorder: ");
    postorder(root);
    printf("\nResult: %d\n", evaluateExpressionTree(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

三、霍夫曼编码树

霍夫曼编码是一种用于数据压缩的算法，通过使用变长编码表对数据进行编码。霍夫曼编码树是生成霍夫曼编码的关键。

代码实现：

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

// 定义霍夫曼树节点结构
typedef struct HuffmanTreeNode {
    char data;
    unsigned freq;
    struct HuffmanTreeNode *left;
    struct HuffmanTreeNode *right;
} HuffmanTreeNode;

// 创建新节点
HuffmanTreeNode* createNode(char data, unsigned freq) {
    HuffmanTreeNode *newNode = (HuffmanTreeNode *)malloc(sizeof(HuffmanTreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->freq = freq;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 霍夫曼编码树的构建和编码生成
// （由于篇幅限制，此处省略具体实现细节）

int main() {
    // 假设输入的字符及其频率如下
    char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    unsigned freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(data) / sizeof(data[0]);

    // 构建霍夫曼编码树
    // HuffmanTreeNode *root = buildHuffmanTree(data, freq, size);

    // 生成并打印霍夫曼编码
    // printHuffmanCodes(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

四、文件系统

文件系统的目录结构通常用树形结构表示，每个目录和文件都是树中的一个节点，目录之间的层次关系通过树的层次关系体现。

代码实现：

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

// 定义文件系统树节点结构
typedef struct FileSystemNode {
    char name[100];
    struct FileSystemNode *firstChild;
    struct FileSystemNode *nextSibling;
} FileSystemNode;

// 创建新节点
FileSystemNode* createNode(char *name) {
    FileSystemNode *newNode = (FileSystemNode *)malloc(sizeof(FileSystemNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    strcpy(newNode->name, name);
    newNode->firstChild = newNode->nextSibling = NULL;
    return newNode;
}

// 插入子节点
void insertChild(FileSystemNode *parent, char *childName) {
    FileSystemNode *child = createNode(childName);
    if (!parent->firstChild) {
        parent->firstChild = child;
    } else {
        FileSystemNode *sibling = parent->firstChild;
        while (sibling->nextSibling) {
            sibling = sibling->nextSibling;
        }
        sibling->nextSibling = child;
    }
}

// 遍历文件系统
void traverseFileSystem(FileSystemNode *root, int level) {
    if (root) {
        for (int i = 0; i < level; i++) printf("  ");
        printf("%s\n", root->name);
        traverseFileSystem(root->firstChild, level + 1);
        traverseFileSystem(root->nextSibling, level);
    }
}

int main() {
    FileSystemNode *root = createNode("root");
    insertChild(root, "bin");
    insertChild(root, "etc");
    insertChild(root, "home");
    insertChild(root->firstChild, "bash");
    insertChild(root->firstChild->nextSibling, "config");

    printf("File System Structure:\n");
    traverseFileSystem(root, 0);

    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

五、数据库索引

在数据库中，索引用于加速数据的检索，B树和B+树是常见的索引结构。

代码实现：

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

// 定义B树节点结构
typedef struct BTreeNode {
    int *keys;
    int t; // 最小度数
    struct BTreeNode **C; // 子节点指针
    int n; // 当前键值数量
    int leaf; // 是否为叶节点
} BTreeNode;

// 创建新节点
BTreeNode* createNode(int t, int leaf) {
    BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->t = t;
    newNode->leaf = leaf;
    newNode->keys = (int *)malloc((2*t-1) * sizeof(int));
    newNode->C = (BTreeNode **)malloc(2*t * sizeof(BTreeNode *));
    newNode->n = 0;
    return newNode;
}

// B树的插入操作
// （由于篇幅限制，此处省略具体实现细节）

int main() {
    int t = 3; // B树的最小度数
    BTreeNode *root = createNode(t, 1);

    // 插入键值
    // insert(root, 10);
    // insert(root, 20);
    // insert(root, 5);
    // insert(root, 6);
    // insert(root, 12);
    // insert(root, 30);
    // insert(root, 7);
    // insert(root, 17);

    // 遍历B树
    // traverse(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