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

以下是用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;
}

在上述main函数中，构建了一个简单的二叉树示例，然后分别调用不同的遍历函数并输出结果，方便直观地看到不同遍历方式的效果。实际应用中，你可以根据实际的二叉树结构来进行相应的测试和使用这些遍历方法。