数据结构学习——树形结构之非递归遍历二叉树
时间：2022-09-05 03:30:00
以上介绍了二叉树和递归遍历二叉树的内容。有兴趣的朋友可以去看看:递归遍历二叉树的树形结构
目录
一. 非递归前序遍历
二.非递归中序遍历
三. 非递归后序遍历
四.数据结构专栏
一. 非递归前序遍历
前序遍历（DLR，lchild,data,rchild），它是一种二叉树遍历，又称先根遍历、先序遍历、前序周游。你可以记得做根。先访问根结点，然后遍历左子树，最后遍历右子树。
前序遍历先访问根结点，再遍历左子树，最后遍历右子树。遍历左右子树时，仍先访问 根点，然后遍历左子树，最后遍历右子树。
若 如果二叉树是空的，返回将结束，否则：
(1)访问根结点。
(2)前序遍历左子树 。
(3)前序遍历右子树 。
需要注意的是，前序遍历仍然用于遍历左右子树。
如图所示:
除了使用递归，二叉树的遍历也可以通过非递归来实现。事实上，大多数可以通过递归解决的问题都可以通过另一种数据结构来解决。这种数据结构是堆栈。因为递归和堆栈具有可追溯性的特点。
如何借助栈来实现二叉树的非递归遍历呢？下面以二叉树的前序遍历为例，看一看具体过程：
1. 二叉树根节点首先遍历A，放入栈中。
2. 左儿童节点2，遍历根节点1，放入栈中。
3. 左儿童节点4，遍历节点2，放入栈中。
4. 节点4既没有左孩子也没有右孩子。我们需要回到最后一个节点2。但现在不是递归操作。如何追溯？别担心，栈已经存储了刚才的路径。让旧栈顶元素4离开栈，您可以再次访问节点2，获得节点2的右儿童节点5。此时，节点2没有使用价值（已访问左右儿童）。节点2离开栈，节点5进入栈。
5. 节点5既没有左孩子也没有右孩子。我们需要再次追溯到节点1。所以让节点5离开栈。
右儿童根节点1为节点3，节点1出栈，节点3入栈。
6. 节点3的右孩子是节点6，节点3出栈，节点6进栈。
7. 节点6既没有左孩子也没有右孩子，所以节点6离开了栈。这时，栈是空的，遍历结束了。
代码如下：
////前序遍历的非递归实现 import java.util.Stack; public class Test { public static void main(String[] args) { TreeNode[] node = new TreeNode[10]; for (int i = 0; i < 10; i ) { node[i] = new TreeNode(i); } for (int i = 0; i < 10; i ) { if (i * 2 1 < 10) node[i].left = node[i * 2 1]; if (i * 2 2 < 10) node[i].right = node[i * 2 2]; } // 非递归实现 preOrderRe(node[0]); } public static void preOrderRe(TreeNode biTree) { Stack stack = new Stack(); //循环体biTree设置为指向左或右节点，因此可能为空。但只要栈不空，就会循环 while (biTree !但只要栈不空，就会循环 while (biTree != null || !stack.isEmpty()) { ///一直到最左边的左节点结束 while (biTree != null) { System.out.print(biTree.value " "); stack.push(biTree); biTree = biTree.left; } //只要栈不是空的，就可以从栈上的左节点回到当前的根节点，然后是右子节点 if (!stack.isEmpty()) { biTree = stack.pop(); biTree = biTree.right; } } } } //节点结构 class TreeNode { int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; } } 二.非递归中序遍历
中序遍历（LDR）是 一种二叉树遍历，又称 中根遍历，中序周游。二叉树中，先左后根再右。巧记:左根右。
先遍历左子树，再访问根结点，最后遍历右子树
若 如果二叉树是空的，返回将结束。
否则：
(1)中序遍历左子树
(2)访问根结点
(3)中序遍历右子树
如图所示：
中序遍历结果：DBEAFC
实现代码:
import java.util.Stack; public class Test { public static void main(String[] args) { TreeNode[] node = new TreeNode[10]; for (int i = 0; i < 10; i ) { node[i] = new TreeNode(i); } for (int i = 0; i < 10; i ) { if (i * 2 1 < 10) node[i].left = node[i * 2 1]; if (i * 2 2 < 10) node[i].right = node[i * 2 2]; } //中序遍历 midOrderRe(node[0]); } public static void midOrderRe(TreeNode biTree) { Stack stack = new Stack(); while (biTree != null || != null || !stack.isEmpty()) { while (biTree != null) { stack.push(biTree); biTree = biTree.left; } if (!stack.isEmpty()) { biTree = stack.pop(); System.out.print(biTree.value " "); biTree = biTree.right; } } } } //节点结构 class TreeNode{ int value; TreeNode left; TreeNode right; TreeNode(int value){ this.value = value; } } 三. 非递归后序遍历
&nbp; 后序遍历（LRD）是 二叉树遍历的一种，也叫做 后根遍历、后序周游，可记做左右根。后序遍历有 递归算法和非递归算法两种。在二叉树中，先左后右再根。巧记：左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若 二叉树为空则结束返回，否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
如图所示
后序遍历结果：DEBFCA
算法核心思想：
首先要搞清楚先序、中序、后序的非递归算法共同之处：用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。
实现代码:
import java.util.Stack;
public class Test {
public static void main(String[] args) {
TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树
for (int i = 0; i < 10; i++) {
node[i] = new TreeNode(i);
}
for (int i = 0; i < 10; i++) {
if (i * 2 + 1 < 10)
node[i].left = node[i * 2 + 1];
if (i * 2 + 2 < 10)
node[i].right = node[i * 2 + 2];
}
// 后序遍历非递归实现
postOrderRe(node[0]);
}
public static void postOrderRe(TreeNode biTree) {
int leftFlag = 1;// 在辅助栈里表示左节点
int rightFlag = 2;// 在辅助栈里表示右节点
Stack stack = new Stack();
// 辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。
Stack stackHelp = new Stack();
while (biTree != null || !stack.empty()) {
while (biTree != null) {
// 将节点压入栈1，并在栈2将节点标记为左节点
stack.push(biTree);
stackHelp.push(leftFlag);
biTree = biTree.left;
}
while (!stack.empty() && stackHelp.peek() == rightFlag) {
// 如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
stackHelp.pop();
System.out.print(stack.pop().value + " ");
}
if (!stack.empty() && stackHelp.peek() == leftFlag) {
// 如果是从左子节点返回父节点，则将标记改为右子节点
stackHelp.pop();
stackHelp.push(rightFlag);
biTree = stack.peek().right;
}
}
}
}
//节点结构
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
}
} 
