分别设计出先序中序和后序遍历二叉树的非递归算法

当然，二叉树的遍历有三种主要方式：先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。非递归的层次遍历（也叫广度优先遍历，从上到下、从左到右）通常使用队列来辅助实现。 这里分别给出这些遍历的非递归算法代码： 1. 层序遍历（广度优先遍历）： ```c #include <stdio.h> #include <stdlib.h> #include <queue> struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; void levelOrder(struct TreeNode* root) { if (root == NULL) return; // 使用队列存储每一层的节点 queue<struct TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { struct TreeNode* node = q.front(); q.pop(); printf("%d ", node->val); // 打印当前节点值 if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } printf("\n"); // 换行表示新的一层 } } ``` 2. 先序遍历（递归和非递归两种方式，这里是非递归版本，使用栈）： ```c void preorderNonRecursive(struct TreeNode* root) { if (root == NULL) return; stack<struct TreeNode*> s; s.push(root); while (!s.empty()) { struct TreeNode* node = s.top(); s.pop(); printf("%d ", node->val); // 打印当前节点值 if (node->right != NULL) s.push(node->right); if (node->left != NULL) s.push(node->left); } } ``` 3. 中序遍历（非递归，同样使用栈）： ```c void inorderNonRecursive(struct TreeNode* root) { if (root == NULL) return; stack<struct TreeNode*> s; struct TreeNode* curr = root; while (curr != NULL || !s.empty()) { while (curr != NULL) { s.push(curr); curr = curr->left; } curr = s.top(); s.pop(); printf("%d ", curr->val); // 打印当前节点值 curr = curr->right; } } ``` 4. 后序遍历（非递归，使用两个栈）： ```c void postorderNonRecursive(struct TreeNode* root) { if (root == NULL) return; stack<struct TreeNode*> s1, s2; s1.push(root); while (!s1.empty()) { struct TreeNode* node = s1.top(); s1.pop(); s2.push(node); if (node->left != NULL) s1.push(node->left); if (node->right != NULL) s1.push(node->right); } while (!s2.empty()) { struct TreeNode* node = s2.top(); s2.pop(); printf("%d ", node->val); // 打印当前节点值 } } ```

