二叉树递归遍历C语言如何实现？

二叉树的递归遍历算法（C语言）

二叉树的递归遍历主要有三种方式：前序遍历、中序遍历和后序遍历，下面我将分别实现这三种遍历算法。

二叉树节点结构定义

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

创建新节点

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

前序遍历（根-左-右）

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

中序遍历（左-根-右）

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

后序遍历（左-右-根）

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

释放二叉树内存

// 释放二叉树内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

主函数示例

int main() {
    // 构建一个示例二叉树
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("前序遍历: ");
    preOrderTraversal(root);
    printf("\n");
    printf("中序遍历: ");
    inOrderTraversal(root);
    printf("\n");
    printf("后序遍历: ");
    postOrderTraversal(root);
    printf("\n");
    // 释放内存
    freeTree(root);
    return 0;
}

输出示例

对于上面构建的二叉树,程序输出将是：

前序遍历: 1 2 4 5 3 
中序遍历: 4 2 5 1 3 
后序遍历: 4 5 2 3 1 

递归遍历的特点

1. 简洁性：递归实现非常简洁，代码量少
2. 直观性：递归代码直接对应遍历的定义
3. 效率：递归调用会有函数调用开销，空间复杂度为O(n)（最坏情况下为树的高度）
4. 栈空间：递归深度可能很大，可能导致栈溢出（对于非常深的树）

对于大型二叉树,可以考虑使用迭代方式（使用栈）来实现遍历，以避免递归带来的栈溢出风险。