二叉树遍历c语言

### C语言实现二叉树的前序、中序和后序遍历 以下是基于C语言实现二叉树前序、中序和后序遍历的方法，分别提供递归和非递归（利用栈）的方式。 #### 节点结构体定义 为了便于操作，先定义二叉树节点的数据结构： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构体 typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; ``` --- #### 1. 前序遍历 (Preorder Traversal) ##### 递归方法 前序遍历按照 **根 -> 左子树 -> 右子树** 的顺序访问节点。 ```c void preorderRecursive(TreeNode* root) { if (root == NULL) return; printf("%d ", root->val); // 访问当前节点 preorderRecursive(root->left); // 遍历左子树 preorderRecursive(root->right); // 遍历右子树 } ``` ##### 非递归方法 (使用栈) 通过显式维护一个栈来模拟递归过程。 ```c void preorderIterative(TreeNode* root) { if (root == NULL) return; TreeNode* stack[100]; // 栈数组 int top = -1; // 栈顶指针初始化为-1 stack[++top] = root; // 将根节点压入栈 while (top != -1) { // 当栈不为空时继续循环 TreeNode* node = stack[top--]; printf("%d ", node->val); // 先将右孩子压入栈（因为栈是后进先出） if (node->right != NULL) stack[++top] = node->right; if (node->left != NULL) stack[++top] = node->left; } } ``` --- #### 2. 中序遍历 (Inorder Traversal) ##### 递归方法 中序遍历按照 **左子树 -> 根 -> 右子树** 的顺序访问节点。 ```c void inorderRecursive(TreeNode* root) { if (root == NULL) return; inorderRecursive(root->left); // 遍历左子树 printf("%d ", root->val); // 访问当前节点 inorderRecursive(root->right); // 遍历右子树 } ``` ##### 非递归方法 (使用栈) 同样可以通过栈来实现非递归版本。 ```c void inorderIterative(TreeNode* root) { if (root == NULL) return; TreeNode* stack[100]; // 栈数组 int top = -1; // 栈顶指针初始化为-1 TreeNode* current = root; // 初始化指向根节点 while (current != NULL || top != -1) { // 不断向左走并将沿途节点压入栈 while (current != NULL) { stack[++top] = current; current = current->left; } // 出栈并访问该节点 current = stack[top--]; printf("%d ", current->val); // 移动到右子树 current = current->right; } } ``` --- #### 3. 后序遍历 (Postorder Traversal) ##### 递归方法 后序遍历按照 **左子树 -> 右子树 -> 根** 的顺序访问节点。 ```c void postorderRecursive(TreeNode* root) { if (root == NULL) return; postorderRecursive(root->left); // 遍历左子树 postorderRecursive(root->right); // 遍历右子树 printf("%d ", root->val); // 访问当前节点 } ``` ##### 非递归方法 (使用两个栈) 由于后序遍历较复杂，可以采用双栈法简化逻辑。 ```c void postorderIterative(TreeNode* root) { if (root == NULL) return; TreeNode* stack1[100], *stack2[100]; // 使用两个栈 int top1 = -1, top2 = -1; stack1[++top1] = root; // 将根节点压入第一个栈 while (top1 != -1) { // 当第一个栈不为空时继续 TreeNode* node = stack1[top1--]; stack2[++top2] = node; // 将弹出的节点压入第二个栈 // 先将左孩子压入第一个栈，再将右孩子压入 if (node->left != NULL) stack1[++top1] = node->left; if (node->right != NULL) stack1[++top1] = node->right; } // 输出第二个栈中的所有元素 while (top2 != -1) { printf("%d ", stack2[top2--]->val); } } ``` 以上展示了如何用C语言实现二叉树的三种遍历方式及其对应的非递归形式[^1]。 ---