<think>我们讨论二叉树的三种遍历方式：先序、中序、后序，以及它们的递归和非递归实现。递归实现：直接按照遍历定义编写。非递归实现：使用栈来模拟递归过程。1.先序遍历（PreorderTraversal）:根->左->右2.中序遍历（InorderTraversal）:左->根->右3.后序遍历（PostorderTraversal）:左->右->根注意：非递归实现中，先序和中序相对简单，后序稍微复杂（需要记录上次访问的节点）。我们将分别给出递归和非递归的代码实现（以Java为例）。同时，为了演示方便，我们假设二叉树节点的定义如下：```javaclassTreeNode{charval;TreeNodeleft;TreeNoderight;TreeNode(charx){val=x;}}```一、递归实现：1.先序遍历递归：```javapublicvoidpreorderRecursive(TreeNoderoot){if(root==null)return;System.out.print(root.val+"");//访问根节点preorderRecursive(root.left);//递归左子树preorderRecursive(root.right);//递归右子树}```2.中序遍历递归：```javapublicvoidinorderRecursive(TreeNoderoot){if(root==null)return;inorderRecursive(root.left);//递归左子树System.out.print(root.val+"");//访问根节点inorderRecursive(root.right);//递归右子树}```3.后序遍历递归：```javapublicvoidpostorderRecursive(TreeNoderoot){if(root==null)return;postorderRecursive(root.left);//递归左子树postorderRecursive(root.right);//递归右子树System.out.print(root.val+"");//访问根节点}```二、非递归实现：1.先序遍历非递归：思路：使用栈，先将根节点入栈，然后循环直到栈空。每次出栈一个节点，访问它，然后先将其右孩子入栈，再将其左孩子入栈（注意顺序，因为栈是后进先出，所以先右后左，这样出栈时才是先左后右）。```javapublicvoidpreorderNonRecursive(TreeNoderoot){if(root==null)return;Stack<TreeNode>stack=newStack<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();System.out.print(node.val+"");//访问//先右后左，保证左子树先处理if(node.right!=null)stack.push(node.right);if(node.left!=null)stack.push(node.left);}}```2.中序遍历非递归：思路：使用栈，从根节点开始，先将当前节点的所有左子节点入栈，然后出栈一个节点（此时是最左节点），访问它，然后转向其右子树，对右子树同样进行左链入栈。```javapublicvoidinorderNonRecursive(TreeNoderoot){if(root==null)return;Stack<TreeNode>stack=newStack<>();TreeNodecur=root;while(cur!=null||!stack.isEmpty()){//将当前节点的所有左子节点入栈while(cur!=null){stack.push(cur);cur=cur.left;}cur=stack.pop();System.out.print(cur.val+"");//访问cur=cur.right;//转向右子树}}```3.后序遍历非递归：思路：后序遍历的非递归实现比前两种稍复杂，因为根节点需要在其左右子树都被访问后才能访问。我们可以用两个栈，或者用一个栈并记录上一个访问的节点。这里采用记录上一个访问节点的方法。方法：使用一个栈，首先将根节点入栈。然后设置一个指针`prev`表示上一次访问的节点（初始为null）。在循环中，首先获取栈顶节点（不出栈），判断当前栈顶节点是否可以访问：即其左右子树都已经被访问过（右子树为空或者右子树已经被访问，或者左子树为空且右子树已经被访问，或者左右子树都为空）。如果可访问则访问并出栈，同时记录`prev`为当前节点；否则，将当前节点的右子树和左子树依次入栈（注意顺序：因为入栈顺序是先右后左，出栈顺序则是先左后右，这样就能保证左右子树都被访问后才访问根节点）。但更常用的方法是：后序遍历的顺序是“左右根”，我们可以按照“根右左”的顺序遍历（类似先序遍历，但是调换左右顺序），然后将结果反转即可得到“左右根”的顺序。但这里我们使用传统的一个栈的方法：```javapublicvoidpostorderNonRecursive(TreeNoderoot){if(root==null)return;Stack<TreeNode>stack=newStack<>();TreeNodecur=root;TreeNodeprev=null;//记录上一个访问的节点while(cur!=null||!stack.isEmpty()){//将当前节点的所有左子节点入栈while(cur!=null){stack.push(cur);cur=cur.left;}cur=stack.peek();//查看栈顶元素//如果当前节点的右子树为空，或者右子树已经被访问过，则访问当前节点if(cur.right==null||cur.right==prev){System.out.print(cur.val+"");//访问stack.pop();prev=cur;cur=null;//当前节点已经访问过，置为空，避免再次进入左链循环}else{//否则，转向右子树cur=cur.right;}}}```三、总结：二叉树的遍历是基础，递归实现简单直观，但递归会使用函数栈空间。非递归实现使用栈来模拟递归过程，空间复杂度与递归相同，但可以避免递归调用的开销[^1][^3]。§§相关问题§§1.如何根据二叉树的先序遍历序列和中序遍历序列重建二叉树？2.如何实现二叉树的层序遍历（广度优先遍历）？3.二叉树遍历的应用有哪些（比如求树的高度、节点个数等）？</think> ### 二叉树的递归与非递归遍历算法 二叉树的遍历是数据结构基础，以下是**先序、中序、后序遍历**的递归与非递归实现（Java版）： #### 树节点定义 ```java class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char x) { val = x; } } ``` --- ### 1. 递归遍历实现 递归算法直接遵循遍历定义，简洁但需要函数调用栈空间。 #### 1.1 先序遍历（根→左→右） ```java void preOrderRecur(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); // 访问根 preOrderRecur(root.left); // 递归左子树 preOrderRecur(root.right); // 递归右子树 } ``` #### 1.2 中序遍历（左→根→右） ```java void inOrderRecur(TreeNode root) { if (root == null) return; inOrderRecur(root.left); // 递归左子树 System.out.print(root.val + " "); // 访问根 inOrderRecur(root.right); // 递归右子树 } ``` #### 1.3 后序遍历（左→右→根） ```java void postOrderRecur(TreeNode root) { if (root == null) return; postOrderRecur(root.left); // 递归左子树 postOrderRecur(root.right); // 递归右子树 System.out.print(root.val + " "); // 访问根 } ``` --- ### 2. 非递归遍历实现 使用栈模拟递归过程，避免栈溢出风险[^3]。 #### 2.1 先序遍历非递归 **实现思路**：根节点入栈 → 循环：出栈并访问 → 右子入栈 → 左子入栈 ```java void preOrderNonRecur(TreeNode root) { if (root == null) return; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); System.out.print(node.val + " "); // 注意：先右后左入栈 if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } } ``` #### 2.2 中序遍历非递归 **实现思路**：循环左链入栈 → 出栈访问 → 转向右子树 ```java void inOrderNonRecur(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 左链入栈 while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); System.out.print(cur.val + " "); cur = cur.right; // 关键：转向右子树 } } ``` #### 2.3 后序遍历非递归 **实现思路**：用 `prev` 记录已访问节点，避免重复访问右子树 ```java void postOrderNonRecur(TreeNode root) { if (root == null) return; Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root, prev = null; while (cur != null || !stack.isEmpty()) { // 左链入栈 while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.peek(); // 右子树已访问或为空 if (cur.right == null || cur.right == prev) { System.out.print(cur.val + " "); prev = cur; stack.pop(); cur = null; // 关键：避免重复处理左子树 } else { cur = cur.right; } } } ``` --- ### 关键对比总结 | 遍历方式 | 递归特点 | 非递归核心操作 | |----------|----------------------|-----------------------------| | **先序** | 根→左→右自然递归 | 右→左入栈保证左子树优先处理 | | **中序** | 左子树优先返回 | 左链入栈+转向右子树 | | **后序** | 最后访问根节点 | 记录`prev`避免重复访问右子树 | 非递归实现通过栈模拟函数调用栈，时间复杂度均为 $O(n)$，空间复杂度 $O(h)$（h为树高）[^1][^3]。