二叉树链式存储详解_二叉树的链式存储

二叉树链式存储详解

前言

二叉树是数据结构中一个非常重要的概念，它广泛应用于各种算法和程序设计中。在C语言中，我们可以使用链式存储的方式来实现二叉树。本文将详细介绍如何使用C语言实现二叉树的链式存储，并提供相关的代码示例，帮助初学者更好地理解和掌握二叉树的相关知识。

二叉树的基本概念

在正式介绍二叉树的链式存储之前，我们先来回顾一下二叉树的基本概念。

二叉树是一种特殊的树形结构，它的每个节点最多只能有两个子节点，分别称为左子节点和右子节点。二叉树的子树有左右之分，其次序不能颠倒。二叉树的第一个节点称为根节点，根节点的子树称为左子树和右子树。

二叉树具有以下特点：

1. 每个节点最多有两个子节点，即左子节点和右子节点。
2. 左子树和右子树是有顺序的，次序不能随意颠倒。
3. 即使树中某节点只有一个子节点，也要区分它是左子节点还是右子节点。

二叉树节点的定义

在使用链式存储实现二叉树时，我们需要先定义二叉树节点的结构体。每个节点包含三个部分：数据域、左子节点指针和右子节点指针。

typedef struct TreeNode {
    int val;                // 数据域
    struct TreeNode *left;  // 左子节点指针
    struct TreeNode *right; // 右子节点指针
} TreeNode;
1
2
3
4
5

在上面的代码中，我们定义了一个名为TreeNode的结构体，它包含一个整型变量val表示节点的数据，以及两个指向TreeNode类型的指针left和right，分别表示节点的左子节点和右子节点。

创建二叉树节点

有了二叉树节点的定义，我们就可以编写一个函数来创建新的二叉树节点了。

TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
1
2
3
4
5
6
7

在上面的代码中，我们定义了一个名为createNode的函数，它接受一个整型参数val，表示要创建的节点的数据。函数内部首先使用malloc函数动态分配一个TreeNode类型的内存空间，然后将val赋值给新节点的数据域，并将左右子节点指针初始化为NULL，最后返回新创建的节点。

插入节点

创建了新的节点后，我们需要将其插入到二叉树中的适当位置。以下是一个递归实现的插入函数：

void insertNode(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = createNode(val);
    } else {
        if (val < (*root)->val) {
            insertNode(&((*root)->left), val);
        } else if (val > (*root)->val) {
            insertNode(&((*root)->right), val);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

在上面的代码中，insertNode函数接受两个参数：一个指向指针的指针root，表示要插入节点的二叉树的根节点；一个整型变量val，表示要插入的节点的数据。

函数首先判断根节点是否为NULL，如果是，则直接将新节点作为根节点插入。否则，函数会比较要插入的节点的数据与当前节点的数据大小，如果小于当前节点，则递归地在左子树中插入新节点；如果大于当前节点，则递归地在右子树中插入新节点。

二叉树的遍历

二叉树的遍历是指按照某种顺序访问二叉树中的每个节点，使得每个节点都被访问且只被访问一次。二叉树有三种常见的遍历方式：前序遍历、中序遍历和后序遍历。

前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}
1
2
3
4
5
6
7

中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }
}
1
2
3
4
5
6
7

后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->val);
    }
}
1
2
3
4
5
6
7

示例程序

下面是一个完整的示例程序，展示了如何使用C语言实现二叉树的链式存储，并进行插入和遍历操作。

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void insertNode(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = createNode(val);
    } else {
        if (val < (*root)->val) {
            insertNode(&((*root)->left), val);
        } else if (val > (*root)->val) {
            insertNode(&((*root)->right), val);
        }
    }
}

void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }
}

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->val);
    }
}

int main() {
    TreeNode* root = NULL;

    insertNode(&root, 5);
    insertNode(&root, 3);
    insertNode(&root, 7);
    insertNode(&root, 1);
    insertNode(&root, 9);

    printf("前序遍历: ");
    preorderTraversal(root);
    printf("\n");

    printf("中序遍历: ");
    inorderTraversal(root);
    printf("\n");

    printf("后序遍历: ");
    postorderTraversal(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

在上面的示例程序中，我们首先定义了二叉树节点的结构体TreeNode，然后实现了创建节点的函数createNode和插入节点的函数insertNode。接着，我们实现了三种遍历方式的函数：preorderTraversal（前序遍历）、inorderTraversal（中序遍历）和postorderTraversal（后序遍历）。

在main函数中，我们创建了一个空的二叉树，然后通过insertNode函数插入了几个节点。最后，我们分别调用三种遍历函数，打印出二叉树的前序遍历、中序遍历和后序遍历结果。

运行该程序，输出结果如下：

前序遍历: 5 3 1 7 9 
中序遍历: 1 3 5 7 9 
后序遍历: 1 3 9 7 5 
1
2
3

可以看到，程序正确地实现了二叉树的链式存储，并按照不同的遍历方式输出了二叉树的节点值。

总结

本文详细介绍了如何使用C语言实现二叉树的链式存储，包括二叉树节点的定义、创建节点、插入节点以及三种常见的遍历方式（前序遍历、中序遍历和后序遍历）。通过示例程序，我们展示了如何将这些概念应用到实际的编程中。

对于初学者来说，理解和掌握二叉树的链式存储是学习数据结构和算法的重要一步。希望本文能够对你有所帮助，让你更好地理解二叉树的相关知识。如果你有任何问题或建议，欢迎留言交流。