C语言树算法详解（从零开始掌握二叉树与常见操作）

用C语言定义二叉树节点

在C语言中，我们通常使用结构体（struct）来定义树的节点：

struct TreeNode {    int data;                // 节点存储的数据    struct TreeNode* left;   // 指向左子节点    struct TreeNode* right;  // 指向右子节点};typedef struct TreeNode Node;  

创建新节点

为了方便使用，我们可以写一个函数来动态分配内存并初始化一个新节点：

#include <stdio.h>#include <stdlib.h>Node* createNode(int value) {    Node* newNode = (Node*)malloc(sizeof(Node));    if (!newNode) {        printf("内存分配失败！\n");        return NULL;    }    newNode->data = value;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}  

二叉树的三种遍历方式

遍历是访问树中所有节点的过程。对于二叉树，有三种经典遍历方法，它们都属于C语言数据结构中的核心内容：

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

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

// 前序遍历void preorder(Node* root) {    if (root != NULL) {        printf("%d ", root->data);        preorder(root->left);        preorder(root->right);    }}// 中序遍历void inorder(Node* root) {    if (root != NULL) {        inorder(root->left);        printf("%d ", root->data);        inorder(root->right);    }}// 后序遍历void postorder(Node* root) {    if (root != NULL) {        postorder(root->left);        postorder(root->right);        printf("%d ", root->data);    }}  

完整示例：构建并遍历一棵二叉树

下面是一个完整的程序，演示如何构建一棵简单的二叉树并进行三种遍历：

#include <stdio.h>#include <stdlib.h>struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;};typedef struct TreeNode Node;Node* createNode(int value) {    Node* newNode = (Node*)malloc(sizeof(Node));    newNode->data = value;    newNode->left = NULL;    newNode->right = NULL;    return newNode;}void inorder(Node* root) {    if (root) {        inorder(root->left);        printf("%d ", root->data);        inorder(root->right);    }}int main() {    // 构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5    Node* root = createNode(1);    root->left = createNode(2);    root->right = createNode(3);    root->left->left = createNode(4);    root->left->right = createNode(5);    printf("中序遍历结果: ");    inorder(root);    printf("\n");    return 0;}  

为什么学习C语言树算法很重要？

掌握树的实现不仅能帮助你理解更复杂的数据结构（如AVL树、红黑树、B树等），还能提升你在面试和实际项目中的问题解决能力。例如，表达式求值、哈夫曼编码、决策树等都依赖于树结构。

小结

本文介绍了C语言树算法的基础知识，包括二叉树的定义、节点创建、三种遍历方式，并提供了可运行的代码示例。通过动手实践这些代码，即使是编程小白也能逐步掌握二叉树遍历和C语言数据结构的核心思想。

建议读者尝试修改代码，比如添加插入节点、查找节点或计算树的高度等功能，以加深对树的实现的理解。