048. 使用递归进行树的遍历

在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;
}

// 创建一个简单的二叉树
TreeNode* createTree() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    return root;
}

递归实现树的遍历

前序遍历（Pre-order Traversal）

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

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

中序遍历（In-order Traversal）

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

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

后序遍历（Post-order Traversal）

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

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

主函数

在主函数中，创建一棵树并调用不同的遍历函数。

int main() {
    // 创建一棵简单的二叉树
    TreeNode* root = createTree();

    printf("前序遍历结果：\n");
    preOrderTraversal(root);
    printf("\n");

    printf("中序遍历结果：\n");
    inOrderTraversal(root);
    printf("\n");

    printf("后序遍历结果：\n");
    postOrderTraversal(root);
    printf("\n");

    // 释放树的内存（递归释放）
    void freeTree(TreeNode* node) {
        if (node == NULL) {
            return;
        }
        freeTree(node->left);
        freeTree(node->right);
        free(node);
    }
    freeTree(root);

    return 0;
}

示例运行

假设我们创建的二叉树如下：

输出结果：

前序遍历结果：
1 2 4 5 3 6 7

中序遍历结果：
4 2 5 1 6 3 7

后序遍历结果：
4 5 2 6 7 3 1

递归遍历的特点

简洁性：递归实现的代码简洁易读，逻辑清晰。
效率：递归遍历的时间复杂度为 O(n)，其中 n 是树中节点的数量。
空间复杂度：递归调用会占用系统栈空间，空间复杂度为 O(h)，其中 h 是树的高度。
适用性：递归是实现树遍历的自然方式，适合处理树结构。

通过递归实现树的遍历，可以方便地访问树中的每个节点，适用于各种树相关的算法和数据处理任务。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)