C语言二叉树实现（从零开始掌握二叉树数据结构与遍历算法）

1. 定义二叉树节点结构

在 C 语言中，我们使用 struct 来定义二叉树的节点。每个节点包含数据域和两个指向左右子节点的指针：

#include <stdio.h>#include <stdlib.h>typedef struct TreeNode {    int data;    struct TreeNode* left;    struct TreeNode* right;} TreeNode;  

2. 创建新节点

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

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

3. 插入节点（以二叉搜索树为例）

这里我们以二叉搜索树（BST）为例进行插入操作：左子树所有节点值小于根节点，右子树所有节点值大于根节点。

TreeNode* insert(TreeNode* root, int value) {    if (root == NULL) {        return createNode(value);    }    if (value < root->data) {        root->left = insert(root->left, value);    } else if (value > root->data) {        root->right = insert(root->right, value);    }    return root;}  

4. 二叉树的三种遍历方式

遍历是访问树中所有节点的过程。主要有三种方式：

• 前序遍历（根 → 左 → 右）
• 中序遍历（左 → 根 → 右）——对 BST 可得到升序序列
• 后序遍历（左 → 右 → 根）

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

5. 完整示例程序

下面是一个完整的 C 语言程序，演示如何构建一棵二叉搜索树并进行遍历：

int main() {    TreeNode* root = NULL;    // 插入节点    root = insert(root, 50);    insert(root, 30);    insert(root, 70);    insert(root, 20);    insert(root, 40);    insert(root, 60);    insert(root, 80);    printf("前序遍历: ");    preorder(root);    printf("\n");    printf("中序遍历: ");    inorder(root);    printf("\n");    printf("后序遍历: ");    postorder(root);    printf("\n");    return 0;}  

总结

通过本教程，你已经掌握了使用 C语言二叉树实现 的基本方法，包括节点定义、插入和三种经典遍历算法。这些是学习更高级数据结构（如 AVL 树、红黑树）的基础。建议你动手敲一遍代码，加深理解。

记住，二叉树数据结构 是面试和实际开发中的高频考点，熟练掌握将为你打下坚实的编程基础。如果你正在寻找一份系统的 C语言教程，不妨多练习类似的数据结构实现。

最后，不同的应用场景可能需要不同的 二叉树遍历算法，比如表达式求值常用后序遍历，而 BST 的排序输出则依赖中序遍历。理解原理比死记硬背更重要！