C语言树数据结构入门（从零开始掌握二叉树的定义、创建与遍历）

用C语言定义二叉树节点

在C语言中，我们通常使用结构体（struct）来定义树的节点。每个节点包含数据域和指向左右子节点的指针：

#include <stdio.h>#include <stdlib.h>// 定义二叉树节点结构typedef struct TreeNode {    int data;                    // 节点存储的数据    struct TreeNode* left;       // 指向左子节点    struct TreeNode* right;      // 指向右子节点} TreeNode;  

创建新节点

为了方便构建树，我们编写一个函数来动态分配内存并初始化一个新节点：

// 创建新节点TreeNode* createNode(int value) {    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));    if (newNode == NULL) {        printf("内存分配失败！\n");        return NULL;    }    newNode->data = value;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}  

构建一个简单的二叉树

下面的例子将创建如下结构的二叉树：

      1     / \    2   3   / \  4   5  

int main() {    // 创建根节点    TreeNode* root = createNode(1);        // 添加左右子节点    root->left = createNode(2);    root->right = createNode(3);        // 为左子节点添加子节点    root->left->left = createNode(4);    root->left->right = createNode(5);        printf("二叉树创建成功！\n");    return 0;}  

树的遍历：三种基本方式

遍历是访问树中所有节点的过程。常见的遍历方式有三种，它们都属于树遍历算法的核心内容：

• 前序遍历（Pre-order）：根 → 左 → 右
• 中序遍历（In-order）：左 → 根 → 右
• 后序遍历（Post-order）：左 → 右 → 根

以下是三种遍历的C语言实现：

// 前序遍历void preorderTraversal(TreeNode* node) {    if (node != NULL) {        printf("%d ", node->data);        preorderTraversal(node->left);        preorderTraversal(node->right);    }}// 中序遍历void inorderTraversal(TreeNode* node) {    if (node != NULL) {        inorderTraversal(node->left);        printf("%d ", node->data);        inorderTraversal(node->right);    }}// 后序遍历void postorderTraversal(TreeNode* node) {    if (node != NULL) {        postorderTraversal(node->left);        postorderTraversal(node->right);        printf("%d ", node->data);    }}  

完整示例与运行结果

将上述代码整合后，完整的程序如下：

#include <stdio.h>#include <stdlib.h>typedef struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;TreeNode* createNode(int value) {    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));    newNode->data = value;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}void inorderTraversal(TreeNode* node) {    if (node != NULL) {        inorderTraversal(node->left);        printf("%d ", node->data);        inorderTraversal(node->right);    }}int main() {    TreeNode* root = createNode(1);    root->left = createNode(2);    root->right = createNode(3);    root->left->left = createNode(4);    root->left->right = createNode(5);        printf("中序遍历结果: ");    inorderTraversal(root);    printf("\n");        return 0;}  

运行结果：

中序遍历结果: 4 2 5 1 3

总结

通过本教程，你已经掌握了C语言数据结构中树的基本概念、二叉树的定义、创建方法以及三种核心遍历算法。这些知识是深入学习平衡树、二叉搜索树、堆等高级结构的基石。

记住，实践是最好的老师。建议你动手编写代码，尝试修改树的结构，观察不同遍历方式的输出结果。随着练习的深入，你会对C语言树结构和树遍历算法有更深刻的理解。

继续加油，你离成为C语言高手又近了一步！