C语言实现二叉树非递归遍历：先序与中序

二叉树遍历是数据结构中的一个重要概念，主要涉及三种基本方式：先序遍历、中序遍历和后序遍历。这里着重讲解了非递归版本的先序遍历和中序遍历。 先序遍历（Preorder Traversal）的非递归实现策略是利用栈的数据结构。首先，从根节点开始，将其压入栈中。然后进入一个循环，只要栈不为空，就弹出栈顶节点并处理。对于当前节点的右子节点，由于要遵循先右后左的顺序，所以在处理完当前节点后，先将其右子节点压入栈。对于左子节点，尽管后续会访问，但为了保持栈的先进后出原则，应先将左子节点压入栈中。这样做的好处是确保了在弹出节点时，始终按照先右子树再左子树的顺序执行。 以下是先序遍历的非递归代码实现： ```java public void preorder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> s = new Stack<>(); // 初始化栈 s.push(root); // 压入根节点 while (!s.isEmpty()) { TreeNode cur = s.pop(); // 弹出栈顶节点并处理 System.out.println(cur.val); // 处理当前节点 if (cur.right != null) { // 右子节点存在 s.push(cur.right); // 先压入右子节点 } if (cur.left != null) { // 左子节点存在 s.push(cur.left); // 后压入左子节点 } } } ``` 中序遍历（Inorder Traversal）则需要先遍历左子树，然后处理当前节点，最后遍历右子树。在非递归实现中，我们需要一个额外的指针`cur`指向当前节点，同时使用栈来辅助。首先将根节点压入栈，并设置`cur`指向根。然后，当`cur`不为空时，不断将`cur`的左子节点压入栈，直到遇到空节点。此时，弹出栈顶元素（即当前左子树的最左节点），处理它，然后将`cur`移动到其右子节点，继续此过程。中序遍历的非递归流程如下： 1. 初始化栈`s`，设置`cur`为根节点 2. 当`cur`不为空，执行以下步骤： - 将`cur`的左子节点压入栈 - 弹出栈顶节点并处理 - 将`cur`更新为其右子节点 3. 重复步骤2，直到`cur`变为`null` 总结来说，非递归二叉树遍历通过巧妙地利用栈的数据结构，实现了对二叉树节点的有序访问，既避免了递归带来的堆栈调用开销，又保证了遍历的正确性。理解和掌握这两种方法，对于深入理解二叉树的结构和遍历算法至关重要。