二叉树的先序,中序,后序遍历

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
#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 先序遍历
void preOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data); // 访问根节点
        preOrderTraversal(root->left); // 先序遍历左子树
        preOrderTraversal(root->right); // 先序遍历右子树
    }
}

// 中序遍历
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left); // 中序遍历左子树
        printf("%d ", root->data); // 访问根节点
        inOrderTraversal(root->right); // 中序遍历右子树
    }
}

// 后序遍历
void postOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        postOrderTraversal(root->left); // 后序遍历左子树
        postOrderTraversal(root->right); // 后序遍历右子树
        printf("%d ", root->data); // 访问根节点
    }
}

// 创建新的二叉树节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // 构建一个二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 先序遍历
    printf("Preorder traversal: ");
    preOrderTraversal(root);
    printf("\n");

    // 中序遍历
    printf("Inorder traversal: ");
    inOrderTraversal(root);
    printf("\n");

    // 后序遍历
    printf("Postorder traversal: ");
    postOrderTraversal(root);
    printf("\n");

    // 释放内存
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right);
    free(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
#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 队列结构
struct QueueNode {
    struct TreeNode* node;
    struct QueueNode* next;
};

// 入队操作
void enqueue(struct QueueNode** front, struct QueueNode** rear, struct TreeNode* node) {
    struct QueueNode* newQueueNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newQueueNode->node = node;
    newQueueNode->next = NULL;

    if (*rear == NULL) {
        *front = newQueueNode;
        *rear = newQueueNode;
    } else {
        (*rear)->next = newQueueNode;
        *rear = newQueueNode;
    }
}

// 出队操作
struct TreeNode* dequeue(struct QueueNode** front, struct QueueNode** rear) {
    if (*front == NULL) {
        return NULL;
    }

    struct TreeNode* dequeuedNode = (*front)->node;
    struct QueueNode* temp = *front;

    *front = (*front)->next;
    free(temp);

    if (*front == NULL) {
        *rear = NULL;
    }

    return dequeuedNode;
}

// 层序遍历
void levelOrder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct QueueNode* front = NULL;
    struct QueueNode* rear = NULL;

    enqueue(&front, &rear, root);

    while (front != NULL) {
        struct TreeNode* current = dequeue(&front, &rear);
        printf("%d ", current->data);

        if (current->left != NULL) {
            enqueue(&front, &rear, current->left);
        }

        if (current->right != NULL) {
            enqueue(&front, &rear, current->right);
        }
    }
}

// 创建新的二叉树节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // 构建一个二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);

    // 层序遍历
    printf("Level Order Traversal: ");
    levelOrder(root);
    printf("\n");

    // 释放内存
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

image-20231217135500934

java代码:

image-20231217135835227

二叉树的序列化与反序列化(先序遍历)

序列化:

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 先序序列化
void serialize(struct TreeNode* root, char* result) {
    if (root == NULL) {
        strcat(result, "null "); // 使用特殊标记表示空节点
        return;
    }

    char buffer[20]; // 假设值的范围在 int 的表示范围内
    sprintf(buffer, "%d ", root->val);
    strcat(result, buffer); // 将当前节点的值追加到结果中

    serialize(root->left, result);  // 递归序列化左子树
    serialize(root->right, result); // 递归序列化右子树
}

int main() {
    // 构建一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // 先序序列化
    char result[100]; // 假设序列化结果不超过 100 个字符
    result[0] = '\0'; // 初始化为空字符串
    serialize(root, result);
    
    // 输出序列化结果
    printf("Serialized: %s\n", result);

    // 释放内存
    // ...（释放二叉树的节点，这里省略）

    return 0;
}

反序列化:

java代码:

image-20231217152610867