数据结构---------二叉树前序遍历中序遍历后序遍历

以下是用C语言实现二叉树的前序遍历、中序遍历和后序遍历的代码示例，包括递归和非递归（借助栈实现）两种方式：

1. 二叉树节点结构体定义

#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

2. 前序遍历

（ps:图来自一位前辈，非常感谢无商用）
在这里插入图片描述

2.1 递归方式

// 前序遍历递归函数
void preorderTraversalRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorderTraversalRecursive(root->left);
    preorderTraversalRecursive(root->right);
}

解释：

首先判断根节点是否为空（NULL），如果为空，说明已经遍历完或者二叉树本身就是空树，直接返回，不做任何操作。
若根节点不为空，则先输出根节点的值（通过printf函数），这符合前序遍历“根节点、左子树、右子树”的顺序。
接着递归调用preorderTraversalRecursive函数去遍历左子树，完成左子树的前序遍历。
最后再递归调用该函数遍历右子树，完成整个二叉树的前序遍历。

2.2 非递归方式（借助栈实现）

// 前序遍历非递归函数（借助栈）
void preorderTraversalNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[100];  // 简单起见，这里假设栈的最大容量为100，可以根据实际情况调整
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        TreeNode* current = stack[top--];
        printf("%d ", current->val);
        if (current->right!= NULL) {
            stack[++top] = current->right;
        }
        if (current->left!= NULL) {
            stack[++top] = current->left;
        }
    }
}

解释：

同样先判断根节点是否为空，为空则直接返回。
然后创建一个数组来模拟栈（这里简单地定义了固定大小为100的数组作为栈，实际应用中可根据二叉树规模动态分配内存），并初始化栈顶指针top为 -1，表示栈为空。
将根节点入栈后，进入循环，只要栈不为空（即top >= 0）：
- 取出栈顶元素（current = stack[top--]），输出其值，这模拟了访问根节点的操作。
- 按照前序遍历先右后左的顺序将子节点入栈（因为栈是后进先出的数据结构，先入栈右子节点，后入栈左子节点，这样出栈时就能先访问左子树），如果右子节点或左子节点不为空，就将它们依次入栈，以便后续继续遍历。

3. 中序遍历

在这里插入图片描述

3.1 递归方式

// 中序遍历递归函数
void inorderTraversalRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversalRecursive(root->left);
    printf("%d ", root->val);
    inorderTraversalRecursive(root->right);
}

解释：

先判断根节点是否为空，为空则返回。
按照中序遍历“左子树、根节点、右子树”的顺序，首先递归调用inorderTraversalRecursive函数去遍历左子树，确保左子树的节点先被访问。
当左子树遍历完后，输出根节点的值。
最后再递归调用该函数遍历右子树，完成整个二叉树的中序遍历。

3.2 非递归方式（借助栈实现）

// 中序遍历非递归函数（借助栈）
void inorderTraversalNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[100];  // 假设栈最大容量为100，可按需调整
    int top = -1;
    TreeNode* current = root;
    while (current!= NULL || top >= 0) {
        while (current!= NULL) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        printf("%d ", current->val);
        current = current->right;
    }
}

解释：

还是先判断根节点是否为空，为空则返回。
创建一个栈并初始化栈顶指针，同时用current指针指向根节点。
进入循环，只要current不为空或者栈不为空：
- 先通过内层循环将当前节点及其所有左子树节点依次入栈（不断将current指向其左子节点并入栈），直到current为空，这意味着找到了最左边的节点。
- 然后取出栈顶元素（即最左边的节点），输出其值，这模拟了访问根节点的操作（在中序遍历中此时访问的是左子树遍历完后的根节点）。
- 最后将current更新为该节点的右子节点，以便继续遍历右子树，重复上述过程，完成中序遍历。

4. 后序遍历

在这里插入图片描述

4.1 递归方式

// 后序遍历递归函数
void postorderTraversalRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversalRecursive(root->left);
    postorderTraversalRecursive(root->right);
    printf("%d ", root->val);
}

解释：

首先判断根节点是否为空，为空则返回，不做后续操作。
按照后序遍历“左子树、右子树、根节点”的顺序，先递归调用postorderTraversalRecursive函数遍历左子树。
接着递归调用该函数遍历右子树。
最后输出根节点的值，完成整个二叉树的后序遍历。

4.2 非递归方式（借助栈实现）

// 后序遍历非递归函数（借助栈）
void postorderTraversalNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack1[100];  // 假设栈1最大容量为100，可按需调整
    struct TreeNode *stack2[100];  // 假设栈2最大容量为100，可按需调整
    int top1 = -1, top2 = -1;
    stack1[++top1] = root;
    while (top1 >= 0) {
        TreeNode* current = stack1[top1--];
        stack2[++top2] = current;
        if (current->left!= NULL) {
            stack1[++top1] = current->left;
        }
        if (current->right!= NULL) {
            stack1[++top1] = current->right;
        }
    }
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->val);
    }
}

解释：

先判断根节点是否为空，为空则返回。
创建两个栈stack1和stack2（这里同样是简单地假设了固定大小为100的数组来模拟栈，实际可按需优化），以及对应的栈顶指针top1和top2，并将根节点入stack1。
在第一个循环中：
- 从stack1中取出栈顶元素，放入stack2中，这一步是为了后续能按后序遍历的顺序输出节点。
- 然后按照后序遍历先左后右的顺序将其左子节点和右子节点（如果存在）依次入stack1，方便后续处理。
第一个循环结束后，stack2中存储的节点顺序就是后序遍历的顺序了，通过第二个循环依次输出stack2中节点的值，完成二叉树的后序遍历。

你可以使用以下代码来测试这些遍历函数：

int main() {
    // 构建一个简单的二叉树示例
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->val = 4;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 5;

    // 测试前序遍历
    printf("前序遍历（递归）结果：");
    preorderTraversalRecursive(root);
    printf("\n");
    printf("前序遍历（非递归）结果：");
    preorderTraversalNonRecursive(root);
    printf("\n");

    // 测试中序遍历
    printf("中序遍历（递归）结果：");
    inorderTraversalRecursive(root);
    printf("\n");
    printf("中序遍历（非递归）结果：");
    inorderTraversalNonRecursive(root);
    printf("\n");

    // 测试后序遍历
    printf("后序遍历（递归）结果：");
    postorderTraversalRecursive(root);
    printf("\n");
    printf("后序遍历（非递归）结果：");
    postorderTraversalNonRecursive(root);
    printf("\n");

    return 0;
}