二叉树的前序、中序和后序遍历算法

#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 preOrder(TreeNode *root) {
    if (root == NULL) {
        return;  // 递归终止条件：空节点
    }
    printf("%d ", root->data);  // 访问根节点
    preOrder(root->left);       // 遍历左子树
    preOrder(root->right);      // 遍历右子树
}

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

// 后序遍历：左 -> 右 -> 根
void postOrder(TreeNode *root) {
    if (root == NULL) {
        return;  // 递归终止条件：空节点
    }
    postOrder(root->left);      // 遍历左子树
    postOrder(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   6
  
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
  
    printf("前序遍历: ");
    preOrder(root);  // 预期输出: 1 2 4 5 3 6
  
    printf("\n中序遍历: ");
    inOrder(root);   // 预期输出: 4 2 5 1 3 6
  
    printf("\n后序遍历: ");
    postOrder(root); // 预期输出: 4 5 2 6 3 1
  
    // 释放内存
    freeTree(root);
    return 0;
}

代码解析

1. 数据结构定义：
   • 定义了 TreeNode结构体，包含数据域和左右子树指针
   • 每个节点包含一个整数数据，以及指向左右孩子的指针
2. 核心遍历算法：
   • 三种遍历算法都采用递归实现，逻辑清晰，易于理解
   • 区别仅在于访问根节点的时机不同：
     • 前序遍历：先访问根节点，再遍历左子树，最后遍历右子树
     • 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树
     • 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点
3. 递归终止条件：
   • 当遇到空节点（root == NULL）时，递归函数返回
   • 这是所有递归遍历算法的关键，确保不会无限递归
4. 示例树结构：
   • 代码中构建了一棵简单的二叉树用于测试
   • 通过不同的遍历方式，可以得到不同的输出序列

一、时间复杂度（前序 / 中序 / 后序遍历均相同）

• 结论：O (n)，其中 n 为二叉树的节点总数。
• 原因：
  三种遍历方式（前序、中序、后序）都需要访问每个节点恰好一次。
  对每个节点的操作（打印数据、递归调用左右子树）都是常数时间 O (1)，总操作次数与节点数 n 成正比，因此整体时间复杂度为 O (n)。

二、空间复杂度

• 结论：最坏情况下 O (n)，最好情况下 O (log n)。
• 原因：
  空间复杂度主要来自递归调用栈的深度（代码中没有使用其他额外的辅助空间）。* 最坏情况：当二叉树是 “斜树”（所有节点只有左孩子或只有右孩子，如单链状），递归栈的深度会等于节点总数 n（每次递归只能访问一个节点，栈需要保存 n 个调用帧），此时空间复杂度为 O (n)。
  • 最好情况：当二叉树是 “平衡二叉树”（左右子树高度差不超过 1），递归栈的深度为树的高度 log₂n（向上取整），此时空间复杂度为 O (log n)。

补充说明

• freeTree函数的时空复杂度与遍历函数一致：时间 O (n)（每个节点释放一次），空间 O (n)（最坏情况，递归栈深度为 n）。
• 递归实现的遍历空间复杂度由树的高度决定，而迭代实现（用栈模拟递归）的空间复杂度同样取决于树的高度，与递归版本一致。

总体来说，二叉树的递归遍历是 “线性时间、线性空间（最坏情况）” 的算法，符合数据结构中对遍历操作的基本复杂度特征。