当前位置：首页 > news >正文

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

news 2025/7/13 3:15:27

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